Axiom Of Choice

Description:

Content:

A proof that Form 314 (For every set $X$ and every permutation $\pi$ on $X$ there are two reflections $\rho$ and $\sigma$ on $X$ such that $\pi =\rho\circ\sigma$ and for every $Y\subseteq X$ if $\pi[Y]=Y$ then $\rho[Y]=Y$ and $\sigma[Y]=Y$ .(A reflection is a permutation $\phi$ such that $\phi^2$ is the identity.) implies Form 119 ( $C(\aleph_{0}$ ,uniformly orderable with order type of the integers)).

Form 314 (For every set $X$ and every permutation $\pi$ on $X$ there are two reflections $\rho$ and $\sigma$ on $X$ such that $\pi =\rho\circ\sigma$ and for every $Y\subseteq X$ if $\pi[Y]=Y$ then $\rho[Y]=Y$ and $\sigma[Y]=Y$ .(A reflection is a permutation $\phi$ such that $\phi^2$ is the identity.) implies Form 119 ( $C(\aleph_{0}$ ,uniformly orderable with order type of the integers)).

Assume that $B=\{A_i: i\in\omega\}$ is a denumerable set of denumerable sets and $f$ is a function defined on $\omega$ such that $\forall i\in\omega$ , $f(i)$ is an ordering of $A_i$ with order type that of the integers. We want to construct a choice function $g$ for $B$ so we may assume that the elements of $B$ are pairwise disjoint.

Let $\eta$ be the permutation of $\bigcup B$ defined by $\eta(a) =$ the immediate successor of $a$ under the ordering $f(A_i)$ where $A_i$ is the unique element of $B$ such that $a\in A_i$ . By Form 314, $\eta$ is the product of two reflections: $\eta = \phi\circ\psi$ .

Fix an $i\in\omega$ and for each permutation $\beta$ of $\bigcup B$ , let $\beta' = \beta\mid A_i$ . Then $\eta' = \phi'\circ\psi'$ and $\phi'$ and $\psi'$ are reflections. We complete the proof by showing that exactly one of $\phi'$ or $\psi'$ has exactly one fixed point. (This fixed point will be $g(A_i)$ .)

Since $\phi'$ and $\psi'$ are both reflections, $\phi'$ and $\psi'$ can both be written as a product of disjoint cycles, $\phi' = \prod_{i\in I}(s_i,t_i)$ and $\psi' = \prod_{j\in J}(c_j,d_j)$ . Assume that $A_i = \{\ldots,a_{-1},a_0,a_1,a_2,\ldots\}$ where the elements are listed in the order determined by the ordering $f(A_i)$ . Then $\eta'$ is the infinite cycle $\eta' = (\ldots,a_{-1},a_0,a_1,a_2,\ldots)$ . Let $r$ be the smallest positive integer such that for some integer $k$ the transposition $(a_k,a_{k+r})$ is one of the $(s_i,t_i)$ or one of the $(c_j,d_j)$

We first show that $r=1$ . Assume that $r>1$ and that $(a_k,a_{k+r})$ is one of the $(c_j,b_j)$ . (The argument is similar if $(a_k,a_{k+r})$ is one of the $(s_i,t_i)$ .) This means that $\psi'(a_k) = a_{k+r}$ .Since $\eta'(a_k) = a_{k+1}$ (and $r\ne 1$ ), $\phi'(a_{k+r})$ must be $a_{k+1}$ , hence the transposition $(a_{k+1},a_{k+r})$ must be one of the $(s_i,t_i)$ . This contradicts the definition of $r$ .

Assume that $(a_k,a_{k+1})$ is one of the $(c_j,d_j)$ . (The argument is similar if $(a_k,a_{k+1})$ is one of the $(s_i,t_i)$ .) This means that $\psi'(a_k)=a_{k+1}$ . Since $\eta'(a_k) = a_{k+1}$ we conclude that $a_{k+1}$ must be a fixed point of $\phi'$ . Further, since $\psi'(a_{k+1})=a_k$ and $\eta'(a_{k+1}) = a_{k+2}$ we conclude that $\phi'(a_k) = a_{k+2}$ ,that is, $(a_k,a_{k+2})$ is one of the $(s_i,t_i)$ . By this last conclusion, $\psi'(a_{k+2})=a_k$ . It follows that $\psi'(a_{k-1})=a_{k+2}$ , that is $(a_{k-1},a_{k+2})$ is one of the $(c_j,d_j)$ . Continuing in this way, we see that for every natural number $j$ , $\psi'$ interchanges $a_{k-j}$ and $a_{k+j+1}$ and $\phi'$ interchanges $a_{k-j}$ and $a_{k+j+2}$ . Therefore, $\psi'$ has no fixed points and $\phi'$ has exactly one fixed point.

Howard-Rubin number: 124

Type: Proof

Back

Notes