2.3. RELATIONS 322.3. Relations2.3.1. Relations. Assume that we have a set of men M and a setof women W , some of whom are married. We want to express whichmen in M are married to which women in W. One way to do that is bylisting the set of pairs (m, w) such that m is a man, w is a woman, andm is married tow. So, the relation “married to” can be representedby a subset of the Cartesian product M × W . In general, a relation Rfrom a set A to a set B will be understood as a subset of the Cartesianproduct A × B, i.e., R ⊆ A × B. If an element a ∈ A is related to anelement b ∈ B, we often write a R b instead of (a, b) ∈ R.The set{a ∈ A | a R b for some b ∈ B}is called the domain of R. Theset{b ∈ B | a R b for some a ∈ A}is called the range of R. For instance, in the relation “married to”above, the domain is the set of married men, and the range is the setof married women.If A and B are the same set, then any subset of A × A will be abinary relation in A. For instance, assume A = {1, 2, 3, 4}. Then thebinary relation “less than” in A will be:<A= {(x, y) ∈ A × A | x < y}= {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}.Notation: A set A with a binary relation R is sometimes representedby the pair (A, R). So,for instance, (Z, ≤) means the set of integerstogether with the relation of non-strict inequality.2.3.2. Representations of Relations.Arrow diagrams. Venn diagrams and arrows can be used for repre-senting relations between given sets. As an example, figure 2.14 rep-resents the relation from A = {a, b, c, d} to B = {1, 2, 3, 4} given byR = {(a, 1), (b, 1), (c, 2), (c, 3)}. In the diagram an arrow from x to ymeans that x is related to y. This kind of graph is called directed graphor digraph.2.3. RELATIONS 33abc1234dABFigure 2.14. Relation.Another example is given in diagram 2.15, which represents thedivisibility relation on the set {1, 2, 3, 4, 5, 6, 7, 8, 9}.123456789Figure 2.15. Binary relation of divisibility.Matrix of a Relation. Another way of representing a relation Rfrom A to B is with a matrix. Its rows are labeled with the elementsof A, and its columns are labeled with the elements of B. If a ∈ Aand b ∈ B then we write 1 in row a column b if a R b, otherwise wewrite 0. For instance the relation R = {(a, 1), (b, 1), (c, 2), (c, 3)} fromA = {a, b, c, d} to B = {1, 2, 3, 4} has the following matrix:1 2 3 4abcd1 0 0 01 0 0 00 1 1 00 0 0 02.3.3. Inverse Relation. Given a relation R from A to B, theinverse of R, denoted R−1, is the relation from B to A defined asb R−1a ⇔ a R b .2.3. RELATIONS 34For instance, if R is the relation “being a son or daughter of”, thenR−1is the relation “being a parent of”.2.3.4. Composition of Relations. Let A, B and C be three sets.Given a relation R from Ato B and a relation S from B to C, thenthe composition S ◦ R of relations R andS is a relation from A to Cdefined by:a (S ◦ R) c ⇔ there exists some b ∈ B such that a R b and b S c .For instance, if R is the relation “to be the father of”, and S is therelation “to be married to”, then S ◦R is the relation “to be the fatherin law of”.2.3.5. Properties of Binary Relations. A binary relation RonA is called:1. Reflexive if for all x ∈ A, x R x. For instance on Z the relation“equal to” (=) is reflexive.2. Transitive if for all x, y, z ∈ A, x R y and y R z implies x R z.For instance equality (=) and inequality (<) on Z are transitiverelations.3. Symmetricif for all x, y ∈ A, x R y ⇒ y R x. For instance on Z,equality (=) is symmetric, but strict inequality (<) is not.4. Antisymmetric if for all x, y ∈ A, x R y and y R x implies x = y.For instance, non-strict inequality (≤) on Z is antisymmetric.2.3.6. Partial Orders. A partial order, or simply, an order on aset A is a binary relation “4” on A with the following properties:1. Reflexive: for all x ∈ A, x 4 x.2. Antisymmetric: (x 4 y) ∧ (y 4 x) ⇒ x = y.3. Transitive: (x 4 y) ∧ (y 4 z) ⇒ x 4 z.Examples:1. The non-strict inequality (≤) in Z.2.Relation of divisibility on Z+: a|b ⇔ ∃t, b = at.2.3. RELATIONS 353. Set inclusion (⊆) on P(A) (the collection of subsets of a givenset A).Exercise: prove that the aforementioned relations are in fact partialorders. As an example we prove that integer divisibility is a partialorder:1. Reflexive: a = a 1 ⇒ a|a.2. Antisymmetric: a|b ⇒ b =at for some t and b|a ⇒ a = bt0forsome t0. Hence a = att0, which implies tt0= 1 ⇒ t0= t−1. Theonly invertible positive integer is 1, so t = t0= 1 ⇒ a = b.3. Transitive: a|b and b|c implies b = at for some t and c = bt0forsome t0, hence c = att0, i.e., a|c.Question: is thestrict inequality (<) a partial order on Z?Two elements a, b ∈ A are said to be comparable if either x 4 yor y 4 x, otherwise they are said tobe non comparable. The orderiscalled total or linear when every pair of elements x, y ∈ A are com-parable. For instance(Z, ≤) is totally ordered, but (Z+, |), where “|”represents integer divisibility, is not. A totally ordered subset of a par-tially ordered set is called a chain; forinstance the set {1, 2, 4, 8, 16, . . . }is a chainin (Z+, |).2.3.7. Hasse diagrams. A Hasse diagram is a graphical represen-tation of a partially ordered set in which each element is representedby a dot (node or vertex of the diagram). Its immediate successors areplaced above the node and connected to it by straight line segments. Asan example, figure 2.16 represents the Hasse diagram for the relationof divisibility on {1, 2, 3, 4, 5, 6, 7, 8, 9}.Question: How does the Hasse diagram look for a totally orderedset?2.3.8. Equivalence Relations. An equivalence relation on a setA is a binary relation “∼” on A with the following properties:1. Reflexive: for all x∈ A, x ∼ x.2. Symmetric: x ∼ y ⇒ y ∼ x.3. Transitive: (x ∼ y) ∧ (y ∼ z) ⇒ x ∼ z.2.3. RELATIONS 36148627935Figure 2.16. Hasse diagram for divisibility.For instance, on Z, the equality (=) is an equivalence relation.Another example, also on Z, is the following: x ≡ y (mod 2) (“x iscongruent to y modulo 2”) iff x−y is even. For instance, 6 ≡ 2 (mod 2)because 6 −2 = 4 is even, but …