Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The wikipedia page on the cardinal numbers says that $\aleph_0$, the cardinality of the set of natural numbers, is the smallest transfinite number. It doesn't provide a proof. Similarly, this page makes the same assertion, again without a proof.

How does one prove there is no smaller transfinite number? Equivalently (I think), why is there no smaller infinite set than the natural numbers?

share|improve this question

6 Answers 6

up vote 12 down vote accepted

This is a consequence of the following theorem:

Suppose that $A$ is a set of integers, then either $A$ is finite, or $|A|=|\Bbb N|$.

Since we define $\aleph_0$ to be the cardinality of $\Bbb N$, this means that every infinite subset of a set of size $\aleph_0$ is itself of size $\aleph_0$, and so there cannot be a smaller infinite cardinal.

Note that the above proves that $\aleph_0$ is a minimal element of the infinite cardinals. There is no smaller. To prove that it is in fact the smallest of the infinite cardinals we need to use some other set theoretical assumptions (e.g. every two cardinals are comparable) which are commonly assumed throughout mathematics nowadays.


The proof of the aforementioned theorem is simple, by the way. Suppose that $A$ is infinite, then the map $a\mapsto |\{a'\in A\mid a'<a\}|$ is a bijection between $A$ and $\Bbb N$. The proof of that is by induction.

share|improve this answer
2  
Curious that you did not mention the key use of the axiom of choice... –  Andres Caicedo Oct 6 '13 at 21:16
1  
@Andres: I thought about it, but I feel that it might cause more damage than help to someone inexperienced with infinite sets. I'm still tempted to make that edit. –  Asaf Karagila Oct 6 '13 at 21:17
    
As a parenthetical remark, at least. –  Andres Caicedo Oct 6 '13 at 21:21
    
When you're right, you're right. :-) –  Asaf Karagila Oct 6 '13 at 21:24
    
I found a related question here. Is the "every two cardinals are comparable" assumption the same as $2^{\aleph_\alpha} = \aleph_{\alpha+1}$? How does it relate to the axiom of choice? Further reading would be as welcome as a concrete answer :-) –  statusfailed Oct 6 '13 at 22:43

This really comes down to definitions. It is not uncommon to define "finite" to mean "a cardinality strictly less than that of $\mathbb N$", in which case what you're looking for is just what the definition says and allows no further proof.

If you want more than that (and what you want is actually a proof from definite axioms and definitions, rather than just an informal argument that it's probably about right), then you need to start by choosing a particular different definition of "finite" to prove things about.

share|improve this answer
4  
I have not seen that "not uncommon" definition in practice anywhere, or in any of a large number of standard sources. –  Andres Caicedo Oct 6 '13 at 21:28
    
@AndresCaicedo: It's usually written with $\omega$ instead of $\mathbb N$, and after having proved that the cardinalities strictly smaller than an initial ordinal are exactly the cardinalities of its elements. –  Henning Makholm Oct 6 '13 at 21:31
2  
No, it is not. Finite means "of the same size as a natural number". One then can prove that this notion has the property you state. Yes, natural numbers are the elements of $\omega$. Yes, membership among ordinals is commonly denoted by $<$. No, this is not the same as what you said, as in this context $n<\omega$ simply means "$n$ is an element of $\omega$", not "$n$ has size strictly smaller than $\omega$". –  Andres Caicedo Oct 6 '13 at 21:34

$\Bbb N$ is the union of all finite ordinals $[n]:=\{0,1,2,\dots,n-1\}$.

Hence, if a set $A$ is not finite, then each $[n]$ embeds into it. In particular, we can define embeddings $f_n:[n]\hookrightarrow A$ on top of each other, i.e. satisfying $f_n(k)=f_{n-1}(k)$ for all $k<n-1$. But that altogether (considering $\bigcup_nf_n$) gives an embedding of $\Bbb N$ into $A$, so that $\aleph_0\le |A|$.

share|improve this answer
1  
The part after "Hence," is unclear. –  Asaf Karagila Oct 6 '13 at 21:15

Well a set $M$ is infinite if for every finite subset $U \subsetneq M$ there exists a $x \in M, x\notin U$. Consequently, you will be able to construct a sequence $(x_n)_{n \in \mathbb{N}} $ of distinct elements in $M$. Therefore $|M| \ge \aleph_0 $

share|improve this answer
4  
This is not true as written. Replace $\subsetneq$ with $\subseteq$, and it will be fine now. –  Andres Caicedo Oct 6 '13 at 21:30

One property of cardinals says that if there is an injection $f:A \to B$ then the cardinality of $A$ is less than or equal to the cardinality of $B$. If $B$ is infinite, then you can choose any $b_1 \in B$ and define $f(1) = b_1$, and then choose different $b_2 \in B$ so that $f(2) = b_2$, and so forth and you will get an injection $f:{\mathbb N} \to B$ if $B$ is infinite (because for every $n$, you have infinitely many choices left in $B$ for $f(n)$). So $|B| \geq |{\mathbb N}|$ if $B$ is infinite, thus $| \mathbb{N}|$ is the smallest infinite cardinal.

share|improve this answer

It is proved by Whitehead and Russell in Principia Mathematica ✳124.23. The proof can be summarized like this: every infinite class contains at least $\aleph_0$ terms. It follows that every infinite number is greater or equal to $\aleph_0$

Definition of $\aleph_0$ :

✳122.01 $Prog = 1\rightarrow 1 \cap \hat{R}(D‘R=\overset{\leftarrow}{R_✳}‘B‘R) $ Df

✳123.01 $\aleph_0 = D‘‘Prog$

Which says a set is said to have $\aleph_0$ terms if the set is the domain of a progression. A progression is a one-one relation whose domain consists entirely of the first term's descendants (including the first term).

For example, suppose you are on a sandy beach. You see a row of pebbles. Every pebble is immediately followed by only one pebble; each, except for the first one, is immediately preceded by one pebble, then the total number of pebbles in this row is Cantor's $\aleph_0$. enter image description here

✳123.34 $\vdash: Infin \ ax(x) .\supset. \aleph_0 = NC‘(NC induct ∩ t^3‘x)$

I.e. $\aleph_0 $ is the cardinal number of all inductive numbers.

Relations between $\aleph_0$ and infinite numbers:

Let P stand for a one-one relation "Precedes" whose domain contains its converse domain and whose field can be arranged in generations:

    a  b  c  d  e  f ...

    𐤀  𐤁  𐤂  𐤃  𐤄  𐤅 ...

    Γ  ∆  ∑  ∏  Θ  Ψ ...

Where the first generation consists of terms that are not preceded by other terms. If the first generation of the domain, e.g. {a, 𐤅, Γ} exists and each row is a family that consists of descendants of one of the first terms, then the domain as a whole is a set that has infinite number of terms, and each row, e.g. {a, b, c, d, ...}, has $\aleph_0$ terms.


You can skip the following details unless you are interested:

✳124.23 $\vdash: \mu \in NC_{refl}.≡.\mu ≥ \aleph_0 $

which states that "$\mu$ is a reflexive number" is equivalent to "$\mu$ is greater or equal to $\aleph_0$." The proof is based on ✳124.15


✳124.15 $\vdash: \rho \in Cls_{refl} .≡. \exists!\aleph_0 ∩ Cl‘\rho$

which states that every reflexive class contains one or more subclasses of $\aleph_0$ terms. The proof is based on ✳124.1 and ✳123.192


✳124.1 $\vdash: \rho \in Cls_{refl} .≡. (\exists R). R\in 1\rightarrow 1. Ɑ‘R \subset D‘R. \exists!\overset{→}{B}‘R.\rho=D‘R$

Which states that a reflexive class is the domain of a one-one relation whose first terms exist and whose converse domain is contained by its domain.


✳123.192 $\vdash: R\in 1\rightarrow1.Ɑ‘R\subset D‘R.\supset.\overset{\leftarrow}{R_✳}‘‘\overset{\rightarrow}{B}‘R\subset\aleph_0$

which states that if a one-one relation's converse domain is contained by its domain, then the class of descendants of any of its first term has $\aleph_0$ members. For example, suppose x and y are first terms (having no predecesors) of such a relations, then $\overset{\leftarrow}{R_✳}x$(the descendants of x) and $\overset{\leftarrow}{R_✳}y$(the descendants of y) each has $\aleph_0$ members.


Definitions:

  • A class (or a set) is a collection of terms satisfying some propositional function. Every propositional function determines a class.

  • The number of a class is the class of all classes (of a given type) that are similar to the give class. See ✳100.01.1

  • There are two ways of defining the finite and the infinite. 1. The finite is inductive; the infinite is non-inductive. 2 the finite is non-reflexive; the infinite is reflexive. When multiplicative axiom is assumed, these two definitions coalesce.

  • A class is called reflexive when there is a one-one relation that correlates the class to a proper part of itself. See 124.01

  • A class is called inductive if it can be assembled from an empty class $\Lambda$ by successive unions with some unit class. A number is called inductive if it can be reached from $0$ by successive additions of $1$.

  • A infinite number (reflexive cardinal in PM or transfinite number in Cantor's words) is the number of a reflexive class. see ✳124.021

  • $\mu$ is said to be greater than or equal to $\nu$ when a member class of $\mu$ contains (when raised to the same type) or is similar to a member class of $\nu$. see ✳117.01.05

  • The first terms of a relation is the relation's domain subtracted by its converse domain. Given the relation "precedes," then, among the governors of Tennessee, Mississippi and Arkansas, the first terms are the first governors of these states, namely John Sevier, David Holmes, James S. Conway.

share|improve this answer
3  
It's debatable (to me) whether this actually has any meaning in today's mathematics, since they were using a different foundational theory than ZF(C), and a different concept of cardinal than von Neumann's. –  Ryan Reich Jul 23 at 14:48
    
The beauty of PM is that every step appeals directly to the senses. The theorem I chose can be written out in plain English like this: every infinite class contains at least $\aleph_0$ members. Therefore the cardinality of infinite classes must be greater or equal to $\aleph_0$ –  George Chen Jul 23 at 16:00
2  
We do, but we may not agree what a class is, what infinite is, or what $\aleph_0$ is. This is a foundations question, so I think the particulars of the axiomatic system matter. –  Ryan Reich Jul 23 at 16:44
1  
No, that is not the point. Here is an example: Consider $[0,1)$, and replace $0$ by a copy of the naturals, and all other points by a copy of the integers. ($(\{0\}\times\mathbb N)\cup((0,1)\times\mathbb Z)$ ordered lexicographically.) Of course, you can object that this is not what you meant by "row", but a serious technical issue prevents any description as the one you gave from working: Your characterization is first-order and by the compactness theorem no first-order characterization of countability exists. –  Andres Caicedo Aug 15 at 4:15
1  
You can fix your description by requiring that between any two pebbles there are only finitely many (perhaps none) others. But then of course you shift the issue to describing finiteness, though that's a different story. –  Andres Caicedo Aug 15 at 4:16

protected by Asaf Karagila Sep 18 at 17:57

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

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