There are sixteen combinations of these four properties on relations, and I believe one of the impossible combinations is Reflexive, Symmetric, Not Anti-symmetric, and Not transitive. However, I am having trouble finding contradictions in the other fifteen combinations.
Of the 4 properties (transitivity, anti-symmetry, symmetry, and reflexivity) that a relation could hold, which two are not possible?
876 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail AtThere are 2 best solutions below
On
Here are (minimal?) example sets and relations for all fourteen possible combinations of the properties; the zeroes and ones are a short for whether (in this order) reflexivity, symmetry, anti-symmetry, transitivity hold.
0000: $X=\{1,2,3\}$, $R=\{(1,2), (2,3), (3,2)\}$
0001: $X=\{1,2,3\}$, $R=\{(1,2), (2,3), (3,2), (1,3), (2,2), (3,3)\}$
0010: $X=\{1,2,3\}$, $R = \{ (1,2), (2,3) \}$
0011: $X=\{1,2\}$, $R = \{ (1,2) \}$
0100: $X=\{1,2\}$, $R = \{ (1,2), (2,1) \}$
0101: $X=\{1,2,3\}$, $R = \{ (1,2), (2,1), (1,1), (2,2) \}$
0110: Impossible because symmetry and antisymmetry imply transitivity: Assume $aRb$ and $bRc$. Then $cRb$ by symmetry. Then $b=c$ by anti-symmetry and hence $aRc$.
0111: $X=\{1\}$, $R=\emptyset$
1000: $X=\{1,2,3\}$, $R = \{ (1,1), (2,2), (3,3), (1,2), (2,3), (2,1) \}$
1001: $X=\{1,2,3\}$, $R = \{ (1,1), (2,2), (3,3), (1,2), (2,3), (3,2), (1,3) \}$
1010: $X=\{1,2,3\}$, $R = \{ (1,1), (2,2), (3,3), (1,2), (2,3) \}$
1011: $X=\{1,2\}$, $R = \{ (1,1),(2,2), (1,2) \}$
1100: $X=\{1,2,3\}$, $R = \{ (1,1), (2,2), (3,3), (1,2), (2,1), (2,3), (3,2) \}$
1101: $X=\{1,2\}$, $R = \{ (1,1), (2,2), (1,2), (2,1) \}$
1110: Impossible, see 0110
1111: $X=R=\emptyset$
** Wrong answer (sorry) ** The relation $R = \emptyset$ on the set $\emptyset$ has all 16 configurations of those properties. So none of them are contradictory.