Well ordered-set

**novice** · March 12th 2010, 09:32 AM

Prove that for each integer $m$ , the set $S=\{i \in \mathbb{Z}: i\geq m \}$ is well-ordered. [Hint: For every subset $T$ of $S$ , either $T \subseteq N$ or $T-N$ is a finite nonempty set.]

I know how to prove this, but I have a simple question.

Question: Did the author mean $T \subseteq \mathbb{Z}$ or $T-\mathbb{Z}$ ?

**clic-clac** · March 12th 2010, 09:57 AM

Originally Posted by novice

Question: Did the author mean $T \subseteq \mathbb{Z}$ or $T-\mathbb{Z}$ ?

I guess no. $\mathbb{N}$ is well ordered while $\mathbb{Z}$ is not: $T\subseteq\mathbb{Z}$ does not help. Furthermore $T-\mathbb{Z}=\emptyset.$

**novice** · March 12th 2010, 01:46 PM

There is no mistake that the author meant it $T \subseteq \mathbb{N}$ or $T-\mathbb{N}$ . He was trying to make the set either a set of all positive integers or a set of all non-positive integers.

$T-\mathbb{Z}$ does not make sense because it suggests that $T \cap \mathbb{Z}^c = \emptyset$ , which is impossible.

**Drexel28** · March 12th 2010, 03:00 PM

Originally Posted by novice

$T-\mathbb{Z}$ does not make sense because it suggests that $T \cap \mathbb{Z}^c = \emptyset$ , which is impossible.

What?? $T\subseteq\mathbb{Z}\implies \mathbb{Z}'\subseteq T'\implies T\cap \mathbb{Z}'\subseteq T\cap T'=\varnothing\implies T\cap\mathbb{Z}'=\varnothing$ .

Why is that impossible?

**novice** · March 13th 2010, 06:48 AM

Originally Posted by Drexel28

What?? $T\subseteq\mathbb{Z}\implies \mathbb{Z}'\subseteq T'\implies T\cap \mathbb{Z}'\subseteq T\cap T'=\varnothing\implies T\cap\mathbb{Z}'=\varnothing$ .

Why is that impossible?

Sorry for causing so much confusion. I raised a very stupid question and then realized that asked too soon.

Well, since we are at it, if you don't mind I would like to show you my proof so that you can evaluate whether it's legitimate.

Here we go:

We are asked to prove that for each integer $m$ , the set $S=\{i \in \mathbb{Z}: i\geq m\}$ is a well-ordered set.

Proof:

Let $T$ be a nonempty subset of $S$ . So we may say that $T \subseteq \mathbb{N}$ or $T-\mathbb{N}$ . In other words,

$S=T \cup (T \cap N^c)$ . Now we have inclusively in S, two separate sets, namely $T \subseteq S$ and $T \cap \mathbb{N}^c \subseteq S$

Case 1: Consider $T \subseteq S \subseteq \mathbb{N}$ . In this case, since $T \subseteq N$ , we know by Well-ordering theorem that T is well-ordered.

Case 2: $T \cap \mathbb{N}^c$ . We will take advantage of the symmetry of $\mathbb{Z}$ about zero. Now let

$A=\{n+1: -n\in T\cap \mathbb{N}^c\}$ for every integer $n$ .

Since $A$ is a set of positive integers, again by Well ordering theorem, $A$ has a least element $m$ . Hence
$m \leq n$ for every $n \in A$ . Therefore,

$-m \in T \cap \mathbb{N}^c$ and $-m\geq -n$ for every $n\in T \cap \mathbb{N}^c$ . So by the Well-ordering theorem, $T\cap \mathbb{N}^c$ has a greatest element $-m$ ; therefore, $T \cap \mathbb{N}^c$ is also well-ordered.

Consequently, $S=T \cup (T \cap N^c)$ is well-ordered.

Question: I am trying to avoid having to deal with the zero, I contrived

$A=\{n+1: -n\in T\cap \mathbb{N}^c\}$ . Is this legitimate?

**novice** · March 13th 2010, 07:32 AM

Originally Posted by Drexel28

What?? $T\subseteq\mathbb{Z}\implies \mathbb{Z}'\subseteq T'\implies T\cap \mathbb{Z}'\subseteq T\cap T'=\varnothing\implies T\cap\mathbb{Z}'=\varnothing$ .

Why is that impossible?

Sorry again, I did not answer your question.

$T\cap\mathbb{Z}^c = \emptyset$ is impossible because T $\subseteq \mathbb{Z}$ and $T \not = \emptyset$ .

$T$ is a nonempty subset of S with a least element. If $T$ is empty, we would have nothing to prove.

To say $T\cap\mathbb{Z}^c = \emptyset$ is to say $T = \emptyset$

**clic-clac** · March 13th 2010, 08:23 AM

I answer about your proof.

Originally Posted by novice

Let $T$ be a nonempty subset of $S$ . So we may say that $T \subseteq \mathbb{N}$ or $T-\mathbb{N}$

Be careful, the underlined sentence has no meaning. What was proposed is : we have either ( $T\subseteq \mathbb{N}$ ) or ( $T-\mathbb{N}$ is finite and non-empty).

Your first case proof is correct, but try again for the second one. You cannot use $\mathbb{Z}$ symmetry about $0,$ see that what you wrote applies for $S=\mathbb{Z}:$ you did not use the fact that S has a minimal element and therefore $T\cap\mathbb{N}^c$ is finite (and of course a finite set of integers is well ordered by the restriction of the natural order).

Recall that a well ordered set is an ordered set whose any non-empty subset has a minimal element; having a maximal element does not make your order be a well order.

**novice** · March 13th 2010, 08:32 AM

Will be back later in the day. Currently have a commitment to fulfill. Thanks for the comment on the greatest element.

**novice** · March 13th 2010, 02:15 PM

Originally Posted by clic-clac

...see that what you wrote applies for $S=\mathbb{Z}:$ you did not use the fact that S has a minimal element and therefore $T\cap\mathbb{N}^c$ is finite (and of course a finite set of integers is well ordered by the restriction of the natural order).

I understand that we can prove it by Principle of Transfinite Induction, which says

Let $T$ be a subset of a well-ordered set $S$ with the following properties:
(1) $m \in S$ ,
(2) $s(a) \subseteq S \Rightarrow a \in S$
where $m$ is the least element in $S$ , and $s(a)$ the set of elements precede $a$ .

However, I am still at the elementary level where the chapter has not cover Principle of Transfinite Induction. So I would like to do my best without using it and see if I could prove it at my level.

Originally Posted by clic-clac

Recall that a well ordered set is an ordered set whose any non-empty subset has a minimal element; having a maximal element does not make your order be a well order.

I was being too creative that I twisted the principle. Yes, it's laughable.

Let's try again:

We have proved that since $T$ being a nonempty subset of $S$ and that $T \subseteq \mathbb{N}$ , it follows that $T$ has a least element $t_0$ ; therefore, $T$ is well-ordered.

Now in case 2: $T-\mathbb{N}$ where $T-\mathbb{N} \subseteq S$ and $T-\mathbb{N} \not = \emptyset$ .

Suppose that none of the least element $t_0 \in T \subset \mathbb{N}$ is the first element $m$ of $S$ , then $t_0 \not \in T- \mathbb{N}, t_0-1 \in T-\mathbb{N}$ and $m \in T-\mathbb{N}$ . Hence $T-\mathbb{N}$ has a least element $m$ and the largest element $t_0-1$ . As a consequence, $T-\mathbb{N}$ is a finite set of integers. Since every nonempty finite set of real numbers is well-ordered, T-N is well-ordered, so is $S$ .

I hope it works this time.

Thread: Well ordered-set

LinkBack

Thread Tools

Display

Well ordered-set

Similar Math Help Forum Discussions

A well-ordered set

Ordered pair

Well ordered set

Set ordered

How many different ordered pairs?

Search Tags