Here's what I've tried so far.

Let $A$ be a set and suppose $|A| < |\mathbb{N}|$. By the definition of less than for cardinalities (I'm reading out of Hrbacek's Introduction to Set Theory), this means that there exists a one-to-one function $f$ from $A$ onto a subset of $\mathbb{N}$, but there does not exist a one-to-one function from $A$ onto $\mathbb{N}$ itself.

In the book, finite is defined as in bijection with a natural number $n \in \mathbb{N}$. The natural numbers are defined in a weird way:

$$0 = \varnothing$$

$$1 = \{0\} = \{\varnothing\}$$

$$2 = \{0,1\}$$

$$3 = \{0,1,2\}$$

... and so on ad infinitum.

My intuition is this: I want to show that $A$ is in one-to-one correspondence with a finite subset of $\mathbb{N}$, and once I've done this it's trivial to show that $A$ is finite itself (the composition of bijections is a bijection, so $A$ is in bijection with some $n \in \mathbb{N}$, and we're done). I just have no idea how to find the correspondence with a finite subset of $\mathbb{N}$.

If I show that any infinite (infinite is simply defined as not finite) subset of $\mathbb{N}$ is in bijection with $\mathbb{N}$ itself, this would work ...

  • $\begingroup$ This has been asked before. What you want to show is that for any infinite set $A$, $\aleph_0\leqslant \# A$. This can be proven using the axiom of choice. $\endgroup$ – Pedro Tamaroff Dec 17 '14 at 2:33
  • $\begingroup$ @PedroTamaroff what is $\#A$? EDIT: Are you sure this requires the Axiom of Choice? $\endgroup$ – Vincent Luo Dec 17 '14 at 2:36
  • $\begingroup$ Consider the following argument: since $A\neq \varnothing$, there is $x_0\in A$. Since $A$ is infinite, there is $x_1\in A\smallsetminus x_0$. Since $A$ is infinite, there is $x_2\in A\smallsetminus \{x_0,x_1\}$. Since $A$ is infinite, $\ldots$. Then $x_i\longleftrightarrow i$ is a bijection, i.e. there is a subset $A'\subseteq A$ equipotent with $\Bbb N$. $\endgroup$ – Pedro Tamaroff Dec 17 '14 at 2:37
  • $\begingroup$ Then there is a bijection between $A$ and $\mathbb{N}$ via the function that takes $\{x_0, x_1 ... x_n\}$ to $n$? $\endgroup$ – Vincent Luo Dec 17 '14 at 2:39
  • $\begingroup$ @PedroTamaroff Okay I think this works, the recursion part seems a bit non-rigorous but it makes complete intuitive sense to me $\endgroup$ – Vincent Luo Dec 17 '14 at 2:40

Given an infinite set of $A$ we can define an injection from $A$ to $\mathbb N$ by the inclusion mapping. define the injective map from $\mathbb N$ to $A$ where $1$ goes to the minimum element of $\mathbb A$, where $2$ goes to the minimum element of $A\setminus f(1)$ and in general map $n$ to the minimum element of $A\setminus \{f(i)|1\leq i\leq(n-1)\}$.

So if you have an infinite subset of $\mathbb N$ it has the same cardinality as $\mathbb N$

  • $\begingroup$ Oh, I thought I could do that, sorry I haven't taken set theory yet. $\endgroup$ – Jorge Fernández Hidalgo Dec 17 '14 at 2:58
  • $\begingroup$ You can prove that $A$ can be well-ordered. Define the order $\prec$ over $A$ such that $x\prec y$ iff $i(x)<i(y)$, where $i$ is an injection from $A$ to $\Bbb{N}$. $\endgroup$ – Hanul Jeon Dec 17 '14 at 2:58
  • 1
    $\begingroup$ I was just using the order on $\mathbb N$ $\endgroup$ – Jorge Fernández Hidalgo Dec 17 '14 at 2:59
  • $\begingroup$ $A$ is well ordered using the induced order from $\mathbb{N}$. $\endgroup$ – copper.hat Dec 17 '14 at 3:00
  • 1
    $\begingroup$ You could even avoid Cantor-Bernstein by noting that the function mapping $f(n)$ to the minimum of $A\setminus\{f(i)\mid i<n\}$ is a bijection. $\endgroup$ – Asaf Karagila Dec 17 '14 at 5:54

Let $f:A \to \mathbb{N}$ be an injection. Consider the following recursively defined function $g:D\subseteq \mathbb{N} \to A$:

$$ \DeclareMathOperator*{\argmin}{argmin} g(n) = \argmin_{a\in A\setminus\{g(k)|k<n\}}(f(a)) $$

Notice that $g$ is a bijection from its domain of definition $D$ to $A$, so $D$ cannot equal all of $\mathbb{N}$ (since $|A| < |\mathbb{N}|$). Therefore there exists some $n = \min(\mathbb{N}\setminus D)$. Observe that $D = \{0, \ldots, n-1\} = n$. So $g$ is a bijection from $n$ to $A$, so $A$ is finite.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.