Show that the relation \"A has the same cardinality as B\" is an equivalence rel

Question

Show that the relation "A has the same cardinality as B" is an equivalence relation.

I don't even know where to begin with this question.

Explanation / Answer

To show something is an equiv relation you need to show it is reflexive, symmetric, and transitive. Recall A has the same cardinality as B iff there exists a bijection between the two sets. proof: Let x,y,z be arbitrary sets. 1) Reflexive We need to show x~x [ x is related to x] This is obvious, of course we can find a bijection from x to itself, namely the identity function. 2) Symmetric Given x~y we need to show y~x This is again pretty easy. x~y mean x has the same cardinality as y which means there is a bijection f: x --> y. Then f^(-1) is a bijection from y to x so y~x. 3) Transitive Given x~y and y~z we need to show x~z Since x~y we know we can find a bijection f from x to y. Similarly we can find a bijection g from y to z. Then the composite function (g o f) is a bijection from x to z. Hence x~z and the proof is complete. Hope this helps, write back if you are still confused.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.