Maximal element of a linearly ordered set

Printable View

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

Any thoughts/contradictions? Thanks.
-Dan
March 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?
March 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
March 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?
March 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