For the theorem,

Let $E$ be the set and suppose $G\subseteq E\times E$. Let $A=domG$ and $B=ranG$, then there exists a function $f:A\rightarrow B$ such that $f\subseteq G$.

The theorem imples Axiom of choice.

I'm proving the statement, but I think my proof is going wrong. So Could you tell me how can I correct the proof?

Proof) Need to show that arbitrary set E has a choice function $\gamma$.

Assume the theorem, and Let $E$ be a set and let $Q_D=\text{{$(D,d)|d\in D$}}$ for all $D \in \mathscr P'(E)$. Let $Q = \cup_{D\in \mathscr P'(E)} Q_D$

Then, $Q \subseteq E\times E$? I'm very confused.

If the above thing is right, let $A=domQ$ and $B=ranQ$. Then there exist a function $f:A\rightarrow B$ such that $f\subseteq Q$.

Since $Q = \cup_{D\in \mathscr P'(E)} Q_D$, $A = domQ = \mathscr P'(E)$

Since $f:A\rightarrow B$ is a fuction, there exist a $d\in D$ for all $D \in \mathscr P'(E)$ by F2.

Then, Let $\gamma: \mathscr P'(E) \rightarrow E$ such that $\gamma(D)=f(D)=d\in D$ for all $D \in \mathscr P'(E)$.

Hence, Axiom of choice holds


  • 1
    $\begingroup$ Do you mean to say $f\subseteq G$ in the first paragraph? $\endgroup$ – florence May 27 '17 at 3:59
  • 3
    $\begingroup$ Seeing as the axiom of choice can be stated in many different but equivalent forms, it might help if you told us the statement of the axiom of choice that you want to prove. $\endgroup$ – bof May 27 '17 at 4:02
  • $\begingroup$ The statement of axiom of choice is that " Every set has a choice function". so I want to show E has a choice function in the proof. $\endgroup$ – dlfjsemf May 27 '17 at 4:07
  • $\begingroup$ Is $E$ a set of nonempty sets? Otherwise the choice function won't make sense to be defined on $E$. $\endgroup$ – MaudPieTheRocktorate May 27 '17 at 4:32
  • $\begingroup$ E is just arbitrary set..could you tell me the reason why I'm wrong? :) $\endgroup$ – dlfjsemf May 27 '17 at 5:08

First, some unclarified assumptions, $\mathcal P'(E)$ is the set of non-empty subsets of $E$, and the axiom of choice states that $\mathcal P'(E)$ admits a choice function (when you say that $E$ has a choice function, you mean there is a function choosing from the elements of $E$, but it seems that you mean a function choosing from subsets of $E$).

The essence of your proof is correct, but some parts are a bit murky. Let's work backwards, okay?

Instead of using $E$, let's use $X$ for our set. This is important because mentally you want to aim for $E$ to be the set on which the relation $G$ is given, and you don't necessarily know that this would be $X$ itself.

We want a choice function from $\mathcal P'(X)$, so this means that it would be a function with domain $\mathcal P'(X)$ and its range would be a subset of $X$.

So if we want a set $E$ such that $f$ is a subset of $E\times E$, it means that $E$ has to include both $X$ and its power set. Therefore, taking $E=X\cup\mathcal P(X)$ would easily do the job.

Now, to simplify your definition, we can just define $G$ to be $\{(D,d)\mid d\in D\subseteq X\}$. Now you don't need to define $\gamma$ anymore, because $f$ is already a choice function.


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.