Well ordered-set

• Mar 12th 2010, 10:32 AM
novice
Well ordered-set
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}$?
• Mar 12th 2010, 10:57 AM
clic-clac
Quote:

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.$
• Mar 12th 2010, 02:46 PM
novice
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.
• Mar 12th 2010, 04:00 PM
Drexel28
Quote:

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?
• Mar 13th 2010, 07:48 AM
novice
Quote:

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?
• Mar 13th 2010, 08:32 AM
novice
Quote:

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?

$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$
• Mar 13th 2010, 09:23 AM
clic-clac

Quote:

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.
• Mar 13th 2010, 09:32 AM
novice
Will be back later in the day. Currently have a commitment to fulfill. Thanks for the comment on the greatest element.
• Mar 13th 2010, 03:15 PM
novice
Quote:

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.

Quote:

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.