|
|
|
Viewing Version
1
of
'surjection and axiom of choice'
|
[ view 'surjection and axiom of choice'
|
back to history
]
| Title of object: |
surjection and axiom of choice |
| Canonical Name: |
SurjectionAndAxiomOfChoice |
| Type: |
Derivation |
| Created on: |
2009-01-17 21:27:33 |
| Modified on: |
2009-01-17 21:27:33 |
| Classification: |
msc:03-00 |
Preamble:
\usepackage{amssymb,amscd}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{mathrsfs}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
\usepackage{amsthm}
% making logically defined graphics
\usepackage{xypic}
\usepackage{pst-plot}
% define commands here
\newcommand*{\abs}[1]{\left\lvert #1\right\rvert}
\newtheorem{prop}{Proposition}
\newtheorem{thm}{Theorem}
\newtheorem{ex}{Example}
\newcommand{\real}{\mathbb{R}}
\newcommand{\pdiff}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\mpdiff}[3]{\frac{\partial^#1 #2}{\partial #3^#1}} |
Content:
In this entry, we show the statement that
\begin{quote}
(*) every surjection has a left inverse
\end{quote}
is equivalent to the axiom of choice (AC).
\begin{prop} AC implies (*). \end{prop}
\begin{proof}
Let $f:A\to B$ be a surjection. Then the set $C:=\lbrace f^{-1}(y)\mid y\in B\rbrace$ partitions $A$. By the axiom of choice, there is a function $g:C\to \bigcup C$ such that $g(f^{-1}(y))\in f^{-1}(y)$ for every $y\in B$. Since $\bigcup C=A$, $g$ is a function from $C$ to $A$. Define $h:B\to A$ by $h(y)=g(f^{-1}(y))$. Then $h(y)\in f^{-1}(y)$, and therefore $(f\circ h)(y)=f(h(y))=y$, implying that $f$ has a left inverse.
\end{proof}
\begin{prop} (*) implies AC. \end{prop}
Before proving this, let us remark that, in the axiom of choice, the collection $C$ of non-empty sets, there is no assumption that the sets in $C$ be pairwise disjoint. The statement
\begin{quote} (**) given a set $C$ of pairwise disjoint non-empty sets, there is a choice function $f:C\to \bigcup C$
\end{quote}
seemingly weaker than AC, turns out to be equivalent to AC, and we will prove this fact first.
\begin{proof}
Obviously AC implies (**). Conversely, assume (**). Let $C$ be a collection of non-empty sets. We assume $C\ne \varnothing$. For each $a\in C$, define a set $A_a:=\lbrace (x,a)\mid x\in a\rbrace$. Since $a\ne \varnothing$, $A_a\ne \varnothing$. In addition, $A_a\cap A_b= \varnothing$ iff $a\ne b$ (true since elements of $A_a$ and elements of $A_b$ have distinct second coordinates). So the collection $D:=\lbrace A_a\mid a\in C\rbrace$ is a set consisting of pairwise disjoint non-empty sets. By (**), there is a function $f:D\to \bigcup D$ such that $f(A_a)\in A_a$ for every $a\in C$. Now, define two functions $g: C\to D$ and $h:\bigcup D\to \bigcup C$ by $g(a)=A_a$ and $h(x,a)=x$ Then, for any $a\in C$, we have $(h\circ f \circ g)(a)=h(f(A_a))$. Since $f(A_a)\in A_a$, its first coordinate is an element of $a$. Therefore $h(f(A_a))\in a$, and hence $h\circ f\circ g$ is the desired choice function.
\end{proof}
\begin{proof}[Proof of Propositon 2] We show that (*) implies (**), and since (**) implies AC as shown above, the proof of Proposition 2 is then complete.
Let $C$ be a collection of pairwise disjoint non-empty sets. Each element of $\bigcup C$ belongs to a unique set in $C$. Then the function $g:\bigcup C \to C$ taking each element of $\bigcup C$ to the set it belongs in $C$, is a well-defined function. It is clearly surjective. Hence, by assumption, there is a function $f:C\to \bigcup C$ such that $g\circ f=1_C$. For each $x\in C$, $g(f(x))=x$, which is the same as saying that $f(x)$ is an element of $x$ by the definition of $g$.
\end{proof} |
|
|
|
|
|
