Relations on set A and conditions of existence of descending chains

Question

I am reading through the Elements of Set theory by Herbert Enderton and even though I have passed this exercise long ago,the more I look at my solution the less I believe it.

Problem goes like this:

For any relation R on some set A such that $(\forall x \in A)(\exists y \in A)yRx$ then there is a descending chain $f:\omega \to A$

My proof goes like this:

Since R is relation then its domain and range exist,due to definition of the relation we can conclude that $ran\;R=A$ thus we can conclude that $dom\; R^{-1}=A$.

Then by axiom of choice there is function whose domain is A and it is subset of $R^{-1}$,thus such function satisfies $x\;R^{-1}\;f(x)$,then we can conclude that $f(x)\;R\;x$

Then by recursion theorem there is function $h:\omega \to A$ such that : $$h(0)=x$$ $$h(n^+)=f(h(n))$$ and h is our descending chain,and thus it is proven.

I am not very sure about my argument regarding transition from relation to its inverse,so if anyone could confirm or disprove I would be grateful

Answer 1

Here is a sketch of a proof using the axiom of choice:

Let $R$ be a relation on $A$. For each $a \in A$, let $X_a = \{b \in A : b R a\}$. By the assumption on the relation $R$, $X_a \neq \emptyset$. Let $\mathcal{X} = \{X_a : a \in A\}$ ($\mathcal{A}$ is a set by the axiom of replacement). Since $\mathcal{X}$ is a family of nonempty sets, the axiom choice gives a choice function for $\mathcal{X}$, i.e. for all $X \in \mathcal{X}$, $h(X) \in X$.

Let $a_0 \in A$ be arbitrary. Let $f(0) = a_0$. By recursion, $f(n + 1) = h(X_{f(n)})$. This $f$ is your desired function.

---

Note that your statement above is called the axiom of dependent choice. Above is a proof of the axiom of dependent choice from the axiom of choice. The axiom of dependent is weaker than the axiom of choice.

Answer 2

Your proof is a bit jumbled. In its principle it is the same proof as sketched by William, but your proof is harder to read for two reasons.

1. You are using $f$ for the a choice function and $h$ is in fact the function you prove to exist. That's fine, but it is confusing to the reader.

2. The way you find the choice function is a bit cumbersome. You are correct that since $R^{-1}$ is a relation whose domain is $A$, there is a function which is a subset of $R^{-1}$ with domain $A$.

   It will be wise to note that this function is precisely a choice function from the family $\{\{y\in A\mid y\mathrel{R} x\}\mid x\in A\}$. So perhaps using the axiom of choice directly applied to this family of sets would have been clearer. And if not, then at least pointing out that the function chooses from such set, namely $f(x)\mathrel R x$.