28 - Definitions regarding cardinality

Definition: Sets A and B have the same cardinality if there exists a bijection from A to B.
!Screenshot 2023-11-15 at 10.06.53 AM.png

A and B have different cardinality because no bijection exists from A to B.
!Screenshot 2023-11-17 at 10.42.50 AM.png

In class practice

A = $N$ , $B = N \in E V E N$
Bijective
$| N |$ = $| N_{e v e n} |$

$A = (0, 1), B = (4, 17)$ open intervals
$f : A \to B$
$f (x) = 13 x + 4$ is a bijection $| (0, 1) | = | (4, 17) |$

Theorem $| N | = | Z |$
Let $f : N \to Z$ be the function

f (n) = {\begin{cases} \frac{n}{2} if n is even \\ - \frac{n - 1}{2} if n is odd \end{cases}

By the pasting together theorem (and other previous work), $f$ is a bijection $◻$

Proof.
Let $f$ be the function

1	2	3	4	5	6	7	...
0	1	-1	2	-2	3	-3	...

Since this is a non repeating list that covers all of $Z$ it defines a bijection $N \to Z$ .

Principle: To construct a bijection from $N \to A$ , it suffices to enumerate the elements in $A$ in a list with no repeats. The pattern must be obvious.

Theorem. Let $\sim$ be the relation on sets given by $A \sim B$ if $| A | = | B |$ . Then $\sim$ is an equivalence relation.

Proof.
(Reflexive)
Let $A$ be a set. Then $i d_{A} : A \to A$ is a bijection, so $| A | = | A |$ so $A \sim A$

(Symmetric)
Let A, B be sets. Assume that $A \sim B$ . Then $| A | = | B |$ , so there exists a bijection $f : A \to B$ . Then $f^{- 1} : B \to A$ is a bijection so $| B | = | A |$ .

(Transitive)
Let $A, B, C$ be sets. Assume that $A \sim B$ and $B \sim C$ . Then there exists bijections $f : A \to B$ and $g : B \to C$ . Then $g \circ f : A \to C$ is a bijection, so $| A | = | C |$ i.e. $A \sim C$ . $◻$

The cardinality of A is a name we give to the equivalence class of A under $\sim$ .

$| N | = | N_{e v e n} | = | Z | = ℵ_{0}$ "aleph-nought". Things in this equivalence class are called countably infinite. It is the smallest infinite cardinality.
$ℵ :$ the first letter of the Hebrew alphabet.

Theorem: If $A$ is an infinite subset of a countably infinite set, then $| A | = ℵ_{0}$
Proof. Without loss of generality, we may assume that $A \subseteq N$ . Let $a_{1}$ be the least element of $A$ . Let $a_{2}$ be the least element of $A - {a_{1}}$ . Repeat. Let $a_{n}$ be the least element of $A - {a_{1}, . . ., a_{n - 1}}$ . So $a_{1}, a_{2}, a_{3} . . .$ is an infinite, non-repeating list that covers all of A. So $| A | = | N |$ . $◻$

HW 28

Ben Finch

E 28.1
a) False. {1, 2} and {a, b, c} do not have the same cardinality.
b) True. Per the definition of a function, each $a \in A$ must be the component of exactly one element in $f : A \to B$ . So $| A | = | f |$ .
c) False. {1} $\subseteq N$ but it is not countably infinite.
d) False. Some infinite sets are not countable, so they could have a cardinality of $ℵ_{1}$ or higher.
e) False. Let A = {1, 2, 3}. Let B = {4, 5}. Let $f : A \to B =$ {(1, 4), (2, 5), (3, 4)}. We see that $f$ is surjective but $2 \neq 3$ .

E 28.2
Proof.
We first aim to prove that that the set of those natural numbers with exactly one digit equal to 7 is infinite. Suppose by way of contradiction that there this set is finite. Suppose that $a$ is the greatest element of this set. Now replace any digits of $a$ equal to $7$ with $9$ . Then multiply by this number ten and add seven. Call this number $b$ . We see that $b > a$ but $b$ is still in the set of natural numbers with exactly one digit equal to seven. So the set of natural numbers with exactly one digit equal to 7 is infinite. Per theorem 28.14, this set is also countably infinite, since it is a subset of the natural numbers, which is countably infinite. $◻$

E 28.3
Let $S = {x \in Z : x = a^{2} + b^{2}$ for some $a, b \in Z}$ . Then $S \subseteq Z$ since adding any two squares of integers will always be an integer. Per theorem 28.4, the cardinalities of $N$ and $Z$ are the same. Per theorem 28.14, any subset of a countably infinite set is countably infinite. Therefore, since $S \subseteq Z$ , $| S | = | N |$

E 28.4
We see that for every $x$ in $(0, \infty)$ , there is a $y$ in $(0, 1)$ . Since $x$ is positive, $x + 1$ is also positive, and thus $\frac{x}{x + 1}$ is positive. Also, $\frac{x}{x + 1}$ is less than 1 because the numerator $x$ is always less than the denominator $x + 1$ . Therefore, $y$ exists in $(0, 1)$ for each $x$ in $(0, \infty)$ .

We now prove that $h$ is a bijection.

(Injective)
Let $a_{1}, a_{2} \in (0, \infty)$ . Assume that $h (a_{1}) = h (a_{2})$ . We find

\begin{aligned} \frac{a_{1}}{a_{1} + 1} & = \frac{a_{2}}{a_{2} + 1} \\ a_{1} (a_{2} + 1) & = a_{2} (a_{1} + 1) \\ a_{1} a_{2} + a_{1} & = a_{2} a_{1} + a_{2} \\ a_{1} & = a_{2} \end{aligned}

(Surjective)
Let $b \in (0, 1)$ . Define $a = - \frac{b}{b - 1}$ .
We find

\begin{aligned} f (a) & = \frac{a}{a + 1} \\ = \frac{- \frac{b}{b - 1}}{- \frac{b}{b - 1} + 1} \\ = \frac{- \frac{b}{b - 1}}{\frac{- 1}{b - 1}} \\ = - \frac{b}{- 1} \\ = b \end{aligned}

So $h$ is surjective.

So $h$ is a bijection. $◻$

Since $h$ is a bijection, it follows that $(0, \infty)$ and $(0, 1)$ have the same cardinality.

E 28.5
Let

\begin{aligned} j (x) & = \frac{- x}{x - 1} \end{aligned}

We see that for every $x$ in $(- \infty, 0)$ , there is a $y$ in $(- 1, 0)$ . Since $x$ is negative, -x is positive, $x - 1$ is negative, and thus $\frac{x}{x + 1}$ is negative. Also, $\frac{- x}{x - 1}$ is greater than -1 but less than 0 because the numerator $x$ is always greater than the denominator $x$ (where $x$ is negative). Therefore, $y$ exists in $(- 1, 0)$ for each $x$ in $(- \infty, 0)$ .

(Injective)
Let $a_{1}, a_{2} \in (0, \infty)$ . Assume that $j (a_{1}) = j (a_{2})$ . We find

\begin{aligned} \frac{- a_{1}}{a_{1} - 1} & = \frac{- a_{2}}{a_{2} - 1} \\ a_{1} (a_{2} - 1) & = a_{2} (a_{1} - 1) \\ a_{1} a_{2} - a_{1} & = a_{2} a_{1} - a_{2} \\ - a_{1} & = - a_{2} \\ a_{1} & = a_{2} \end{aligned}

So $j$ is injective.

(Surjective)

\begin{aligned} y & = \frac{- x}{x - 1} \\ y (x - 1) & = - x \\ y x - y & = - x \\ y x + x & = y \\ x (y + 1) & = y \\ x & = \frac{y}{y + 1} \end{aligned}

Let $b \in (- 1, 0)$ . Define $a = \frac{b}{b + 1}$ . We find

\begin{aligned} j (a) & = \frac{- a}{a - 1} \\ = \frac{(- \frac{b}{b + 1})}{\frac{b}{b + 1} - 1} \\ = \frac{(- \frac{b}{b + 1})}{\frac{b - (b + 1)}{b + 1}} \\ = \frac{\frac{- b}{b + 1}}{\frac{- 1}{b + 1}} \\ = \frac{- b}{- 1} \\ = b \end{aligned}

So $j$ is surjective.

Since $j$ is both injective and surjective, $j$ is bijective. $◻$

E 28.6
Define $f : R \to (- 1, 1)$

f (x) = {\begin{cases} \frac{x}{x + 1} if x \in (0, \infty) \\ \frac{- x}{x - 1} if x \in (- \infty, 0) \\ 0 if x \in {0} \end{cases}

We know that the first two parts of $f (x)$ are bijective from the previous two exercises. If $x = 0$ then $f$ is bijective since $(0, f (0)) = (0, 0)$ and the identity function is a bijection. By the pasting together theorem, since each part of $f (x)$ is bijective, $f (x)$ is bijective.

Let $l : (- 1, 1) \to (0, 1)$ . Let $l (x) = \frac{1}{2} (x + 1) = \frac{1}{2} x + \frac{1}{2}$ .
We see that for every $x \in (- 1, 1)$ , there exists a $y$ in $(0, 1)$ .

(Injective)
Let $a_{1}, a_{2} \in (- 1, 1)$ . Assume that $f (a_{1}) = f (a_{2})$ . We find

\begin{aligned} \frac{1}{2} a_{1} + \frac{1}{2} & = \frac{1}{2} a_{2} + \frac{1}{2} \\ \frac{1}{2} a_{1} & = \frac{1}{2} a_{2} \\ a_{1} & = a_{2} \end{aligned}

So $l$ is injective.
(Surjective)

Let $b \in (0, 1)$ . Define $a = 2 b - 1$ . We find

\begin{aligned} f (a) & = \frac{1}{2} a + \frac{1}{2} \\ = \frac{1}{2} (2 b - 1) + \frac{1}{2} \\ = b - \frac{1}{2} + \frac{1}{2} \\ = b \end{aligned}

So $l$ is surjective.

Since $l$ is surjective and injecting, $l$ is bijective.

We now form a composition of $f$ and $l$ . Then $f \circ l : R \to (0, 1)$ is a bijection since both $f$ and $l$ are bijections, per theorem 26.12. Since there exists a bijection from $R$ to $(0, 1)$ , $| R | = | (0, 1) |$ .

E 28.7
Let B be a countable set. Let $A \subseteq B$ . Then $| A | \leq | B |$ . Also, in order for B to be countable, $| B | \leq ℵ_{0}$ . Since $| A | \leq | B |$ , then $| A | \leq ℵ_{0}$ . So $A$ is countable. $◻$

E 28.8

( $\Rightarrow$ )
Assume some set $A$ is countable. By definition, a set is countable if it is finite or if it has the same cardinality as the set of natural numbers $N$ . If $A$ is finite, we can define an injective function from $A$ to $N$ by assigning each element in $A$ to a unique natural number. If $A$ is infinite and countable, it can be listed in a sequence $a_{1}, a_{2}, a_{3}, \dots$ . We can then define $f$ such that $f (a_{i}) = i$ , which is injective since each element in $A$ is mapped to a unique natural number.

( $\Leftarrow$ )
Let $A$ be a set. Assume there exists an injective function $f : A \to N$ . An injective function $f$ from $A$ to $N$ ensures that each element of $A$ is mapped to a distinct natural number. This mapping creates a sequence of elements in $A$ based on their corresponding natural numbers in $N$ . This sequence will list a subset of $N$ , showing that $A$ is countable (Theorem 28.14). If $A$ is finite, it is obviously countable. If $A$ is infinite, since it can be put into a one-to-one correspondence with a subset of $N$ , it is countable.

Thus, we conclude that a set $A$ is countable if and only if there exists an injective function $f : A \to N$ . $◻$