I'm having trouble developing my intuition about the need for a particular form of proof that Halmos presents in Naive Set Theory.
The theorem is on page 53 in the Arithmetic section is about the natural numbers:
In other words, if $n \in \omega$ then $n$ is not equivalent to a proper subset of $n$.
I'll present my attempt at a proof, and then Halmos's more detailed proof. My question is:
what error have I made in my proof? What assumptions have I made that are not allowed, and that require the Halmos version?
My Attempt
The theorem's truth seems like an obvious consequence of the definition of equivalence and an earlier theorem about the natural numbers:
Every proper subset of a natural number $n$ is equivalent to some smaller natural number (i.e., to some element of n).
It seems trivial to state that if $n$ were equivalent to a proper subset of $n$, then because of this latter theorem it would also be equivalent to a smaller $m$, which is not possible because there are strictly fewer elements in that smaller $m$ ($n \cap m\neq \emptyset$)
Side note – equivalence is defined on page 53:
Two sets $E$ and $F$ are called equivalent, in symbols $E \sim F$, if there exists a one-to-one-correspondence between them.
Halmos's Proof
Best Answer
You're right that you can deduce that if $n$ were equivalent to a proper subset of $n$ then it must be equivalent to some smaller $m\in n$.
The mistake in your argument is the next step: "which is not possible because there are strictly fewer elements in that smaller $m$". Why does that mean it's not possible? What do you mean by 'strictly fewer' anyway? Presumably you mean that "the cardinality of $m$ is less than or equal to the cardinality of $n$ and not the same as the cardinality of $m$".
...But showing that the cardinality of $m$ is not the same as the cardinality of $n$ is exactly what you're trying to prove. We're working with a precise notion of 'more/fewer elements than' here, which is precisely the point of the formalisation that Halmos is working with.
It seems obvious to say that $m$ is a smaller number than $n$, therefore it can't be the same size as $n$...but we have to use something quite special about the natural numbers here, because think about what fails with the argument "the even numbers are a strict subset of all the natural numbers, therefore they can't have the same size as them".