Lecture 3 – Relations
Elements in two sets may be related in some way. These relationships may be represented
mathematically in various ways.
Binary Relations
A binary relation is defined from one set onto another as ordered pairs. This can be written as a R b
or <a, b> ∈ R. This shows that a and b are in a relationship R.
In the circumstance where the two sets are equal, that being each item of the pair is in both sets, it
can be said that the relation from A to B is also called the relation on A.
The relation R of two sets is always a subset of the cartesian product of the sets: R ∈ (A x B).
Two binary relations (Ra and Rb of A1 x A2 and B1 x B2) may be equal if the following is true:
• Their supersets are the same, i.e. A1 = B1 and A2 = B2.
• The set of things related are the same as sets, Ra = Rb.
For example,
R1 = {<1, 2> , <2, 2>} ∈ {1, 2} x {1, 2}
R2 = {<a, b> , <b, b>} ∈ {a, b} x {a, b}
R1 = R2 if:
• set {1, 2} = {a, b}
• {<1, 2> , <2, 2>} = {<a, b> , <b, b>}
This shows us that a = 1 and b = 2
Ordered n-Tuples
With n sets, an ordered n-tuple is a set of n objects in order.
Written: <x1, x2, ..., xn>
• There are n sets and n elements in the n-tuple where, x1 ∈ A1, x2 ∈ A2, ... xn ∈ An.
The total possible n-tuples is the cartesian product of the sets from which the tuples are produced
A set of n-tuples on n sets is called an n-ary relation. An n-ary relation, R, is a subset of the set of the
cartesian product of the parent sets.
n-ary relation R1 ∈ A1 x ... x An
m-ary relation R2 ∈ B1 x ... x Bm
R1 = R2 if
• m=n
• Ai = Bi for each i, 1 ≤i ≤n
Elements in two sets may be related in some way. These relationships may be represented
mathematically in various ways.
Binary Relations
A binary relation is defined from one set onto another as ordered pairs. This can be written as a R b
or <a, b> ∈ R. This shows that a and b are in a relationship R.
In the circumstance where the two sets are equal, that being each item of the pair is in both sets, it
can be said that the relation from A to B is also called the relation on A.
The relation R of two sets is always a subset of the cartesian product of the sets: R ∈ (A x B).
Two binary relations (Ra and Rb of A1 x A2 and B1 x B2) may be equal if the following is true:
• Their supersets are the same, i.e. A1 = B1 and A2 = B2.
• The set of things related are the same as sets, Ra = Rb.
For example,
R1 = {<1, 2> , <2, 2>} ∈ {1, 2} x {1, 2}
R2 = {<a, b> , <b, b>} ∈ {a, b} x {a, b}
R1 = R2 if:
• set {1, 2} = {a, b}
• {<1, 2> , <2, 2>} = {<a, b> , <b, b>}
This shows us that a = 1 and b = 2
Ordered n-Tuples
With n sets, an ordered n-tuple is a set of n objects in order.
Written: <x1, x2, ..., xn>
• There are n sets and n elements in the n-tuple where, x1 ∈ A1, x2 ∈ A2, ... xn ∈ An.
The total possible n-tuples is the cartesian product of the sets from which the tuples are produced
A set of n-tuples on n sets is called an n-ary relation. An n-ary relation, R, is a subset of the set of the
cartesian product of the parent sets.
n-ary relation R1 ∈ A1 x ... x An
m-ary relation R2 ∈ B1 x ... x Bm
R1 = R2 if
• m=n
• Ai = Bi for each i, 1 ≤i ≤n
