1. ## Well ordered-set

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

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

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

2. Originally Posted by novice Question: Did the author mean $\displaystyle T \subseteq \mathbb{Z}$ or $\displaystyle T-\mathbb{Z}$?
I guess no. $\displaystyle \mathbb{N}$ is well ordered while $\displaystyle \mathbb{Z}$ is not: $\displaystyle T\subseteq\mathbb{Z}$ does not help. Furthermore $\displaystyle T-\mathbb{Z}=\emptyset.$

3. There is no mistake that the author meant it $\displaystyle T \subseteq \mathbb{N}$ or $\displaystyle 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.

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

4. Originally Posted by novice $\displaystyle T-\mathbb{Z}$ does not make sense because it suggests that $\displaystyle T \cap \mathbb{Z}^c = \emptyset$, which is impossible.
What?? $\displaystyle 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?

5. Originally Posted by Drexel28 What?? $\displaystyle 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 $\displaystyle m$, the set $\displaystyle S=\{i \in \mathbb{Z}: i\geq m\}$ is a well-ordered set.

Proof:

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

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

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

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

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

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

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

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

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

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

6. Originally Posted by Drexel28 What?? $\displaystyle 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?

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

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

To say $\displaystyle T\cap\mathbb{Z}^c = \emptyset$ is to say $\displaystyle T = \emptyset$ Originally Posted by novice Let $\displaystyle T$ be a nonempty subset of $\displaystyle S$. So we may say that $\displaystyle T \subseteq \mathbb{N}$ or $\displaystyle T-\mathbb{N}$
Be careful, the underlined sentence has no meaning. What was proposed is : we have either ($\displaystyle T\subseteq \mathbb{N}$) or ($\displaystyle T-\mathbb{N}$ is finite and non-empty).

Your first case proof is correct, but try again for the second one. You cannot use $\displaystyle \mathbb{Z}$ symmetry about $\displaystyle 0,$ see that what you wrote applies for $\displaystyle S=\mathbb{Z}:$ you did not use the fact that S has a minimal element and therefore $\displaystyle 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.

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

9. Originally Posted by clic-clac ...see that what you wrote applies for $\displaystyle S=\mathbb{Z}:$ you did not use the fact that S has a minimal element and therefore $\displaystyle 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 $\displaystyle T$ be a subset of a well-ordered set $\displaystyle S$ with the following properties:
(1) $\displaystyle m \in S$,
(2)$\displaystyle s(a) \subseteq S \Rightarrow a \in S$
where $\displaystyle m$ is the least element in $\displaystyle S$, and $\displaystyle s(a)$ the set of elements precede $\displaystyle 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 $\displaystyle T$ being a nonempty subset of $\displaystyle S$ and that $\displaystyle T \subseteq \mathbb{N}$, it follows that $\displaystyle T$ has a least element $\displaystyle t_0$; therefore, $\displaystyle T$ is well-ordered.

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

Suppose that none of the least element $\displaystyle t_0 \in T \subset \mathbb{N}$ is the first element $\displaystyle m$ of $\displaystyle S$, then $\displaystyle t_0 \not \in T- \mathbb{N}, t_0-1 \in T-\mathbb{N}$ and $\displaystyle m \in T-\mathbb{N}$. Hence $\displaystyle T-\mathbb{N}$ has a least element $\displaystyle m$ and the largest element $\displaystyle t_0-1$. As a consequence, $\displaystyle 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 $\displaystyle S$.

I hope it works this time.

#### Search Tags

orderedset 