I am working through Rudin's POMA and in Chapter 2 on Basic Topology he gives the following definition of one-to-one correspondence:
If there exists a 1-1 mapping of $A$ onto $B$, we say that $A$ and $B$ can be put in 1-1 correspondence, or that $A$ and $B$ have the same cardinal number, or, briefly, that $A$ and $B$ are equivalent, and we write $A\sim B$. This relation clearly has the following properties:
- It is reflexive: $A\sim A$.
- It is symmetric: If $A\sim B$, then $B\sim A$.
- It is transitive: If $A\sim B$ and $B\sim C$, then $A\sim C$.
Rudin later goes on to say, "For two finite sets $A$ and $B$, we evidently have $A\sim B$ if and only if $A$ and $B$ contain the same number of elements."
Rudin never defines what cardinal or ordinal numbers are (even though he says $A\sim B$ for finite sets means $A$ and $B$ have the same cardinal number...he never defines a cardinal number) and does not go into set theory in any real depth.
Curiosity: I was thinking about Rudin's statement about finite sets and was wondering how one might prove that. I read an alleged proof in Raffi Grinberg's Real Analysis Lifesaver book (a book I really do not like to be honest), and I'm really questioning whether or not it is accurate. It is reproduced below:
Raffi's proof: Let $A$ and $B$ be finite sets. We claim that $A\sim B$ if and only if $A$ and $B$ have the same number of elements.
If $A\sim B$, then there exists a function that maps every element of $A$ (since $f$ is a well-defined function) to at most one element of $B$ (since $f$ is injective), and every element of $B$ is mapped to by some element of $A$ (since $f$ is surjective). So for every element of $A$ there is a corresponding element of $B$, and all elements of $B$ are covered by this correspondence, so $A$ and $B$ must have the same number of elements.
If $A$ and $B$ have the same number $n$ of elements, then we can write the sets as $A=\{a_1,a_2,\ldots,a_n\}$ and $B=\{b_1,b_2,\ldots,b_n\}$. Let $f\colon A\to B$ be defined as $f\colon a_i\mapsto b_i$, for every $1\leq i\leq n$. Then $f$ is a one-to-one, onto function, so $f$ is a bijection. We have found a bijection $A\to B$, so $A\sim B$.
Question: Is this proof really correct? It seems hand-wavy at best, especially the first part (the forward direction)---the finiteness of $A$ and $B$ do not seem to matter. The same argument would seem to work in the case of infinite sets $\mathbb N$ and $\mathbb Z$, where $\mathbb N\sim\mathbb Z$, but we do not think of these sets as having the same number of elements in the manner argued above (do we?). More concerning, since Grinberg admits in the introduction/preface that his book is basically based on Rudin's, I wonder how he proposes to prove something about cardinal numbers (i.e., that equivalent finite sets have the same cardinal number) when they have not actually been defined (in his book or in Rudin's).
I was reading in Enderton's Elements of Set Theory that, "Now it turns out that there is no way of defining $\operatorname{card} A$ that is really simple" (p. 136). He later gives the definition: "For any set $A$, define the cardinal number of $A$ ($\operatorname{card} A$) to be the least ordinal equinumerous to $A$" (p. 197).
Ultimately, there seems to be a fair amount going on here (to a novice like me at least), but I did not find Grinberg's proof very convincing. Am I wrong to feel that way? Is there an easy fix? Any thoughts?