31 - Injections and cardinalities

!Screenshot 2023-11-27 at 10.05.21 AM.png
We can think of injections as giving only “half” of the information needed to construct a bijection, which is why we only get an inequality $\leq$

If $A$ is a set, then $| A | < | P (A) |$

Let $A$ and $B$ be sets.

Let $g : A \to B$ be a function.

Define $C = {x \in A : x \notin g (x)}$ (barber set)

Proof.
Let $A$ be a set. Let $g : A \to P (A)$ be a function. Define the barber set $B = {x \in A : x \notin g (x)}$ . Let $a \in A$ .

Case 1: Assume that $a \in g (a)$ . Then $a \notin B,$ hence $g (a) \neq B$ .

Case 2: Assume that $a \notin g (a)$ . Then $a \in B$ hence $g (a) \neq B$ .

So in every case $g (a) \neq B$ . Since $a \in A$ was arbitrary. $g : A \to P (A)$ is not surjective.

Define $f : P (A) \to F (A)$ by the rule $f (s) = χ_{S}$ .
We first show that $f$ is injective.
Let $S, T \in P (A)$ and assume that $f (S) = f (T)$ .
Then $χ_{S} = χ_{t}$ .
Let $a \in A$ , we h

Exam Question
If A is any set, then $| P (A) | = | F (A) |$ .

HW 31

Ben Finch

E 31.1
a) False. Consider the power set of $(0, 1)$ . By theorem 31.5, it has a larger cardinality than (0, 1) despite being uncountable. $◻$ .
b) True. Since A is a subset of B, all elements in A must be in B. Thus it is impossible for A to have a greater cardinality than B. $◻$
c) True. By definition of a true subset, all elements in A must be in B, but A must not include all elements of B. So it is evident that |A| < |B|. $◻$
d) True. Since A is a countably infinite set, and A is a subset of B, B is not finite. Per theorem 28.14, since C is countably infinite, B must also be countably infinte. $◻$
e) False. Take {1} $\subseteq R$ . |{1}| = 1 < $| R |$ . $◻$
f) False. Take A = {1}, B = {3, 4}. We see that |A| < |B| and A is finite, but B is not infinite. $◻$
g) False. Take A = {1}, B = {3, 4}. We see that |A| < |B| and A is countable, but B is also countable. $◻$
h) True. All countably infinite sets have the same cardinality. Also, a countably infinite set has the highest cardinality of any countable set. So if B has a greater cardinality than a countably infinite set, it is uncountable. $◻$
g) True. Per theorem 31.5, take B = $P (A)$ . We have $| A | < | B |$ .

E 31.2
$B = {a, b, d}$
The reason $B$ is not in the image of $g$ is because that is the definition of the barber set. It is specifically constructed so that it is not in the image of $g$ .

E 31.3
Take power set of $R$ . Per theorem 31.5, $| P (R) | > | R |$ . Now take the power set of that set. Per the same theorem $P (P (R)) > P (R)$ . $◻$ .

E 31.4
a)
(injective)
Define a function $f : N \to N$ such that $f (n) = n + 1$ . Let $a_{1}, a_{2} \in N$ . Assume that $f (a_{1}) = f (a_{2})$ . We see that

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

So $f$ is injective.

(not surjective)
$f$ does not map any value to $1$ , since the lowest possible value for $f (n) = 2$ . So $f$ is not surjective. $◻$

b)
(surjective)
Define a function $g : N \to N$ such that

g (n) = {\begin{cases} 1 & if n = 1, \\ n - 1 & if n > 1. \end{cases}

There are two cases:
Case 1: $n \neq 1$ .
Let $b \in N$ . Define $a = b + 1$ . We see that

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

So for all $a \in N$ there exists a $b \in N$ such that $a$ maps to it.

Case 2: $n = 1$ . In this case $n$ is explicitly mapped to 1 which is in $N$ .

Thus in all cases, $g$ is surjective.

(not injective)
We see that $g (1) = g (2) = 1$ so $g$ is not injective. $◻$

E 31.5

(Injective)

Assume $g (S_{1}) = g (S_{2})$ for some $S_{1}, S_{2} \subseteq A$ . This means that ${f (s) : s \in S_{1}} = {f (s) : s \in S_{2}}$ . Since $f$ is a bijection, it is injective, so each element in $S_{1}$ must be mapped to a unique element in $B$ , and similarly for $S_{2}$ . Therefore, $S_{1} = S_{2}$ , so $g$ is injective.

(Surjective)

Let $T$ be any subset of $B$ . We want to find a subset $S \subseteq A$ such that $g (S) = T$ . Since $f$ is a bijection, for each $t \in T$ , there exists a unique $s \in A$ such that $f (s) = t$ . Let $S$ be the set of all such $s$ in $A$ that correspond to elements of $T$ under $f$ . Then $g (S) = T$ , proving that $g$ is surjective.

Since $g$ is both injective and surjective, $g$ is bijective.

Thus, $| P (A) | = | P (B) |$ . $◻$

E 31.6
(Injective)
Let $x_{1}, x_{2} \in R$ . Assume $f (x_{1}) = f (x_{2})$ . Since $f (x_{1}) = f (x_{2})$ , every rational number less than or equal to $x_{1}$ is also less than or equal to $x_{2}$ , and vice versa. Suppose by way of contradiction that $x_{1} \neq x_{2}$ ; without loss of generality, assume $x_{1} < x_{2}$ . From exercise 11.6, there exists a rational number $r$ such that $x_{1} < r < x_{2}$ . However, this rational number $r$ would be in $f (y)$ but not in $f (x)$ , contradicting the assumption that $f (x) = f (y)$ . Therefore, $x$ must equal $y$ , and $f$ is injective. $◻$

By 31.1, we have $| R | \leq | P (Q) |$ . Since, by 29.7, $| Q | = | N |$ then $| P (Q) | = | P (N) |$ . So we have $| R | \leq | P (N) |$ .

E 31.7
Proof.
$\Rightarrow$ Assume there exists an injection $f : A \to B$ . By definition of injection, for each $a_{1}, a_{2} \in A$ , if $f (a_{1}) = f (a_{2})$ , then $a_{1} = a_{2}$ . We need to show that there exists a surjection $g : B \to A$ .

Define $g : B \to A$ as follows:
For each $b \in B$ , if there exists $a \in A$ such that $f (a) = b$ , set $g (b) = a$ . If no $a \in A$ exists (i.e., $b$ is not an image of any $a$ under $f$ ), pick any $a^{'} \in A$ and set $g (b) = a^{'}$ .

Since $A$ is nonempty, such an $a^{'}$ always exists. So, every element of $A$ is the image under $g$ of at least one element of $B$ , thus $g$ is a surjection.

$\Leftarrow$ Assume there exists a surjection $g : B \to A$ . By definition of surjection, for each $a \in A$ , there exists at least one $b \in B$ such that $g (b) = a$ . We need to show that there exists an injection $f : A \to B$ .

Define $f : A \to B$ as follows:
For each $a \in A$ , since $g$ is surjective, there exists at least one $b \in B$ such that $g (b) = a$ . Choose some arbitrary $b$ for each $a$ and set $f (a) = b$ .

This definition ensures that different elements of $A$ are mapped to different elements of $B$ . Thus, if $a_{1} \neq a_{2}$ , then the $b$ chosen for $a_{1}$ is different from the $b$ chosen for $a_{2}$ since $g (b) = a_{1}$ and $g (b) = a_{2}$ cannot hold simultaneously for the same $b$ . Therefore, $f$ is an injection.

Thus, we have shown that the existence of an injection $f : A \to B$ implies the existence of a surjection $g : B \to A$ and vice versa. $◻$