For each of the following statements about relations on a set A, where |A|  n,

Question

For each of the following statements about relations on a set A, where |A|  n, determine whether the statement is true or false. If it is false, give a counterexample. a) If  is a relation on A and || ? n, then  is reflexive. b) If 1, 2 are relations on A and 2 ? 1, then 1 reflexive (symmetric, antisymmetric, transitive) ?2 reflexive (symmetric, antisymmetric, transitive). c) If 1, 2 are relations on A and 2 ? 1, then 2 reflexive (symmetric, antisymmetric, transitive) ?1 reflexive (symmetric, antisymmetric, transitive)

Explanation / Answer

a) If R is a relation on A and |R| = n, then R is reflexive. False. b) If R1, R2 are relations on A and R2 , R1, then R1 is reflexive (symmetric, antisymmetric, transitive) then R2 is reflexive (symmetric, antisymmetric, transitive). Reflexive – True Since every element in R1 is in R2. Symmetric – False Consider A = {1,2,3} R1 = {(1,2),(2,1)} R2 = {(1,2),(2,1),(1,3)} Antisymmetric – False Consider A = {1,2,3} R1 = {(1,1),(2,2)} R2 = {(1,1),(2,2),(1,3), (3,1)} Transitive – False Consider A = {1,2,3,4} R1 = {(1,2),(2,3),(1,3)} R2 = {(1,2),(2,3), (1,3),(1,4),(4,2)} c) Reflexive – False Consider A = {1,2,3} R2 = {(1,1),(2,2),(3,3)} R1 = {(1,1),(2,2)} Symmetric – False Consider A = {1,2,3} R2 = {(1,2),(2,1)} R1 = {(1,2)} Antisymmetric – True Transitive – False Consider A = {1,2,3} R2 = {(1,2),(2,3),(1,3)} R1 = {(1,2),(2,3)} d) |R| = n² must be true since the most elements that can be in a relation on A is n² which would be the cross product R ? R. Since R is an equivalence relation, one of the requirements is that it must be reflexive. This means there will be at least n elements in the relation. Therefore n = |R| = n².

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.