文献あり

Recreational Choicelessness

It is sometimes useful to pursue constructive proofs in set theoretic combinarotics, that is, to avoid the Axiom of Choice . Here are some examples where the constructive proofs are particularly simple.

Set families in $\mathscr{P}(\mathbb{N})$

The following are three famous problems concerning the power set of the natural numbers. They focus on the countability of $\left|\mathbb{N}\right|=\aleph_0$ and the uncountability of $\left|\mathscr{P}(\mathbb{N})\right|=\left|\mathbb{R}\right|=2^{\aleph_0}$. Relevant remarks are provided in the end of this section.

☆☆☆

A chain $\mathscr{C}\subseteq\mathscr{P}(\mathbb{N})$ is a set of subsets of $\mathbb{N}$ such that $\forall A, B\in\mathscr{C}$, $(A\subseteq B)\lor(A\supseteq B)$. Find an uncountable chain $\mathscr{C}$.

Solution

Note that it suffices to find any chain $\mathscr{C}\subseteq\mathscr{P}(X)$ with $\left|X\right|=\left|\mathbb{N}\right|$, and then apply the induced bijection $\mathscr{P}(X)\cong\mathscr{P}(\mathbb{N})$ on $\mathscr{C}$. For our purpose we pick $X=\mathbb{Q}$.

For each $a\in \mathbb{R}$ let
$$A_a=\left\{q\in\mathbb{Q}\mid q< a\right\}=\mathbb{Q}\cap(-\infty,a)$$

To see that $\mathscr{C}=\{A_a\mid a\in\mathbb{R}\}$ is a chain, it suffices to show for all $a< b\in\mathbb{R}$ that $A_a\subsetneqq A_b$, which is easy by the density of $\mathbb{Q}\subseteq\mathbb{R}$.
$$\cdots)_a\cdots)_b\cdots^\mathbb{Q}$$

★☆☆

An almost disjoint family $\mathscr{A}\subseteq\mathscr{P}(\mathbb{N})$ is a set such that $\forall A\ne B\in\mathscr{A}$, $\left|A\cap B\right|<\infty$. Find an uncountable almost disjoint family $\mathscr{A}$.

Solution

Similar to problem 1, we instead find an almost disjoint family $\mathscr{A}\subseteq\mathscr{P}(\mathbb{Q})$.

For all $a\in\mathbb{R}$ define
$$A_a=\left\{\frac{\lfloor na\rfloor}{n}\in\mathbb{Q}~\bigg\vert~n\in\mathbb{N}^{>0}\right\}\text{“}{\nearrow}_{n\to\infty}\text{”}~a$$
It's not hard to see that $A_a\ne A_b$ for $a\ne b\in\mathbb{R}$.

To see that $\mathscr{A}=\{A_a\mid a\in\mathbb{R}\}$ is an uncountable almost disjoint family, we show for all $a< b\in\mathbb{R}$ that $\left|A_a\cap A_b\right|<\infty$.
$$\cdots\text{░▒▓}]_a\quad \cdots\text{░▒▓}]_b\quad\rightarrow^\mathbb{Q}$$
Since $A_a\subseteq(-\infty,a]$ and since $b>a$ is an increasing limit point of $A_b$, it's not hard to believe that $A_b$ has only finitely many elements in $A_a\subseteq(-\infty,a]$. Indeed, we have
$$\left|A_a\cap A_b\right|\le\left\lceil\tfrac{1}{b-a}\right\rceil<\infty$$

★☆☆

An independent family $\mathscr{I}\subseteq\mathscr{P}(\mathbb{N})$ is a set such that $\forall X_1\ne\ldots\ne X_\ell\ne Y_1\ne\ldots\ne Y_m\in\mathscr{I}$, $\left|X_1\cap\ldots\cap X_\ell\smallsetminus Y_1\smallsetminus\ldots\smallsetminus Y_m\right|=\infty$. Find an uncountable independent family $\mathscr{I}$.

Solution

Similar to problems 1 and 2, we start by constructing a countable set
$$\mathfrak{Q}=\left\{(q_1,q_2)\sqcup\ldots\sqcup(q_{2n-1},q_{2n})\subseteq\mathbb{R}\mid n\in\mathbb{N},~q_1,\ldots,q_{2n}\in\mathbb{Q}\right\}$$

For each $a\in\mathbb{R}$ define
$$A_a=\left\{\mathfrak{q}\in\mathfrak{Q}\mid a\in \mathfrak{q}\subseteq\mathbb{R}\right\}$$

Then to see that $\mathscr{I}=\{A_a\mid a\in\mathbb{R}\}$ is an independent family, let $x_1\ne\ldots\ne x_\ell\ne y_1\ne\ldots\ne y_m\in\mathbb{R}$ be arbitrary. We can pick some $\mathfrak{q}=(q_1,q_2)\sqcup\ldots\in\mathfrak{Q}$ that separates all the reals:
$${-}(_{q_1}\bullet^{x_1})_{q_2}{-}\bullet^{y_1}{-}\bullet^{y_2}{-}\cdots{-}(_{q_{2n-1}}\bullet^{x_\ell})_{q_{2n}}{-}\bullet^{y_m}\rightarrow_{\mathbb{Q}}^{\mathbb{R}}$$
Then it's easy to see that $\mathfrak{q}\in A_{x_1}\cap\ldots\cap A_{x_\ell}\smallsetminus A_{y_1}\smallsetminus\ldots\smallsetminus A_{y_m}$. In fact there are infinitely many ways to choose $\mathfrak{q}$, which shows that
$$\left|A_{x_1}\cap\ldots\cap A_{x_\ell}\smallsetminus A_{y_1}\smallsetminus\ldots\smallsetminus A_{y_m}\right|=\infty$$

Here are some remarks.

An interesting alternative proof of problem 2 involves diagonalizing any countably infinite almost disjoint family to add a new member to it, which by transfinite induction gives an almost disjoint family of size $\left|\mathscr{A}\right|=\aleph_1$. In fact the cardinality $\mathfrak{a}$ of a smallest maximal almost disjoint family is a cardinal characteristic , so it's consistent that $\aleph_1<\mathfrak{a}<2^{\aleph_0}$.
All three problems above can be generalized to higher cardinals. In problem 3, we used the fact that $\mathbb{Q}\subseteq\mathbb{R}$ is a countable dense subset of an uncountable Hausdorff space . For $\kappa\ge\aleph_0$ an infinite cardinal, one can take $\mathbb{R}_\kappa=2^\kappa=\{a:\kappa\to 2\}$ to be a Hausdorff space by endowing with the product topology . The subset $\mathbb{Q}_\kappa=\{a\in 2^\kappa\mid \left|\{a=1\}\right|<\aleph_0\}$ of points of finite support is a size-$\kappa$ dense subset of $\mathbb{R}_\kappa$, and $\{\{r\cdot q=q'\}\mid q,q'\in\mathbb{Q}_\kappa\}$ is a size-$\kappa$ topological base of $\mathbb{R}_\kappa$. This then implies the number of ultrafilters on $\kappa$ is $2^{2^\kappa}$. See Thm 7.6 of [1].
Contrary to remark (2), the lexicographic order on $2^\kappa$ does not generate $\mathbb{R}_\kappa$ as its order topology , and so that generalization does not apply to problems 1 and 2. To construct a large linear order with a small dense subset, let $\lambda\le\kappa$ be the least such that $2^\lambda\ge\kappa^+$. Let $\tilde{\mathbb{R}}_\kappa=(2^\lambda,{<}_\text{lex})$ and let $\tilde{\mathbb{Q}}_\kappa=2^{<\lambda}\subseteq 2^\lambda$ be the set of all $a\in 2^\lambda$ of bounded support. Then $\tilde{\mathbb{Q}}_\kappa$ is a dense subset of $\tilde{\mathbb{R}}_\kappa$ of size $2^{<\lambda}\le\kappa$. The cardinality of $\tilde{\mathbb{R}}_\kappa$ thus depends on cardinal arithmetic.

$\mathscr{P}(\mathbb{N})/\text{fin}\cong\mathbb{R}/\mathbb{Q}$

$\mathscr{P}(\mathbb{N})/\text{fin}$

Define the almost equality equivalence relation $\sim_{\text{fin}}$ on $\mathscr{P}(\mathbb{N})$ via $\forall A,B\subseteq\mathbb{N}$,
$$A\mathrel{\sim_\text{fin}}B\iff\left|A\mathbin{\vartriangle}B\right|<\infty\iff \exists N,\forall n\ge N,(n\in A\leftrightarrow n\in B)$$
For example,
$$\{1,3,5,7,\ldots\}\mathrel{\sim_\text{fin}}\{\mathbf{0},\mathbf{2},\mathbf{4},5,7,\ldots\}\mathrel{\nsim_\text{fin}}\{0,2,4,6,\ldots\}$$
Write $\mathscr{P}(\mathbb{N})/\text{fin}$ for the quotient space of equivalence classes of $\sim_\text{fin}$.

$\mathbb{R}/\mathbb{Q}$

Define the Vitali equivalence relation $\sim_\mathbb{Q}$ on $\mathbb{R}$ via $\forall a,b\in\mathbb{R}$,
$$a\mathrel{\sim_\mathbb{Q}}b\iff a-b\in\mathbb{Q}$$
For example, $1\mathrel{\sim_\mathbb{Q}}\frac{22}{7}\mathrel{\nsim_\mathbb{Q}}\pi$.

Write $\mathbb{R}/\mathbb{Q}$ for the quotient space of equivalence classes of $\sim_\mathbb{Q}$.

From cardinal arithmetic one sees that $\left|\mathscr{P}(\mathbb{N})/\text{fin}\right|=2^{\aleph_0}=\left|\mathbb{R}/\mathbb{Q}\right|$. The following construction explicitly shows this equality.

$\leqq$

For sets $X,Y$ and equivalence relations ${\sim},{\approx}$ on $X,Y$ respectively, we say that $X/{\sim}\leqq Y/{\approx}$ iff there exists a function $f:X\to Y$ such that $\forall x,x'\in X$,
$$x\sim x'\iff f(x)\approx f(x')$$
This induces an injection $\hat{f}:X/{\sim}\hookrightarrow Y/{\approx}$, and so $\left|X/{\sim}\right|\le\left|Y/{\approx}\right|$.

★★☆

Construct explicit functions ${}^{f:}\mathscr{P}(\mathbb{N})\rightleftarrows\mathbb{R}{}_{:g}$ to show that $\mathscr{P}(\mathbb{N})/\text{fin}\mathrel{\lesseqqgtr}\mathbb{R}/\mathbb{Q}$.

Solution 1/2 ($\mathscr{P}(\mathbb{N})/\text{fin}\leqq\mathbb{R}/\mathbb{Q}$)

For each $A\subseteq\mathbb{N}$ define
$$f(A)=\sum_{n\in A}\frac{1}{n!}\in\mathbb{R}$$
Clearly if $A\mathrel{\sim_\text{fin}}B$ then $f(A)\mathrel{\sim_\mathbb{Q}}f(B)$.

It remains to show that if $A\mathrel{\nsim_\text{fin}}B$ then $f(A)\mathrel{\nsim_\mathbb{Q}}f(B)$. Note that
$$f(A)-f(B)=\sum_{n=0}^\infty\frac{1_A(n)-1_B(n)}{n!}$$
where $1_A(n)-1_B(n)\in\{\pm 1\}$ for infinitely many $n\in\mathbb{N}$.

Thus $f(A)-f(B)\notin\mathbb{Q}$ follows from one of the proofs that $e$ is irrational .

Solution 2/2 ($\mathscr{P}(\mathbb{N})/\text{fin}\geqq\mathbb{R}/\mathbb{Q}$)

This proof is by Itay Neeman.

For every $r\in \mathbb{R}$, there exists a unique terminating factorial base representation
$$r-\lfloor r\rfloor=\sum_{n=2}^\infty\frac{a_n}{n!}=\text{“}(0.a_2 a_3 a_4\ldots)_{!}\text{”}$$
where $a_n\in\{0,\ldots,n-1\}$ for all $n\ge 2$. See also [2].

It's not hard to see that the representation terminates (that is $\exists N,\forall n\ge N,a_n=0$) iff $r\in\mathbb{Q}$. Moreover one can show that $r\mathrel{\sim_\mathbb{Q}}s$ iff the representations of $r,s$ differ finitely (that is $\exists N,\forall n\ge N,a_n=b_n$ where $s=(0.b_2b_3\ldots)_{!}$).

Thus one can define the function $g:\mathbb{R}\to \mathscr{P}(\mathbb{N}\times\mathbb{N})$ via
$$g(r)=\left\{(n,a_n)\mid n\ge 2\right\}\subseteq\mathbb{N}\times\mathbb{N}$$
In return, $\forall r,s\in\mathbb{R}$, $r\mathrel{\sim_\mathbb{Q}}s$ iff $\left|g(r)\mathrel{\vartriangle}g(s)\right|<\infty$. By a simple bijection $\mathbb{N}\times\mathbb{N}\cong\mathbb{N}$ as in Problems 1,2,3 above, we get $\mathbb{R}/\mathbb{Q}\leqq\mathscr{P}(\mathbb{N})/\text{fin}$ as desired.

Here are some remarks.
(1) In general, whenever one can constructively show that $X/{\sim}\lesseqqgtr Y/{\approx}$, they can then apply the standard Cantor–Schröder–Bernstein argument to find a constructive bijection $X/{\sim}\cong Y/{\approx}$. It follows that $\left|X/{\sim}\right|=\left|Y/{\approx}\right|$ constructively.
(2) The function $f:\mathscr{P}(\mathbb{N})\to\mathbb{R}$ constructed in Solution 1/2 has the property that whenever $A_1\nsim_\text{fin}\ldots\nsim_\text{fin} A_n\in\mathscr{P}(\mathbb{N})$, the set $\{f(A_1),\ldots,f(A_n)\}\subseteq\mathbb{R}$ is in fact $\mathbb{Q}$- linearly independent . One can find an uncountable family of such $f(A_i)\in\mathbb{R}$ by using either of Problems 1,2,3 above. Thus constructively we've shown that $\dim_\mathbb{Q}(\mathbb{R})\ge\left|\mathbb{R}\right|$. Contrast this with the fact that there exists no constructive $\mathbb{Q}$-basis of $\mathbb{R}$ .
(3) With respect to the product-discrete topology on $\mathscr{P}(\mathbb{N})\cong 2^\mathbb{N}$, both $\sim_\text{fin},\sim_\mathbb{Q}$ are Borel equivalence relations , and the functions $f,g$ constructed are Borel reductions between them. In standard notation, $\mathscr{P}(\mathbb{N})/\text{fin}\cong\mathbb{R}/\mathbb{Q}$ can be instead written as $E_0\mathrel{\equiv_B}E_v$.
(4) There exists no constructive bijection $\mathbb{R}\cong \mathbb{R}/\mathbb{Q}$. Assuming $\mathsf{AD}^{L(\mathbb{R})}$ , one can in fact show that $\left|\mathbb{R}\right|<\left|\mathbb{R}/\mathbb{Q}\right|$ holds in $L(\mathbb{R})$. See Ch. 4 Sec. 4 of [3].

Miscellaneous Puzzles

I have no idea how to come up with solutions to the following puzzles. However, other people have:

★★★

A 3-term arithmetic progression in $\mathbb{R}$ is a set of the form $\{x,x+a,x+2a\}$ for some $a>0$. Construct a maximal subset $\mathscr{S}\subseteq\mathbb{R}$ without a 3-term arithmetic progression.

That is, $\mathscr{S}$ has no 3-term arithmetic progressions, but $\forall r\notin\mathscr{S}$, $\mathscr{S}\sqcup\{r\}\subseteq\mathbb{R}$ has a 3-term arithmetic progression.

Link to Solution

★★★

A circle in $\mathbb{R}^3$ is any circle of radius $r\in(0,\infty)$. Construct a partition of $\mathbb{R}^3$ into circles.

Link to Solution