# Maximal element of a linearly ordered set

• Mar 18th 2011, 01:53 PM
topsquark
Maximal element of a linearly ordered set
First, this is the definition of Zorn's Lemma in my text. (Just in case it's not a standard way of defining it.)
Quote:

If A is a non-empty partially ordered set such that every chain in A (a sequence $a_1 \leq a_2 \leq ~..~\leq a_n$ where $a_i \in A$) has an upper bound in A then A contains a maximal element.
The problem is:
Quote:

Let $(A, \leq )$ be a linearly ordered set. The immediate successor of $a \in A$ (if it exists) is the least element in the set $\{ x \in A | a < x\}$. Prove that if A is well ordered by $\leq$, then at most one element of A has no immediate successor.
So. The proof.

If $(A, \leq)$ is a linear order then by Zorn's Lemma all chains (a, b, ..., z) in A have a maximal element. Since all elements of A are comparable in a linearly ordered set (and therefore all elements of A form a single chain) then there exists a single element z in A such that a < z for all $a \in A$. Thus z has no immediate successor. That is $\{ x | z < x \}$ is empty.

I think the proof looks good, but the trouble is I have what I think is a counter-example. Define the set A to be the natural numbers, N, linearly ordered by the usual definition of $\leq$ on the real numbers. I can find no (infinite) chain in N that has a maximal element.

My proof evidently missed something, but I can't tell what is missing.

-Dan
• Mar 18th 2011, 04:01 PM
DrSteve
Quote:

Originally Posted by topsquark
If $(A, \leq)$ is a linear order then by Zorn's Lemma all chains (a, b, ..., z) in A have a maximal element.
-Dan

This very first sentence is incorrect. Zorn's Lemma does NOT say "for every linear ordered set every chain has a maximal element." It says "IF a linearly ordered set has that property, then..."

Your "counterexample" isn't a counterexample at all. The naturals do not satisfy the hypothesis of Zorn's Lemma. So Zorn's Lemma says NOTHING about the naturals with its usual order.
• Mar 18th 2011, 04:26 PM
topsquark
Quote:

Originally Posted by DrSteve
This very first sentence is incorrect. Zorn's Lemma does NOT say "for every linear ordered set every chain has a maximal element." It says "IF a linearly ordered set has that property, then..."

Your "counterexample" isn't a counterexample at all. The naturals do not satisfy the hypothesis of Zorn's Lemma. So Zorn's Lemma says NOTHING about the naturals with its usual order.

Oh dear. Now look what you've done. You're making me think...

Thanks for the help. (Handshake)
-Dan
• Mar 20th 2011, 11:35 AM
topsquark
This problem can't be as complicated as I am making it....

To recap:
Let A be a linearly ordered set, that is $(A, \leq )$. Assume further that $\leq$ well orders A.

My most recent attack on this is to note that A may be separated by $\{ x \in A| x \leq a \}$ and $\{ x \in A|a < x \}$. I need to show that there exists an element a of A that is maximal (and unique.) My idea is to show that there exists an a in A such that $\{ x \in A|a < x \}$ is empty. That means that a is maximal and since A is linearly ordered a is also unique.

It sounds good, but I keep getting gnarled up in the logic and arguing in circles. The "example set" I am working with here is the well ordered set of integers
1, 2, 3, 4, ...., -1, -2, -3, -4, ...., 0 (in order from left to right. It's a weird one, but it serves its purpose.)
I can easily "see" that my argument works, it's just that convincing myself isn't a proof.

-Dan
• Mar 20th 2011, 11:53 AM
Plato
Quote:

Originally Posted by topsquark
This problem can't be as complicated as I am making it....
The "example set" I am working with here is the well ordered set of integers
1, 2, 3, 4, ...., -1, -2, -3, -4, ...., 0 (in order from left to right. It's a weird one, but it serves its purpose.)

What is the exact statement of the 'root' question that you are working on?
• Mar 20th 2011, 01:18 PM
topsquark
Quote:

Originally Posted by Plato
What is the exact statement of the 'root' question that you are working on?

I mentioned it in the first post of the thread. There is a last part, all I have to do is show an example, but as soon as I have a proof for the first part the example should not be that difficult. Here is the whole original:
Quote:

Let $(A, \leq )$ be a linearly ordered set. The immediate successor of $a \in A$ (if it exists) is the least element in the set $\{ x \in A | a < x \}$. Prove that if A is well ordered by $\leq$, then at most one element of A has no immediate successor. Give an example of a linearly ordered set in which precisely two elements have no immediate successor.
-Dan
• Mar 20th 2011, 04:48 PM
Plato
Quote:

Originally Posted by topsquark
I mentioned it in the first post of the thread. There is a last part, all I have to do is show an example, but as soon as I have a proof for the first part the example should not be that difficult. Here is the whole original:

If $\left( {A, \ll } \right)$ is totally well ordered set-relation.
Suppose that $\alpha~\&~\beta$ are two maximal elements.
Because of the total order one of those precedes the other.
Let's say $\alpha\ll\beta$, thus $\{x\in A:\alpha\ll x\}$ is nonempty.
Doesn't well ordering give you a contradiction?
• Mar 20th 2011, 05:10 PM
topsquark
Quote:

Originally Posted by Plato
If $\left( {A, \ll } \right)$ is totally well ordered set-relation.
Suppose that $\alpha~\&~\beta$ are two maximal elements.
Because of the total order one of those precedes the other.
Let's say $\alpha\ll\beta$, thus $\{x\in A:\alpha\ll x\}$ is nonempty.
Doesn't well ordering give you a contradiction?

Oh for the love of... Thanks. (Bow)

-Dan