Set with Choice Function is Well-Orderable

From ProofWiki
Jump to navigation Jump to search


This article has been identified as a candidate for Featured Proof status.
In particular: I just believe this is a really elegant proof.
If you do not believe that this proof is worthy of being a Featured Proof, please state your reasons on the talk page.
To discuss this page in more detail, feel free to use the talk page.


Theorem

Let $S$ be a set.

Let there exist a choice function for $S$.


Then $S$ is well-orderable.


Proof

Let us define the notation:

$\map {\PP_{\ne \O} } S := \powerset S \setminus \set \O$

for the power set of $S$ without the empty set.


Let $C: \map {\PP_{\ne \O} } S \to S$ be a choice function for $S$.

Let $x \subseteq S$ be a subset of $S$.

From Subset is Element of Power Set we have:

$x \subseteq S \iff x \in \powerset S$


Let us define $g: \powerset S \to S$ as follows:

$\forall x \in \powerset S: \map g x := \begin {cases} x \cup \paren {\map C {S \setminus x} } & : x \ne S \\ S & : x = S \end {cases}$

where $S \setminus x$ denotes the difference between $S$ and $x$.

We note that when $x \ne S \iff S \setminus x \ne \O$, hence $\map C {S \setminus x}$ is always defined in the above.


Thus:

$\map g S = S$

and for an arbitrary proper subset $x$ of $S$, $\map g x$ adds to $x$ exactly $1$ element of $S$ which is not in $x$.

That is:

$g$ is a slowly progressing mapping

and:

$S$ is the unique fixed point of $g$.

Hence $S$ fulfils the assumptions of Set with Slowly Progressing Mapping on Power Set with Self as Fixed Point is Well-Orderable.

The result follows.

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Set_with_Choice_Function_is_Well-Orderable&oldid=681512"