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$.

  • $\begingroup$ Please make your question's body self-contained. $\endgroup$ – Asaf Karagila Mar 21 '16 at 19:09
  • $\begingroup$ Sorry? @AsafKaragila $\endgroup$ – rnbguy Mar 21 '16 at 19:15
  • $\begingroup$ Your question begins with "I am given this problem in my assignment". What is this problem? $\endgroup$ – Asaf Karagila Mar 21 '16 at 19:16
  • $\begingroup$ I gave the question in title. Ok, I am putting it the main body. $\endgroup$ – rnbguy Mar 21 '16 at 19:17
  • 1
    $\begingroup$ 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. $\endgroup$ – Asaf Karagila Mar 21 '16 at 19:17

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.

| cite | improve this answer | |
  • $\begingroup$ edited my question. can you check? $\endgroup$ – rnbguy Mar 21 '16 at 19:36
  • $\begingroup$ 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. $\endgroup$ – Asaf Karagila Mar 21 '16 at 21:04
  • $\begingroup$ 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. $\endgroup$ – rnbguy Mar 22 '16 at 4:45
  • $\begingroup$ You can, and you should. Yes. $\endgroup$ – Asaf Karagila Mar 22 '16 at 5:25
  • $\begingroup$ 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! $\endgroup$ – LAD Feb 20 '18 at 5:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.