Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|$).

share|cite|improve this question
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?

share|cite|improve this answer

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.)

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.