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.

So if S = {1,2}

$R = \{(\emptyset,\{1\}),\,(\emptyset,\{2\}),\,(\emptyset,\{1,2\}),\,(\{1\},\{1,2\}),\,(\{2\},\{1,2\})\}$

and going off of this

Reflexive- No because S1 does not equal S2

Symmetric- No because if you swap $(\emptyset,\{2\})$ for example, the relation doesn't hold true

Transitive- No because $\{(\emptyset,\{1\}),\,(\emptyset,\{2\})$ and doesn't have $\{(\{1\},\{2\})$

Anti-Symmetric-No also because it doesn't satisfy aRb and bRa being true, a = b.

I think I've done this correctly, but I dont have a strong grasp on these relations yet.

  • 1
    $\begingroup$ This relation is neither reflexive nor symmetric nor anti-symmetric. This relation is only transitive. $\endgroup$ – Dbchatto67 Apr 21 at 4:48

This relation is only transitive. Because if $(S_1,S_2) \in R$ and $(S_2,S_3) \in R$ then we have $$|S_1| < |S_2|\ \text {and}\ |S_2| < |S_3|.$$ But it follows that $$|S_1| < |S_3|.$$ So $(S_1,S_3) \in R.$

  • $\begingroup$ Alright that makes sense, I see how i messed up! Just to be clear, first off is my set of relations correct? Secondly, is my reasoning for the others being false correct? $\endgroup$ – Brownie Apr 21 at 4:56
  • 1
    $\begingroup$ Your defined relation is correct. Your reasoning for other parts (excluding transitivity) are perfectly fine. For concluding transitivity you cannot take $\{\varnothing, {1} \}, \{\varnothing,{2} \} \in R.$ Because $R$ is not symmetric. $\endgroup$ – Dbchatto67 Apr 21 at 4:58
  • 1
    $\begingroup$ Because $$\{\varnothing ,a \} \in R \not\implies \{a,\varnothing \} \in R.$$ for $a=1,2.$ Hence for transitivity to hold we cannot say that $\{1,2 \} \in R.$ $\endgroup$ – Dbchatto67 Apr 21 at 5:05

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.