In Paul R. Halmos's book "Naive Set Theory," in the latter part of section 13 related to arithmetic, there is a definition for a finite set: a set is finite if there is a bijection between it and a natural number $n$. It is proven in the same section that every natural number $n$ cannot be bijected with any proper subset of it. Additionally, it is demonstrated, concerning the set of natural numbers ($\omega$), that there exists a proper subset that bijects with it; in other words, a part of it equals the whole. This led me to intuitively infer that every infinite set must have a proper subset that bijects with it; otherwise, it is a finite set. Please, is there a proof for this assertion?
Set Theory – Does an Infinite Set Always Have a Proper Subset Equal in Cardinality to Itself?
set-theory
Related Solutions
I'm going to give this a go - apologies in advance if there are errors. I assume you're relatively fluent with ordinals (i.e. thinking of numbers as sets, etc.)
Let $A$ be the set in question. If $n$ is any natural number then by assumption $A$ is not in bijection with $n$; the Law of Trichotomy (which requires Choice, I believe) then implies that either $A<n$ or $n<A$.
If $A<n$ there is an injection of $A$ into $n$, which is then a bijection onto its image - but its image, being a subset of $n$, is in bijection with some (smaller) natural number, and this contradicts the assumption on $A$.
Therefore $n<A$ for every natural number $n$; in other words we have injections $n \hookrightarrow A$ for all $n \in \mathbb{N}$. Furthermore we can choose these injections so that they commute with the natural inclusions $n \hookrightarrow m$ for $n<m$.
Now define our map $f: \mathbb{N} \rightarrow A$ by setting $f \vert_n$ equal to the chosen injection $n \hookrightarrow A$, for all natural numbers $n \subseteq \mathbb{N}$. This is well-defined because of the commutativity assumption in the previous paragraph.
Finally, $f$ is an injection: for if $a,b \in \mathbb{N}$ with $f(a) = f(b)$, then we can choose $n$ bigger than both $a$ and $b$, and then: \begin{equation*} f \vert_n(a) = f(a) = f(b) f \vert_n(b) \end{equation*} And therefore $a=b$ by injectivity of $f\vert_n$.
The issue is that induction only tells you that something is true for every finite integer.
For example, by induction we can prove that every natural number $n$ has exactly $n$ predecessors ($0$ is a natural number). Does that mean that there exists a natural number with infinitely many predecessors? No. It does not.
Similarly here. If $A$ is an infinite set, without the axiom of choice we can prove that for every $n$ there is a subset of $A$ of size $n$. But can we prove there exists a subset equipotent with $\Bbb N$ itself? No. That requires us more. That requires that the choices we made during the inductive proof were coherent with one another, which essentially tells us that there is some sort of choice function that we can work with.
And indeed, without the axiom of choice, it is consistent that there are infinite sets without countably infinite subsets. These are called Dedekind-finite sets.
Perhaps the following elaboration is going to clarify this issue. Let's look at what the inductive proof really does.
You start with the empty set, and you have $A$ to choose from. That gives you $|A|$ many choices for a first element in your sequence. Suppose that you managed to get through $n$ choices, that gives you $|A|-n$ many choices to continue, and that's fine, since $|A|$ is not a finite integer, we can always make at least one choice and continue the construction.
But what are we really constructing? It's a tree of options. We start with the root, which is the empty sequence. Then at each step, we have splitting according to our options. In this case, however, there are infinitely many splittings at each step.
The inductive construction simply tells us that we constructed a tree without maximal points. The axiom of choice tells us that this tree has a branch, which in turn can be translated into a countably infinite subset. But the existence of a branch relies heavily on the axiom of choice. Why would you choose the first element to be one and not another? How about the second element? There is no canonical preference to make here, in the arbitrary case.
So what happens is that without choice, you might end up with a tree that has no maximal nodes, but no infinite branches either.
(In Mitchell Spector's answer he discusses inductive definitions, in that case, there is a function which chooses "the next step", so the tree is in fact a unique branch, and everything is fine. But in the proof you suggest, there is no such function, you appeal to choosing arbitrary elements at each step.)
Best Answer
I assume that your definition of an infinite set is that it's not in a bijection with a natural number.
Let $X$ be your infinite set. Let $F$ be a mapping from nonempty subsets of $X$ to elements of that subset, i.e. $F(Y) \in Y$.
By induction, define the sequence $a_n$: $$a_n = F(X - \{a_0, \ldots, a_{n-1}\})$$
And now define $g: X \to X$:
$g(a_n) = a_{n+1}$
$g(x) = x$ for other $x$.
$g$ is a bijection from $X$ to a proper subset of itself, namely $X - \{a_0\}$