Answer to Question #267847 in Discrete Mathematics for Jaishree

Question

For each of these relations on the set {1, 2, 3, 4}, decide

whether it is reflexive, whether it is symmetric, whether

it is antisymmetric, and whether it is transitive.

a) {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)}

b) {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)}

c) {(2, 4), (4, 2)}

d) {(1, 2), (2, 3), (3, 4)}

e) {(1, 1), (2, 2), (3, 3),(4, 4)}

f ) {(1, 3), (1, 4), (2, 3), (2, 4), (3, 1), (3, 4)}

Answer 1

relation R on a set A is reflexive if ∀a∈A, aRa

relation R on a set A is called symmetric if for all a,b∈A it holds that if aRb then bRa

antisymmetric relation R can include both ordered pairs (a,b) and (b,a) if and only if a = b

relation R on a set A is called transitive if for all a,b,c∈A it holds that if aRb and bRc, then aRc

a)

relation R is not reflexive: $(1,1),(4,4)\notin R$

relation R is not symmetric: $(2,4)\isin R,(4,2)\notin R$

relation R is not antisymmetric: $(2,3),(3,2)\isin R$

relation R is transitive: $(2, 2), (2, 3)\isin R \to (2, 3)\isin R;(2, 2), (2, 4)\isin R \to (2, 4)\isin R;$

$(2, 3), (3, 2)\isin R \to (2, 2)\isin R;(2, 3), (3, 3)\isin R \to (2, 3)\isin R;$

$(2, 3), (3, 4)\isin R \to (2, 4)\isin R;(3, 2), (2, 2)\isin R \to (3, 2)\isin R;$

$(3, 2), (2, 3)\isin R \to (3, 3)\isin R;(3, 2), (2, 4)\isin R \to (3, 4)\isin R;$

$(3, 3), (3, 2)\isin R \to (3, 2)\isin R;(3, 3), (3, 4)\isin R \to (3, 4)\isin R$

b)

relation R is reflexive: $(1, 1), (2,2),(3, 3), (4, 4)\isin R$

relation R is symmetric: $(1,2),(2,1)\isin R$

relation R is not antisymmetric: $(1,2),(2,1)\isin R$

relation R is transitive: $(1, 1), (1, 2)\isin R\to (1, 2)\isin R; (2, 1),(1,2)\isin R\to (2, 2)\isin R;$

$(1, 2),(2,1)\isin R\to (1, 1)\isin R;(1, 2),(2,2)\isin R\to (1, 2)\isin R;$

$(2, 2),(2,1)\isin R\to (2, 1)\isin R$

c)

relation R is not reflexive: $(1,1)\notin R$

relation R is symmetric: $(2, 4), (4, 2) \isin R$

relation R is not antisymmetric: $(2, 4), (4, 2) \isin R$

relation R is not transitive: $(2,4),(4,2)\isin R, (2,2)\notin R$

d)

relation R is not reflexive: $(1,1)\notin R$

relation R is not symmetric: $(1,2)\isin R,(2,1)\notin R$

relation R is antisymmetric: $(2, 1), (3, 2), (4, 3)\notin R$

relation R is not transitive: $(1, 2), (2, 3)\isin R,(1,3)\notin R$

e)

relation R is reflexive: $(1, 1), (2,2),(3, 3), (4, 4)\isin R$

relation R is symmetric: $(1, 1), (2,2),(3, 3), (4, 4)\isin R$

relation R is antisymmetric: $(1, 1), (2,2),(3, 3), (4, 4)\isin R$

relation R is transitive: we can satisfy (a, b) and (b, c) when a = b = c. 

f)

relation R is not reflexive: $(1,1)\notin R$

relation R is not symmetric: $(1,4)\isin R,(4,1)\notin R$

relation R is not antisymmetric: $(1,3),(3,1)\isin R$

relation R is not transitive: $(1, 3), (3, 1)\isin R,(1,1)\notin R$