文献あり

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 $P (N)$

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

☆☆☆

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

Solution

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

For each $a \in R$ let
$A_{a} = {q \in Q ∣ q < a} = Q \cap (- \infty, a)$

To see that $C = {A_{a} ∣ a \in R}$ is a chain, it suffices to show for all $a < b \in R$ that $A_{a} ⫋ A_{b}$ , which is easy by the density of $Q \subseteq R$ .
$\dots)_{a} \dots)_{b} \dots^{Q}$

★☆☆

An almost disjoint family $A \subseteq P (N)$ is a set such that $\forall A \neq B \in A$ , $| A \cap B | < \infty$ . Find an uncountable almost disjoint family $A$ .

Solution

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

For all $a \in R$ define
$A_{a} = {\frac{⌊ n a ⌋}{n} \in Q | n \in N^{> 0}} “ ↗_{n \to \infty} ” a$
It's not hard to see that $A_{a} \neq A_{b}$ for $a \neq b \in R$ .

To see that $A = {A_{a} ∣ a \in R}$ is an uncountable almost disjoint family, we show for all $a < b \in R$ that $| A_{a} \cap A_{b} | < \infty$ .
$\dots ░▒▓]_{a} \dots ░▒▓]_{b} \to^{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
$| A_{a} \cap A_{b} | \leq ⌈ \frac{1}{b - a} ⌉ < \infty$

★☆☆

An independent family $I \subseteq P (N)$ is a set such that $\forall X_{1} \neq \dots \neq X_{ℓ} \neq Y_{1} \neq \dots \neq Y_{m} \in I$ , $| X_{1} \cap \dots \cap X_{ℓ} ∖ Y_{1} ∖ \dots ∖ Y_{m} | = \infty$ . Find an uncountable independent family $I$ .

Solution

Similar to problems 1 and 2, we start by constructing a countable set
$Q = {(q_{1}, q_{2}) ⊔ \dots ⊔ (q_{2 n - 1}, q_{2 n}) \subseteq R ∣ n \in N, q_{1}, \dots, q_{2 n} \in Q}$

For each $a \in R$ define
$A_{a} = {q \in Q ∣ a \in q \subseteq R}$

Then to see that $I = {A_{a} ∣ a \in R}$ is an independent family, let $x_{1} \neq \dots \neq x_{ℓ} \neq y_{1} \neq \dots \neq y_{m} \in R$ be arbitrary. We can pick some $q = (q_{1}, q_{2}) ⊔ \dots \in Q$ that separates all the reals:
$- (_{q_{1}} ∙^{x_{1}})_{q_{2}} - ∙^{y_{1}} - ∙^{y_{2}} - \dots - (_{q_{2 n - 1}} ∙^{x_{ℓ}})_{q_{2 n}} - ∙^{y_{m}} \to_{Q}^{R}$
Then it's easy to see that $q \in A_{x_{1}} \cap \dots \cap A_{x_{ℓ}} ∖ A_{y_{1}} ∖ \dots ∖ A_{y_{m}}$ . In fact there are infinitely many ways to choose $q$ , which shows that
$| A_{x_{1}} \cap \dots \cap A_{x_{ℓ}} ∖ A_{y_{1}} ∖ \dots ∖ A_{y_{m}} | = \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 $| A | = ℵ_{1}$ . In fact the cardinality $a$ of a smallest maximal almost disjoint family is a cardinal characteristic , so it's consistent that $ℵ_{1} < a < 2^{ℵ_{0}}$ .
All three problems above can be generalized to higher cardinals. In problem 3, we used the fact that $Q \subseteq R$ is a countable dense subset of an uncountable Hausdorff space . For $κ \geq ℵ_{0}$ an infinite cardinal, one can take $R_{κ} = 2^{κ} = {a : κ \to 2}$ to be a Hausdorff space by endowing with the product topology . The subset $Q_{κ} = {a \in 2^{κ} ∣ | {a = 1} | < ℵ_{0}}$ of points of finite support is a size- $κ$ dense subset of $R_{κ}$ , and ${{r \cdot q = q^{'}} ∣ q, q^{'} \in Q_{κ}}$ is a size- $κ$ topological base of $R_{κ}$ . This then implies the number of ultrafilters on $κ$ is $2^{2^{κ}}$ . See Thm 7.6 of [1].
Contrary to remark (2), the lexicographic order on $2^{κ}$ does not generate $R_{κ}$ 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 $λ \leq κ$ be the least such that $2^{λ} \geq κ^{+}$ . Let ${\tilde{R}}_{κ} = (2^{λ}, <_{lex})$ and let ${\tilde{Q}}_{κ} = 2^{< λ} \subseteq 2^{λ}$ be the set of all $a \in 2^{λ}$ of bounded support. Then ${\tilde{Q}}_{κ}$ is a dense subset of ${\tilde{R}}_{κ}$ of size $2^{< λ} \leq κ$ . The cardinality of ${\tilde{R}}_{κ}$ thus depends on cardinal arithmetic.

$P (N) / fin ≅ R / Q$

P (N) / fin

Define the almost equality equivalence relation $\sim_{fin}$ on $P (N)$ via $\forall A, B \subseteq N$ ,
$A \sim_{fin} B ⟺ | A △ B | < \infty ⟺ \exists N, \forall n \geq N, (n \in A \leftrightarrow n \in B)$
For example,
${1, 3, 5, 7, \dots} \sim_{fin} {0, 2, 4, 5, 7, \dots} ≁_{fin} {0, 2, 4, 6, \dots}$
Write $P (N) / fin$ for the quotient space of equivalence classes of $\sim_{fin}$ .

R / Q

Define the Vitali equivalence relation $\sim_{Q}$ on $R$ via $\forall a, b \in R$ ,
$a \sim_{Q} b ⟺ a - b \in Q$
For example, $1 \sim_{Q} \frac{22}{7} ≁_{Q} π$ .

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

From cardinal arithmetic one sees that $| P (N) / fin | = 2^{ℵ_{0}} = | R / Q |$ . The following construction explicitly shows this equality.

≦

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

★★☆

Construct explicit functions $^{f :} P (N) ⇄ R_{: g}$ to show that $P (N) / fin ⪋ R / Q$ .

Solution 1/2 (

P (N) / fin ≦ R / Q

)

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

It remains to show that if $A ≁_{fin} B$ then $f (A) ≁_{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 N$ .

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

Solution 2/2 (

P (N) / fin ≧ R / Q

)

This proof is by Itay Neeman.

For every $r \in R$ , there exists a unique terminating factorial base representation
$r - ⌊ r ⌋ = \sum_{n = 2}^{\infty} \frac{a_{n}}{n!} = “ (0. a_{2} a_{3} a_{4} \dots)_{!} ”$
where $a_{n} \in {0, \dots, n - 1}$ for all $n \geq 2$ . See also [2].

It's not hard to see that the representation terminates (that is $\exists N, \forall n \geq N, a_{n} = 0$ ) iff $r \in Q$ . Moreover one can show that $r \sim_{Q} s$ iff the representations of $r, s$ differ finitely (that is $\exists N, \forall n \geq N, a_{n} = b_{n}$ where $s = (0. b_{2} b_{3} \dots)_{!}$ ).

Thus one can define the function $g : R \to P (N \times N)$ via
$g (r) = {(n, a_{n}) ∣ n \geq 2} \subseteq N \times N$
In return, $\forall r, s \in R$ , $r \sim_{Q} s$ iff $| g (r) △ g (s) | < \infty$ . By a simple bijection $N \times N ≅ N$ as in Problems 1,2,3 above, we get $R / Q ≦ P (N) / fin$ as desired.

Here are some remarks.
(1) In general, whenever one can constructively show that $X / \sim ⪋ Y / \approx$ , they can then apply the standard Cantor–Schröder–Bernstein argument to find a constructive bijection $X / \sim ≅ Y / \approx$ . It follows that $| X / \sim | = | Y / \approx |$ constructively.
(2) The function $f : P (N) \to R$ constructed in Solution 1/2 has the property that whenever $A_{1} ≁_{fin} \dots ≁_{fin} A_{n} \in P (N)$ , the set ${f (A_{1}), \dots, f (A_{n})} \subseteq R$ is in fact $Q$ - linearly independent . One can find an uncountable family of such $f (A_{i}) \in R$ by using either of Problems 1,2,3 above. Thus constructively we've shown that $\dim_{Q} (R) \geq | R |$ . Contrast this with the fact that there exists no constructive $Q$ -basis of $R$ .
(3) With respect to the product-discrete topology on $P (N) ≅ 2^{N}$ , both $\sim_{fin}, \sim_{Q}$ are Borel equivalence relations , and the functions $f, g$ constructed are Borel reductions between them. In standard notation, $P (N) / fin ≅ R / Q$ can be instead written as $E_{0} \equiv_{B} E_{v}$ .
(4) There exists no constructive bijection $R ≅ R / Q$ . Assuming ${AD}^{L (R)}$ , one can in fact show that $| R | < | R / Q |$ holds in $L (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 $R$ is a set of the form ${x, x + a, x + 2 a}$ for some $a > 0$ . Construct a maximal subset $S \subseteq R$ without a 3-term arithmetic progression.