0
$\begingroup$

I'd like to know if my proof is correct or incorrect in the following.

Given definition of Axiom of Choice (AoC): The direct product of a family of non-empty sets indexed by a non-empty set is non-empty.

Show that the Axiom of Choice is equivalent to the statement that every set has a choice function.

(Choice Function => AoC):

Suppose every set has a choice function.

Let S be a set, and fix a natural number n.

Let $$ I = \{1,2,....,n\} $$ and let $\mathbf A$ be a family of non-empty subsets of S sets indexed over I.

$$ \mathbf A = \{A_1, A_2, ... , A_n\} $$

The task is to show that the direct product over sets in $\mathbf{A}$ is non-empty. This will be shown if an element of this set can be produced.

Let $$ D = A_1 \times A_2 \times ... \times A_n $$

By supposition, this set has a choice function $f$ defined over non-empty subsets $X$ of $D$ with the following:

$f: X \to D$ such that $f(X)∈X$ for all subsets $X$.

So, $f(X) ∈ X$ $\Rightarrow$ $f(X) ∈ D$.

So, $D$ is non-empty.

(Show AoC => Choice Function):

Suppose the Axiom of Choice, let S be a set, and fix a natural number n.

Let $$ I = \{1,2,....,n\} $$ and let

$$ \mathbf{A} = \{A_1,A_2,....,A_n \} $$

be a family of non-empty subsets of S indexed over I.

Let $$ D = A_1 \times A_2 \times ... \times A_n $$

By the Axiom of choice, $D$ is non-empty.

Let $y ∈ D$ and define a function $f: D \to D$ by $f(x) = y$ for all elements $x ∈ D$.

(So, every element of D is mapped to this fixed element $y$.)

So, $f(x)∈D$ for all $x∈ D$.

In other words, $f$ defines a choice function on $D$.

So, assuming the Axiom of Choice implies that $S$ has a choice function defined on its non-empty subsets.

$\endgroup$
  • 1
    $\begingroup$ Your choice function -> AoC argument looks wrong to me. 'By supposition, this set has a choice function defined over non-empty subsets', but you haven't shown that there are any non-empty subsets of D! That is, after all, the thing you're trying to prove. $\endgroup$ – Steven Stadnicki Jul 19 '17 at 0:18
  • 2
    $\begingroup$ Also, you index over 'finite' products $A_1\ldots A_n$, but that doesn't take AC; the non-emptyness of a finite product can be proven in ZF. Choice is only relevant for infinite products. $\endgroup$ – Steven Stadnicki Jul 19 '17 at 0:20
  • $\begingroup$ For some basic information about writing math at this site see e.g. here, here, here and here. $\endgroup$ – Martin Sleziak Sep 4 '17 at 6:04
  • $\begingroup$ The set-theoretic def'n of $\prod_{j\in J}A_j$ is the set of functions from $J$ into $\cup \{A_j:j\in J\}$ that satisfy $\forall j\in J\;(f(j)\in A_j). $ $\endgroup$ – DanielWainfleet Sep 4 '17 at 8:28
2
$\begingroup$

You are working only with finite products, and this hold in general. In the Choice Function $\Rightarrow$ AoC direction you don't know if $D$ is nonempty, that is what you are trying to pare working only with finite products, and this hold in general. In the AoC $\Rightarrow$ Choce Function direction you need a choice function on $\mathcal{A},$ not in $D.$ Moreover, I think we need to clarify some definitions.

First one definition

Definition: Let $\mathcal{A}$ be a nonempty collection os sets. A surjective function $f$ from some set $J$ to $\mathcal{A}$ is called an indexing function for $\mathcal{A}.$ $J$ is called the index set. The collection $\mathcal{A},$ together with $f,$ is called an indexed family of sets.

I'll use your definition of axiom of choice.

Axiom of choice: For any indexed family $\{ A_\alpha \}_{\alpha \in J}$ of nonempty sets, with $J \neq 0,$ the cartesian product $$ \prod_{\alpha \in J} A_\alpha$$ is not empty. Recall that the cartesian product is the set of all functions $$ \mathbf{x}:J \to \bigcup_{\alpha \in J}A_\alpha$$ such that $\mathbf{x}(\alpha) \in A_\alpha$ for all $\alpha \in J.$

Now,

Existence of a choice function: Given a collection $\mathcal{A}$ of nonempty sets, there exists a function $$ c: \mathcal{A} \to \bigcup_{A \in \mathcal{A}}A$$ such that $c(A)$ is an element of $A: c(A)\in A$ for each $A \in \mathcal{A}.$

Axiom of choice $\Rightarrow$ Existence of choice function.

We are assuming that for any indexed family $\{ A_\alpha \}_{\alpha \in J}$ of nonempty sets, with $J \neq 0,$ the cartesian product $ \prod_{\alpha \in J} A_\alpha$ is not empty. Let $\mathcal{A}$ be a collection of nonempty sets. We have to prove that there exists a function $ c: \mathcal{A} \to \bigcup_{A \in \mathcal{A}}A$ such that $c(A) \in A$ for each $A \in \mathcal{A}.$ We first index $\mathcal{A}$: let $J=\mathcal{A}$ and $f:\mathcal{A} \to \mathcal{A}$ given by $f(A)=A.$ Then $\{A\}_{A \in \mathcal{A}}$ is an indexed family of sets, so we can consider its cartesian product $\prod_{A \in \mathcal{A}}A.$ By hypothesis, this product is nonempty, so there exists a function $$ \mathbf{x}: \mathcal{A} \to \bigcup_{A \in \mathcal{A}}A$$ such that $\mathbf{x}(A) \in A$ for each $A \in \mathcal{A}.$ Then $c=\mathbf{x}$ is the function we were looking for.

Existence of choice function $\Rightarrow$ Axiom of choice

Now we are assuming that the existence of choice function, and let $\{A_\alpha \}_{\alpha \in J}$ be an indexed family of nonempty sets, with $J \neq 0.$ This means that there is a nonempty collection of sets $\mathcal{A}$ and there is an indexing (i.e. surjective) function $f:J \to \mathcal{A}$ such that $f(\alpha)=A_\alpha \in \mathcal{A}$ for each $\alpha \in J.$ By the existence of choice function, there is a function $c:\mathcal{A} \to \bigcup_{A \in \mathcal{A}}A$ such that $c(A) \in A$ for each $A \in \mathcal{A}.$ Thus the function $$ \mathbf{x}:= c \circ f : J \to \mathcal{A} = \bigcup_{\alpha \in J}A_\alpha$$ satisfies $\mathbf{x}(\alpha)=c(f(\alpha))=c(A_\alpha) \in A_\alpha$ for each $\alpha \in J,$ so the product $\prod_{\alpha \in J}A_\alpha$ is nonempty.

$\endgroup$
  • $\begingroup$ Thank you for the feedback; I appreciate it! Btw, this is just for my own interest; not for a class or anything... $\endgroup$ – user2192320 Jul 19 '17 at 14:13
  • $\begingroup$ A member of $P=\prod_{a\in A}A_a$ is a choice-function for $\{A_a:a\in A\}$ by the def'n of $P$ and the def'n of a choice-function. So the proposition is essentially a tautology. $\endgroup$ – DanielWainfleet Jul 19 '17 at 16:35
  • $\begingroup$ Your answer is clear, full of relevant definitions, and concise! $\endgroup$ – MadnessFor MATH Feb 23 '18 at 7:42

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.