2
$\begingroup$

Here is the excerpt from the textbook A Course in Mathematical Analysis by Prof D. J. H. Garling.

enter image description here

So I have the Theorem 1:

Given a set $A\neq\varnothing$, a mapping $\varphi:A\to P(A )\setminus \{\varnothing\}$, and $\bar{a}\in A$. Then there exists a sequence $$(a_{n})_{n\in \mathbb{N}}$$ such that $a_{0}=\bar{a}$ and $a_{n+1}\in \varphi(a_{n})$ for all $n\in \mathbb{N}$

Axiom of Choice:

Given a collection $A$ of nonempty sets, there exists a function $$c: A \to \bigcup_{A_{i} \in A}A_{i}$$ such that $c(A_{i})\in A_{i}$ for all $A_{i} \in A$.

Axiom of Dependent Choice:

Given a nonempty set $A$ and a binary relation $\mathcal{R}$ on $A$ such that for all $a\in A$, there exists $b\in A$ such that $a\mathcal{R}b$. There exists a sequence $$(a_{n})_{n\in \mathbb{N}}$$ such that $a_{n}\mathcal{R}a_{n+1}$ for all $n \in \mathbb{N}$.

The author states that The axiom of dependent choice states that this [Theorem 1] is always possible. But I can only infer Theorem 1 from Axiom of Choice, not from Axiom of Dependent Choice. Below is how I did it.

Using Axiom of Choice for the collection $P(A)\setminus \{\varnothing\}$ of nonempty sets, then there exists a choice function $$\varphi':P(A)\setminus \{\varnothing\} \to A$$ such that $\varphi'(X)\in X$ for all $X\in P(A)\setminus \{\varnothing\}$.

Let $\bar{\varphi}=\varphi'\circ \varphi:A\to A\implies\bar{\varphi}(a)=\varphi'(\varphi(a))\in \varphi(\bar{a})$ for all $a\in A$

To sum up, we have $\bar{\varphi}:A\to A$ and $\bar{a}\in A$. Applying Recursion Theorem, we get a sequence $$(a_{n})_{n\in \mathbb{N}}$$ such that $a_{0}=\bar{a}$ and $a_{n+1}=\bar{\varphi}(a_{n})\in\varphi(a_{n})$ for all $n\in \mathbb{N}$. So this $(a_{n})_{n\in \mathbb{N}}$ is the required sequence.

I would like you to check my above proof and check whether it is possible for Axiom of Dependent Choice to imply Theorem 1.

Many thanks for your help!

$\endgroup$
2

2 Answers 2

Reset to default
3
$\begingroup$

Here is how I would think about the problem:

Let $T$ be the set of all finite functions $$ s \colon n \to A $$ such that $n \in \mathbb N$, $s(0) = \bar{a}$ and, for all $i +1 < n$, $$ s(i+1) \in \phi(s(i)). $$ Let $R \subseteq T \times T$ be given by $$ R = \{(s,t) \in T^2 \mid t \text{ is a proper end-extension of } s \} = \{ (s,t) \in T^2 \mid s \subsetneq t \} $$

$R$ satisfies the requirement of DC (since $\phi(a) \neq \emptyset$ for all $a \in A$). Hence there is an infinite sequence (branch) $(s_n \mid n \in \mathbb N)$ through $T$ such that for all $m < n \in \mathbb N \colon s_m \subsetneq s_n$. Let $s := \bigcup_{n \in \mathbb N} s_n$. For each $k \in \mathbb N$ let $a_k := s(k)$. Then $(a_k \mid n \in \mathbb N)$ is as desired.

$\endgroup$
17
  • $\begingroup$ The above also suggest how you can reformulate DC into an equivalent statement that is a generalization of Kőnig's lemma. I find that reformulation much easier to work with in practice. (Mind you: There is a good chance this is only true because I've been inflicted with the 'just build a search tree' virus of inner model theory.) $\endgroup$
    – Stefan Mesken
    Feb 23, 2018 at 13:55
  • 1
    $\begingroup$ To some extent, the tree variant is the clearer version of DC. The reason is that it's easy to translate it into pretty much every other variant. $\endgroup$
    – Asaf Karagila ♦
    Feb 23, 2018 at 14:50
  • 1
    $\begingroup$ @leanhdung No, it's $s \colon n \to A$ -- they are functions with finite domain. (But you should note that, in my notation, $n = \{0,1, \ldots, n-1 \}$ -- that's standard among set theorists but maybe not among other mathematicians.) $\endgroup$
    – Stefan Mesken
    Feb 24, 2018 at 8:10
  • 1
    $\begingroup$ @leanhdung At that point I'm not making any choices -- I simply collect all of those sequences into a set (a priori it could be that there just aren't that many such sequences). Then, in a second step, I use DC to show that not only are there infinitely many such sequences -- there is even an infinite 'chain' (a branch) of them. This may not be true in the absence of DC. (Side note: I usually don't take a stance on the 'philosophical truth' of axioms but I must say -- to me DC seems 'true', it's almost mind bending to me to imagine a situation in which it could possibly fail.) $\endgroup$
    – Stefan Mesken
    Feb 24, 2018 at 10:23
  • 1
    $\begingroup$ Now I got that point, but i'm still not sure how $R$ satisfies the requirement of DC i.e for all $s\in T$, there exists $s'\in T$ such that $s\subsetneq s'$. Please check my reasoning: 1. Assume $s: n\to A$ such that $s\in T$, let $s': n+1\to A$ such that $s'(x)=s(x)$ for all $x\leqslant n-1$ and $s'(n)\in \phi(s(n-1))\implies s'\in T$ and $s'\subsetneq s$. $\endgroup$
    – Akira
    Feb 26, 2018 at 3:48
0
$\begingroup$

Let $\mathcal R =\{ (a,b) \in A \times A \mid a,b \in A \text{ and } b \in \phi(a) \}$, then $\mathcal R$ satisfies DC's requirement. Hence there is an infinite sequence (branch) $(a_n \mid n \in \mathbb N)$ through $A$ such that $a_{n+1} \in \phi(a_n)$ for all $n \in \mathbb N$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .