The Problem: Given a finite set $S$, let the relation $$R = \{(S_1, S_2) \mid |S_1| < |S_2|, S_1, S_2 ⊆ 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 $S_1 = \{1, 2\}$ and $S_2 = \{3, 4, 5\}$. $S_1$ and $S_2$ are subsets of $S$, and $|S_1| < |S_2|$.

Then $R = \{(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5)\}.$

$R$ is not reflexive because $S_1$ will never equal $S_2$ and a reflexive relation must act on a set, not two different sets.

$R$ is clearly not symmetric, nor is it transitive.

  • $\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, 2019 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, 2019 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, 2019 at 3:43
  • $\begingroup$ @amsmath Thank you very much for the clarification! $\endgroup$
    – imconfused
    Apr 20, 2019 at 22:26

1 Answer 1


Some comments on your work:

  • You're correct on reflexivity: $(S_1,S_1) \in R$ iff $|S_1| < |S_1|$, which is nonsense. For instance, if $S = \{1,2,3\}$ and you have $A = \{1\}$, $|A| = 1 \not < 1 = |A|$, so $(A,A) \not \in R$.

  • You're correct on symmetry. For instance, take $S = \{1,2,3\}$, then it holds that $(A,B) =(\{1\},\{1,2\}) \in R$ since $|A| = 1 < 2 = |B|$. However, the reverse isn't true, since $|B| = 2 \not < 1 = |A|$, so $(B,A) \not \in R$, and thus no symmetry.

  • You're correct on anti-symmetry, but probably for the wrong reasons since it's a bit nuanced and subtle. If $(A,B),(B,A) \in R$, then $|A| < |B|$ and $|B|<|A|$. Thus there never exists such a double pair in $R$, so we have anti-symmetry vacuously.

  • You're incorrect on transitivity. If $(A,B),(B,C) \in R$, then $|A|<|B|$ and $|B|<|C|$. Since $<$ is transitive on cardinals, it holds that $|A|<|C|$ and thus $(A,C) \in R$.

  • Note, however, the elements of $R$ are ordered pairs whose components are sets, not numbers. Your example of $R$ has ordered pairs of the form $(|A|,|B|)$ as opposed to $(A,B)$.

  • In general, for work like this, it might be best to avoid claiming things "clearly" hold, when they tie directly into the things you want to prove. For adjacent results, it might be okay, but for situations like these or posts on MSE, it obfuscates what you're actually thinking and what you know, so it makes it harder to help you.

...granted, this question is quite old, so I imagine you don't need help now. But hopefully this helps someone in the future, and, if nothing else, gets this question out of the unanswered queue.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .