# Axiom of choice is equivalent to every relation includes a function with the same domain

The axiom of choice asserts that for any set $X$ there exists a function $f : (2^X − \{\emptyset\}) \rightarrow X$ such that for any nonempty $A \subseteq X$, $f(A) \in A$. Show that this is equivalent to the assertion that every relation includes a function with the same domain.

I am given this problem in my assignment. My approach is following.

I have a set $X$. Then it has a choice function $g : \mathcal{P}(X) \setminus \emptyset \rightarrow X$. Suppose $X$ has a relation $R \subseteq X \times X$. $dom(R) \subseteq X$. Then the required function $f : dom(R) \rightarrow X$ is

$$f(x) = g(\{y\ |\ (x, y) \in R\})$$

Conversely, suppose $X \supseteq Y$ is a non-empty subset. Let $$R_Y = \{(x, y)\ |\ y \in Y, x \in Y, (p, q) \in R_Y \Rightarrow p = x\}$$

Then there is a function $f_Y : dom(R_Y) \rightarrow X$. But $dom(R_Y)$ is singleton from the definition of $R_Y$. Then $im(f_Y)$ is also singleton. We define our choice function as $f = \{(Y, y)\ |\ y \in im(f_Y)\}$

Are my arguments correct?

Edit.1: what I tried to do for converse is, for any subset $Y$, I construct a relation $Y_1 \times Y$ where $Y \supseteq Y_1 = \{y\}$. Then there is a function $f_Y : Y_1 \rightarrow Y$. Then if $f$ is my choice function I define $f(Y) = f_Y(y)$.

May be I should define $R_Y$ as

$$R_Y = \{(x, y)\ |\ y \in Y; x \in Y; (p, q), (p', q) \in R_Y \Rightarrow p = p'\}$$

I understand there may be multiple $R_y$'s. But can't I define a singleton set as $\{s\in S\ |\ a, b \in S \Rightarrow a = b\}$? This can be $\{s\}$ $\forall s \in S$. But isn't it a valid specification?

Edit.2: This is the final solution with the help from @Asaf.

• If we assume axiom of choice then for any $X$ there is a choice function $f : \mathcal{P}(X) \setminus \emptyset \rightarrow X$ such that $f(A) \in A$. Suppose $R$ is a relation between $P$ and $Q$. Then we have a choice function $f_Q$ for $Q$. Let $f_R(p) = f_Q(\{q\ |\ pRq\})$. The function $f_R : P \rightarrow Q$ and $dom(f_R) = dom(R)$. So this is our required function.

• Conversely, if every relation includes a function with same domain. Let $R$ be a relation between $\mathcal{P}(X) \setminus \emptyset$ and $X$ such that $aRb \Rightarrow b \in a$. Now $R$ includes a function $f : \mathcal{P}(X) \setminus \emptyset \rightarrow X$. Then $xRf(x) \Rightarrow f(x) \in x$. So $f$ is the choice function for $X$.

• Please make your question's body self-contained. – Asaf Karagila Mar 21 '16 at 19:09
• Sorry? @AsafKaragila – rnbguy Mar 21 '16 at 19:15
• Your question begins with "I am given this problem in my assignment". What is this problem? – Asaf Karagila Mar 21 '16 at 19:16
• I gave the question in title. Ok, I am putting it the main body. – rnbguy Mar 21 '16 at 19:17
• I know that you gave your question in your title. Which is how I was able to write an answer. But you should keep the body self-contained. The title is the title, it's a different part of your post. – Asaf Karagila Mar 21 '16 at 19:17

## 1 Answer

This depends on your formulation of the axiom of choice, since many different places formulate the axiom of choice differently. But it seems that you're using the formulation: "For every $X$, there is a choice function from $\mathcal P(X)\setminus\{\varnothing\}$."

Your first proof is correct. The second is not quite correct. First of all the definition of $R_Y$ is entirely unclear. But if I did understand it correctly, then you already had chosen $x\in X$ for defining $R_Y$. But which one? Presumably, there are many.

Instead you want to use the assumption. The assumption is that a relation can be reduced to a function with the same domain. Why not make that function your choice function? So what would the domain be? $\mathcal P(X)\setminus\{\varnothing\}$. Now come up with a relation with that domain, that any function that you can reduce from it would be a choice function.

• edited my question. can you check? – rnbguy Mar 21 '16 at 19:36
• Again. You are constructing relations on $Y$. The assumption means that there exists a function from that relation, but then you have to choose the function. Read my answer. Construct a relation whose domain is already the domain of the choice function that you're looking for. – Asaf Karagila Mar 21 '16 at 21:04
• Can I define a relation like this, $\{(A,a)\ |\ A \subseteq X, a \in X, a \in A\}$? Then the reduced function is the choice function. – rnbguy Mar 22 '16 at 4:45
• You can, and you should. Yes. – Asaf Karagila Mar 22 '16 at 5:25
• I'm unable to understand how you have/prove the assumption "a relation can be reduced to a function with the same domain" ? Please explain! – Le Anh Dung Feb 20 '18 at 5:26