# Well-Ordered Sets and Functions

I need some assistance with the following problems. I've come up with some ideas but may need some clarification.

1) Let $S$ be a well-ordered set.

a) Need to show $S$ has a first element.

Solution: We know that any subset of $S$ has a first element, and since $S$ $\subseteq$ $S$, then clearly $S$ must have its own first element.

b) Need to show that $S$ is linearly ordered.

c) Show that $S$ is order-complete; that is, every subset that is bounded above has a suprenum.

My intuition for this is to relate this to the Completeness Axiom of $\mathbb R$.

d) Let $A$ be a non-empty subset of $S$, and show $A$ is well-ordered using the same ordering.

2) Let $f:$ $A \rightarrow$ $B$ be a surjective function; show $\exists$ an injective function $g:$ $B \rightarrow$ $A$. (This would imply $|A| \geq |B|$).

-
For c), let $A$ be our bounded set, and let $U$ be the set of upper bounds of $A$. Then $U$ has a smallest element $b$. Show that $b$ is the required sup. –  André Nicolas Dec 13 '12 at 19:35

My answer to b) is as follows:

Let $x, y \in S$. Clearly {$x,y$} $\subseteq S$, and so {$x,y$} has a first element. If $x$ is the first element, then $x \leq y$. If $y$ is the first element, then $y \leq x$. Thus $x$ and $y$ are comparable, so $S$ is totally ordered.

My answer to d) is as follows:

Let $D \subseteq A \subseteq S$. This implies that $D \subseteq S$, and $D$ has a first element. Since any subset of $A$ has a first element, then $A$ is also well-ordered.'

Are these solutions valid?

-

For (a), (b) and (d), you took exactly the right approach.

For (c), if $T\subseteq S$ is bounded above, then let $B$ be the set of upper bounds of $T$ in $S$, so since $B$ is a non-empty subset of $S$, it has a first element, which is necessarily the least upper bound of $T$.

For (2), I'm assuming that $A$ is well-ordered (for if not, then the proposition need not hold). For each $b\in B$, surjectivity of $f:A\to B$ tells us there is some $a\in A$ such that $f(a)=b$--that is, $\{a\in A:f(a)=b\}$ is a non-empty subset of $A$ for each $b\in B$. Since $A$ is well-ordered, what does that let us say about $\{a\in A:f(a)=b\}$ for each $b\in B$? This will allow us to define an injection $g:B\to A$. (Let me know if you need more.)

-
My solutions for 1 are at the bottom. I think my answers for b) and d) are right then. Thank you! I will work on 2 for the hints you gave. Thank you! –  Julian Park Dec 13 '12 at 22:55
I am still having difficulty understanding what happens with the set {$a$ $\in$ $A$: $f(a) = b$}. What I know is that if we have 2 finite well-ordered sets, say $A$ and $B$, then $A\cong$B (order isomorphic) $\iff$ $A$ is equipotent with $B$... –  Julian Park Dec 13 '12 at 23:35
@Julian: $\{a\in A:f(a)=b\}$ is a non-empty subset of a well-ordered set, so it has a what kind of element? –  Brian M. Scott Dec 13 '12 at 23:56
Since it's a non-empty subset of a well-ordered set, it would imply that the set has a first element. –  Julian Park Dec 14 '12 at 0:03
Precisely so, @Julian! Then for each $b\in B$, we simply take $g(b)$ to be the first element of $\{a\in A:f(a)=b\}.$ To show that $g$ is injective, note that the sets $\{a\in A:f(a)=b_1\}$ and $\{a\in A:f(a)=b_2\}$ are disjoint if $b_1\neq b_2$, since $f$ is a function. –  Cameron Buie Dec 14 '12 at 1:00