Examining properties of the relation $R = \{(S_1,S_2) \mid |S_1| < |S_2|, S_1,S_2 \subseteq S\}$ where $S$ is finite

Question

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.

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.