# Intuition about a proof that no natural number is equivalent to a proper subset of itself

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

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".