Of the 4 properties (transitivity, anti-symmetry, symmetry, and reflexivity) that a relation could hold, which two are not possible?

876 Views Asked by At

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.

2

There are 2 best solutions below

8
On

** Wrong answer (sorry) ** The relation $R = \emptyset$ on the set $\emptyset$ has all 16 configurations of those properties. So none of them are contradictory.

0
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$