A description/proof of that for nonempty set with partial ordering with no minimal element, there is function from natural numbers set to set, for which image of number is larger than image of next number
Topics
About: set
The table of contents of this article
Starting Context
- The reader knows a definition of set.
- The reader knows a definition of partial ordering.
- The reader knows a definition of minimal element for partial ordering.
- The reader admits the recursion theorem for the natural numbers set.
Target Context
- The reader will have a description and a proof of the proposition that for any nonempty set with any partial ordering with no minimal element, there is a function from the natural numbers set to the set, for which the image of any number is larger than the image of the next number.
Orientation
There is a list of definitions discussed so far in this site.
There is a list of propositions discussed so far in this site.
Main Body
1: Description
For any set, \(S\), with any partial ordering, \(\lt\), with no minimal element, which means that for any element, \(p \in S\), there is an element, \(p' \in S\), such that \(p' \lt p\), there is a function, \(f: \omega \rightarrow S\) where \(\omega\) is the natural numbers set such that \(f (n + 1) \lt f (n)\) for any \(n \in \omega\).
2: Proof
There is the function, \(g: S \rightarrow Pow S, p \mapsto \{p' \in S\vert p' \lt p\} \neq \emptyset\). By the choice axiom 2), there is a function, \(h: S \rightarrow S, h (p) \in g (p)\). Let us take any \(p_0 \in S\). By the recursion theorem for the natural numbers set, there is a function, \(f: \omega \rightarrow S, f (0) = p_0, f (n + 1) = h (f (n))\). Then, \(h (f (n)) \in g (f (n))\), so, \(h (f (n)) = f (n + 1) \lt f (n)\).
