3
$\begingroup$

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

  • 0
    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.2012-12-13

2 Answers 2

1

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?

1

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

  • 1
    @JulianPark: I just now realized the other answer was yours! Sorry to waste your time with stuff you'd already figured out. :P2012-12-18