3.6. Advanced set theory problems

Functions

Let $A,B$ and $C$ be sets.

Exponent rules for cardinal numbers.

1. Suppose that $B\cap C=\varnothing$. Then, $\left|A^{B\cup C}\right|=\left|A^B\times A^C\right|$.
2. $\left|{\left(A^B\right)}^C\right|=\left|A^{B\times C}\right|$.

Exercise.

Prove that $\left|A^A\right|\le \left|\{0,1{\}}^{A\times A}\right|$.

Exercise.

Show that $F^X$ and $\{0,1{\}}^X$ have the same size whenever $F$ is finite and has at least two elements, and $X$ is an infinite set.

Countability

Exercise.

Suppose that $X$ is countably infinite and that $A$ is finite. Show that $X\setminus A$ is countably infinite.

Exercise.

A real number $r$ is algebraic if there is a polynomial $p(x)$ with rational coefficients such that $p(r)=0$. Prove that there are countably many algebraic numbers.

Theorem.

The image, under any function, of a countable set is countable.

Exercise.

The collection of all subsets…

1. of a countable set of a fixed finite size, is countable.
2. of a countable set of any finite size, is countable.
3. of an infinite set is always uncountable.

Almost disjointness

Definition (Almost disjoint family).

A family of sets $\mathcal{F}$ is called pairwise disjoint if for all $A,B\in \mathcal{F}$, $A\ne B$ implies $A\cap B$ is empty.

A family $\mathcal{F}$ consisting of infinite sets is called almost disjoint if in the above definition you change empty to finite.

Exercise (Any family can be made disjoint).

For any family $\mathcal{F}$, there is a pairwise disjoint family with the same union as $\mathcal{F}$.

Exercise.

In this exercise we only consider families of subsets of $\mathbb{N}$.

1. Show that all pairwise disjoint families are countable.

2. Show that there is an uncountable almost disjoint family.

3. Any countable almost disjoint family can be extended by adding more subsets.

Hint.

2. For every real number $x$, fix a sequence of rationals $a_k^{(x)}$ that converges to $x$. Enumerate the rationals $q_0,q_1,\dots$ and show that the collection of all sets of the form $A_x:=\{k\in \mathbb{N}:\exists n\in \mathbb{N},q_k=a_n^{(x)}\}$ is almost disjoint and has size $|\mathbb{R}|$.