Types of Relations

• Antisymmetric
• Symmetric
• Reflexive
• Transitive

Theorem 1.3

Let R be an equivalence relation on a set S. Then:

Solution:

• [(a)] Since 0 does not divide 0, therefore R is not re?exive.
• [(b)] 2 divides 4 so 2 R 4. But 4 does not divide 2, so 4 R 2. Thus, R is not symmetric.
• [(c)] To see that R is transitive, let a, b, c be integers. Suppose that \(a R b\) and \(b R c\). Thus, a divides b and b divides c so there exist integers k and l such that b = ak and c = bl. This gives c = bl = (ak)l = a(kl). Therefore, a divides c so a R c

Anti-Symmetfric Relations

We say that a relation R on a set S is anti-symmetric if for all x, y 2 S such that xRy and yRx, we have \(x = y\).

Thus R is anti-symmetric if and only if the relationship digraph of R has no directed cycles of length two.

Transitive Relations

Transitive relations are binary relations defined on a set such that if the first element is related to the second element, and the second element is related to the third element of the set, then the first element must be related to the third element. For example, if for three elements a, b, c in set A, if a = b and b = c, then a = c.

PArtial Order

A partial order relation is a homogeneous relation that is transitive and antisymmetric. There are two common sub-definitions for a partial order relation, for reflexive and irreflexive partial order relations, also called “non-strict” and “strict” respectively.

Question 1

Given a flock of chickens, between any two chickens one of them is dominant. A relation, R, is defined between chicken x and chicken y as xRy if x is dominant over y. This gives what is known as a pecking order to the flock. Home Farm has 5 chickens: Amy, Beth, Carol, Daisy and Eve, with the following relations:

• Amy is dominant over Beth and Carol
• Beth is dominant over Eve and Carol
• Carol is dominant over Eve and Daisy
• Daisy is dominant over Eve, Amy and Beth
• Eve is dominant over Amy.

Suppose \(A = \{1,2,3,4\}\). Consider the following relation in A

\[ \{ (1,1),(2,2),(2,3),(3,2),(4,2),(4,4)\} \]

Draw the direct graph of \(A\). Based on the Digraph of \(A\) discuss whether or not a relation that could be depicted by the digraph could be described as the following, justifying your answer.

1. Symmetric
2. Reflexive
3. Transitive
4. Antisymmetric

---

• Let S be a set and R be a relation on S. Explain what it means to say that R is

1. reflexive,
2. symmetric,
3. transitive,
4. anti-symmetric,
5. an equivalence relation,
6. a partial order,
7. an order.

Question 1

Determine which of the following relations $ x R y$ are reflexive, transitive, symmetric, or antisymmetric on the following - there may be more than one characteristic.

1. \(x = y\)
2. \(x < y\)
3. \(x^2 = y^2\)
4. \(x \geq y\)

---

Question 2

Given a flock of chickens, between any two chickens one of them is dominant. A relation, R, is defined between chicken x and chicken y as xRy if x is dominant over y. This gives what is known as a pecking order to the flock. Home Farm has 5 chickens: Amy, Beth, Carol, Daisy and Eve, with the following relations:

• Amy is dominant over Beth and Carol
• Beth is dominant over Eve and Carol
• Carol is dominant over Eve and Daisy
• Daisy is dominant over Eve, Amy and Beth
• Eve is dominant over Amy.

Question 3

For \(a, b \in Z\) define a R b to mean that a divides b.

1. State whether or not R is reflexive.
2. State whether or not R is symmetric.
3. State whether or not R is transitive.

% Solution: % % % a. Since 0 does not divide 0, therefore R is not reflexive. % b. 2 divides 4 so 2 R 4. But 4 does not divide 2, so 4 R 2. Thus, R is not symmetric. % c. To see that R is transitive, let a, b, c be integers. Suppose that a R b and b R c. Thus, % a divides b and b divides c so there exist integers k and l such that b = ak and c = bl. This % gives c = bl = (ak)l = a(kl). Therefore, a divides c so a R c %

Question 4

Given the set \(S =\{g,e,r,b,i,l\}\).

1. Describe how each subset of \(S\) can be represented by using a 6 digit binary string
2. Write down the string corresponding to the subset \(\{g,r,l\}\) and the subset corresponding to the string 010101.
3. What is the total number of subsets of S?

Example

• Let \(A = \{2, 3, 4, 6\}\) and \(B = \{4, 6, 9\}\)
• Let R be the relation from A to B defined by if \(x\) divides \(y\) exactly.