Proof verification: Let U be some universal set. Define relation on P(U) by A ~ B iff A and B have same cardinality....

[Steven G]

Hi,
I did a proof that my mathematician friend said was wrong. He claims that I should show bijections. I am sure that he is correct but I do not see why my trivial proof is wrong.

The statement of the theorem along with my proof is below.

---

Theorem 2: Let U be some universal set. Define a relation on $$\mathcal{P}(U)$$ by $$A\, \sim\, B$$ iff $$A$$ and $$B$$ have the same cardinality; that is, iff there is a bijection $$f\, :\, A\, \rightarrow\, B.$$ Then $$\sim$$ is an equivalence relation on $$\mathcal{P}(U).$$

---

Proof:

Reflexive: $$A\, \sim\, A$$ since $$A$$ and $$A$$ have the same cardinality.

Symmetric: Suppose $$A\, \sim\, B.$$ Then $$A$$ and $$B$$ have the same cardinality, so $$B$$ and $$A$$ have the same cardinality. Then $$B\, \sim\, A.$$
Transitive: Suppose $$A\, \sim\, B$$ and $$B\, \sim\, C.$$ Then $$A$$ and $$B$$ have the same cardinality, and $$B$$ and $$C$$ have the same cardinality. Since a set has only one cardinality, it follows that $$A$$ and $$C$$ must have the same cardinality, and $$A\, \sim\, C.$$
Since the relation $$\sim$$ is reflexive, symmetric, and transitive, it is an equivalence relation.

---

Thanks for your time!

 

[pka]

Hi,
I did a proof that my mathematician friend set was wrong. He claims that I should show bijections. I am sure that he is correct but I do not see why my trivial proof is wrong.

The statement of the theorem along with my proof is below.

---

Theorem 2: Let U be some universal set. Define a relation on $$\mathcal{P}(U)$$ by $$A\, \sim\, B$$ iff $$A$$ and $$B$$ have the same cardinality; that is, iff there is a bijection $$f\, :\, A\, \rightarrow\, B.$$ Then $$\sim$$ is an equivalence relation on $$\mathcal{P}(U).$$

---

Proof:

Reflexive: $$A\, \sim\, A$$ since $$A$$ and $$A$$ have the same cardinality.

Symmetric: Suppose $$A\, \sim\, B.$$ Then $$A$$ and $$B$$ have the same cardinality, so $$B$$ and $$A$$ have the same cardinality. Then $$B\, \sim\, A.$$
Transitive: Suppose $$A\, \sim\, B$$ and $$B\, \sim\, C.$$ Then $$A$$ and $$B$$ have the same cardinality, and $$B$$ and $$C$$ have the same cardinality. Since a set has only one cardinality, it follows that $$A$$ and $$C$$ must have the same cardinality, and $$A\, \sim\, C.$$
Since the relation $$\sim$$ is reflexive, symmetric, and transitive, it is an equivalence relation.

---

Thanks for your time!

To be fair to your friend, if it were in my class I would prefer use of functions. Noting that the composition two bijections is bijection.
$\displaystyle A\overset f \longleftrightarrow B\overset g \longleftrightarrow C \Leftrightarrow A\overset {g \circ f} \longleftrightarrow C$
Also to be honest, I am guilty of saying "any relation meaning 'same as' is an equivalence relation."

 

[Dr.Peterson]

I'd say it depends on your context. Each of your three statements is a theorem about "same cardinality". If you have access to those theorems (already proved), then what you said is fine. If not, you need to prove them using the definition (which, of course, will not be hard).

 

[Steven G]

Also to be honest, I am guilty of saying "any relation meaning 'same as' is an equivalence relation."

Yep!

 

[Steven G]

I'd say it depends on your context. Each of your three statements is a theorem about "same cardinality". If you have access to those theorems (already proved), then what you said is fine. If not, you need to prove them using the definition (which, of course, will not be hard).

What would the theorem be that would state that set A and set A have the same cardinality? I would think this is true even if a set can have multiple cardinalities.
What would the theorem be that would state that if set A and set B have the same cardinality, then set B and set A have the same cardinality?

The cardinality of a given set is always the same, it is not a function of time!

 

[Dr.Peterson]

Yes, the theorems (especially "any set has the same cardinality as itself", but the others as well) are rather trivial, both to state and the prove; but as I said, if in your context they have not yet been proved, you have to prove them. In a formal proof you can't just say "this is obvious", even if it is.

In a more informal context among mathematicians, you could just say, "We all know this is true, right?" and not bother with the details. That's why I asked about context. And your friend may be seeing the context differently than you do.

 

[ksdhart2]

What would the theorem be that would state that if set A and set B have the same cardinality, then set B and set A have the same cardinality?

My first thought here was to say that, if we already have a theorem under our belt that establishes that a set can have only one cardinality, that it would follow automatically that $\displaystyle |A| = |B| \implies |B| = |A|$ and $\displaystyle (|A| = |B| \wedge |B| = |C|) \implies |A| = |C|$.

However, the more I think about it, the less sure I am. The above definitely holds for any finite set, since the cardinality of any finite set is a real number (oh boy! another subproof?) and we know the real numbers have the symmetric and transitive properties... but what about infinite sets, whose cardinalities aren't real numbers? Do the Aleph numbers have the symmetric and/or transitive property?

 

[Dr.Peterson]

Do the Aleph numbers have the symmetric and/or transitive property?

Completing the proof (using bijections) will show that they do! But we can't just assume it.

 

[pka]

What would the theorem be that would state that set A and set A have the same cardinality? I would think this is true even if a set can have multiple cardinalities. What would the theorem be that would state that if set A and set B have the same cardinality, then set B and set A have the same cardinality? The cardinality of a given set is always the same, it is not a function of time!

Lets cut to the chase. A set is infinite if and only it is equipotent to a proper subset of itself. Think of the positive integers and the even positive integers. If anyone is serious about these questions then here is one to try.
If each of $\displaystyle A\:\&\:B$ is a set then there is a injection $\displaystyle F:A\to B$ if and only if there is a sujection $\displaystyle G:B\to A$.
If one works through that exercise, one gains an appreciation of functions to the concept equipotency of sets.
NOTATION: $\displaystyle \|A\|$ is the cardinally of the set $\displaystyle A$. Using that notation we get.
If $\displaystyle F:A\to B$ is an injection then $\displaystyle \|A\|\le\|B\|$.
AND If $\displaystyle G:B\to A$ is an surjection then $\displaystyle \|B\|\le\|A\|$.