1
$\begingroup$

Given a finite set S, let the relation R = {(S1, S2) | |S1| < |S2|, S1, S2 ⊆ S}. Show whether or not R is reflexive, symmetric, antisymmetric or transitive.
I'm shaky on how to approach this problem. Any help would be greatly appreciated.
I think that it's antisymmetric only.
Suppose S = {1, 2, 3, 4, 5}. Let S1 = {1, 2} and S2 = {3, 4, 5}. S1 and S2 are subsets of S, and |S1| < |S2|.
Then R = {(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5)}.
R is not reflexive because S1 will never equal S2 and a reflexive relation must act on a set, not two different sets.
R is clearly not symmetric, nor is it transitive.

$\endgroup$
  • $\begingroup$ "Then R = {(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5)}." No. The elements in $R$ are pairs of subsets, not of numbers. $\endgroup$ – amsmath Apr 19 at 3:10
  • $\begingroup$ For example, if $S = \{1,2\}$, then $R = \{(\emptyset,\{1\}),\,(\emptyset,\{2\}),\,(\emptyset,\{1,2\}),\,(\{1\},\{1,2\}),\,(\{2\},\{1,2\})\}$. $\endgroup$ – amsmath Apr 19 at 3:13
  • 1
    $\begingroup$ Why is it not transitive? If $|S_1|<|S_2|$ and $|S_2|<|S_3|$, then $|S_1|<|S_3|$ since cardinalities are finite. $\endgroup$ – ersh Apr 19 at 3:43
  • $\begingroup$ @amsmath Thank you very much for the clarification! $\endgroup$ – imconfused Apr 20 at 22:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.