Cardinal Numbers

Contents
Contents
1.  The Order of Cardinal Numbers
   1.1.  Cardinal Ordering
   1.2.  Countable and Uncountable Sets
2.  Continued on Page Three

Page 1 Page 2 Page 3

(Continued.)

1. The Order of Cardinal Numbers 1.1. Cardinal Ordering We also want to talk about the sets that are not equinumerous. Naturally we adopt the following definition.

Definition 1. For two sets

A,B

, if there is an injection from

A

into

B

, we say

A

is at most the size of

B

, and write

A\preccurlyeq B

Definition 2. For two sets

A,B

, if

A\preccurlyeq B

, we define the order of cardinal numbers

|A|,|B|

|A|\leqslant |B|

If $|A|\leqslant|B|$ and $|A|\neq |B|$ , we further define $|A|<|B|$ .

Note that it is necessary to check the cardinal ordering is well-defined. If $A',B'$ are the sets with the same cardinal numbers, i.e. $|A'|=|A|$ and $|B'|=|B|$ , do we have $A'\preccurlyeq B'$ ? This is easy to verify using $A\sim A'$ and $B\sim B'$ .

The notation $\leqslant$ is used. Does it have the usual properties of a usual inequality? One can prove the following theorem.

Theorem 3. Suppose

A,B,C

are sets.

$|A|\leqslant|A|$ .
$(|A|\leqslant|B|)\wedge(|B|\leqslant|C|)\Rightarrow|A|\leqslant|C|$ .
(Schröder-Bernstein theorem) $(|A|\leqslant|B|)\wedge(|B|\leqslant|A|)\Rightarrow|A|=|B|$ .
Either $|A|\leqslant|B|$ or $|B|\leqslant|A|$ .

The first two are obvious. We will prove 3 soon (at the end of this section) but 4 much later.

Schröder-Bernstein theorem is a useful tool to obtain the cardinal number of a set. An immediate consequence is that $(A\subseteq B\subseteq C)\wedge (A\sim C)\Rightarrow |A|=|B|=|C|$ . This can be seen by $|A|\leqslant|B|\leqslant|A|$ and Schröder-Bernstein theorem. A quick example: $[0,1]\sim\mathbb R$ , since $(0,1)\subseteq[0,1]\subseteq\mathbb R$ and we have known $(0,1)\sim\mathbb R$ . (This can also be seen from a direct bijection between $(0,1)$ and $[0,1]$ .)

1.2. Countable and Uncountable Sets We will prove that $|\mathbb N|$ is the least cardinal number. This cardinal number deserves a special natation. We define

$\aleph _ 0:=|\mathbb N|.$

The notation is "aleph zero", used by Cantor, where $\aleph$ is the first letter of the Hebrew alphabet.

Definition 4. A set

A

is countable if

A\preccurlyeq\mathbb N

, i.e.,

|A|\leqslant\aleph _ 0

If it is proved that $\aleph _ 0$ is the least cardinal number (Theorem 7), then $A$ is countable if and only if $A$ is finite or $|A|=\aleph _ 0$ .

A countable set that is infinite is said to be countably infinite. Note that some authors use different terminologies: They call countably infinite sets "countable" and countable sets "at most countable".

A first example: The set $\mathbb Q$ is countable. It is not difficult to see that $\mathbb N\sim\mathbb Z\times\mathbb Z$ (because we can count the integer points on the Cartesian plane from near to distant, starting from the origin,) and $\mathbb N\preccurlyeq\mathbb Q\preccurlyeq\mathbb Z\times\mathbb Z$ . Therefore $|\mathbb Q|=\aleph _ 0$ .

The following theorems proved by Cantor give an example of uncountable sets and assert that there is no largest cardinal number.

Theorem 5.

\aleph _ 0<|\mathbb R|

Theorem 6. For any set

A

|A|<|\mathcal P(A)|

With the help of axiom of choice, we will prove the following theorems.

Theorem 7. If

A

is infinite, then

\mathbb N\preccurlyeq A

. Alternatively, if

|A|

is an infinite cardinal number, then

\aleph _ 0\leqslant|A|

Corollary 8. The following four corollaries are simple, among which the last two can be proved independently, without the axiom of choice.

A set $A$ is finite if and only if $|A|<\aleph _ 0$ .
A set is infinite if and only if it is equinumerous to a proper subset of itself.
Subsets of finite sets are finite.
Any infinite subset of $\mathbb N$ is equinumerous to $\mathbb N$ .

Theorem 9. Suppose

B\neq\varnothing

, then

B\preccurlyeq A

if and only if there is a surjection

f:A\to B

In particular, a nonempty set $B$ is countable if and only if there is a surjection $f:\mathbb N\to B$ .

Theorem 10. A countable union of countable sets is countable, i.e., if

\mathcal A

is countable and if every member of

\mathcal A

is a countable set, then

\bigcup \mathcal A

is countable.

Proposition 11. Given a set

A

, consider the set

A^{<\mathbb N}

of all finite sequences. Here a finite sequence of length

n

is a function from

\mathbb N _ {<n}

(

n\in\mathbb N

) into

A

. Then:

$|\mathbb N^{<\mathbb N}|=\aleph _ 0$ .
If $A$ is countable, then $A^{<\mathbb N}$ is countable.

Proposition 12. A real number is called algebraic it is the root of a polynomial with rational (or equivalently, integer) coefficients. Otherwise the number is called transcendental.

The set of algebraic numbers is countable.
The set of transcendental numbers is uncountable.

We have known the set $\mathbb Q$ of rational numbers, contained in $\mathbb R$ , is countable. The set of algebraic numbers contains $\mathbb Q$ and thus a larger set. However it is still countable. The cardinal number of the set of transcendental numbers is the same as that of the set of real numbers. Therefore typically it is difficult to prove some numbers are transcendental. For example it is not trivial that the base $\mathrm e$ of natural logarithm is transcendental, but it is not very tough to prove either. What is more challenging is to prove the geometric constant $\pi$ is transcendental, which is done in the not-too-distant past.

Finally here are two more examples, which are really simple. (a) Any subset of a countable set is countable. (b) If $A$ is infinite, then $\aleph _ 0\leqslant|A|<|\mathcal P(A)|$ . The power set must be uncountable.

2. Continued on Page Three

Page 1 Page 2 Page 3

评论

发表回复取消回复

Cardinal Numbers

评论

发表回复 取消回复

发表回复取消回复