Well-Ordering Principle Question

[Aryth]

I'm trying to do this proof, but I'm coming across questions about certain properties of well ordered sets that aren't answered by my material. Here's the problem I'm working on:


For any fixed integer \(\displaystyle m\), prove that the set \(\displaystyle X = \{a \in \mathbb{Z} : m \leq a\}\) is well-ordered.


In trying to prove this, but I've come across a question:


For any non-empty subset of \(\displaystyle X\), \(\displaystyle Y\), we shall consider the set \(\displaystyle S = \{b - m : b \in Y\}\). Regardless of the set \(\displaystyle Y\), \(\displaystyle S \subseteq \mathbb{N} \cup \{0\}\), and thus \(\displaystyle S\) is well-ordered (we have proven that the subset of a well-ordered set is well-ordered). Does this imply that \(\displaystyle Y\) is well-ordered? I can't seem to find any information in my class materials that show this to be true, and I can't really see how to prove that property.

 

[pka]

I'm trying to do this proof, but I'm coming across questions about certain properties of well ordered sets that aren't answered by my material. Here's the problem I'm working on:
For any fixed integer \(\displaystyle m\), prove that the set \(\displaystyle X = \{a \in \mathbb{Z} : m \leq a\}\) is well-ordered.

I assume that \(\displaystyle 0 \in \mathbb{N}\text{ and }\mathbb{N}\text{ is well ordered.} \)

It is clear that \(\displaystyle m\in X\). So let \(\displaystyle Y = \{x-m : x\in X \}\) then \(\displaystyle Y= \mathbb{N}\).

Now I do not follow what you are doing. But from there we can prove that \(\displaystyle X\) is well ordered.

 

[Aryth]

I assume that \(\displaystyle 0 \in \mathbb{N}\text{ and }\mathbb{N}\text{ is well ordered.} \)

It is clear that \(\displaystyle m\in X\). So let \(\displaystyle Y = \{x-m : x\in X \}\) then \(\displaystyle Y= \mathbb{N}\).

Now I do not follow what you are doing. But from there we can prove that \(\displaystyle X\) is well ordered.

Well, when I went to my professor, I was given this hint:

For any nonempty \(\displaystyle Y \subseteq X\), consider the set \(\displaystyle S = \{b - m : b \in Y\}\)

I think we are trying to show that \(\displaystyle X\) satisfies the definition of well-ordered, i.e. that every nonempty subset has a minimal element, by actually showing that any nonempty subset has a minimal element. Maybe my question wasn't exactly what I was looking for, but then again, I'm not really sure about this problem at all.

I like what you were doing more, though. How can we use \(\displaystyle Y = \mathbb{N}\) to show that \(\displaystyle X\) is well-ordered? (That is actually the question I wanted to ask, because I tried doing it this way first, but couldn't show it).

 

[pka]

Well, when I went to my professor, I was given this hint:
For any nonempty \(\displaystyle Y \subseteq X\), consider the set \(\displaystyle S = \{b - m : b \in Y\}\)

Well I did say that I did not follow what you were doing.
From the hint we see that \(\displaystyle S\subseteq\mathbb{N}\).
So \(\displaystyle S\) has a first term \(\displaystyle (\exists s_0\in S)(\forall x\in S)[s_0\le x]\)

Show that \(\displaystyle s_0+m\) is the first term in \(\displaystyle Y\).

 

[Aryth]

Well I did say that I did not follow what you were doing.
From the hint we see that \(\displaystyle S\subseteq\mathbb{N}\).
So \(\displaystyle S\) has a first term \(\displaystyle (\exists s_0\in S)(\forall x\in S)[s_0\le x]\)

Show that \(\displaystyle s_0+m\) is the first term in \(\displaystyle Y\).

I do appreciate you working with me. I follow you now.

Well, first we know that there exists some element in \(\displaystyle Y\), which we will call \(\displaystyle b_0\), that generates \(\displaystyle s_0\) in \(\displaystyle S\). Since \(\displaystyle s_0\) is the minimal element of \(\displaystyle S\), there are no elements \(\displaystyle b_i < b_0, \ b_i \in Y\) such that \(\displaystyle b_i - m < s_0\) because every \(\displaystyle b_i \geq m\) so that if \(\displaystyle b_0\) creates the smallest difference in \(\displaystyle S\), no other element can generate a smaller difference, meaning that the other elements of \(\displaystyle Y\) must be greater than or equal to \(\displaystyle b_0\). We know that \(\displaystyle b_0 - m = s_0\), and so the minimum of \(\displaystyle Y\) is \(\displaystyle b_0 = s_0 + m\). Since every nonempty subset of \(\displaystyle X\), \(\displaystyle Y\), has a minimal element, we can conclude that \(\displaystyle X\) is well-ordered.

Let me know if it can be refined... This is only my second proof course, and so I'm still working on my composition.

 

[pka]

Well, first we know that there exists some element in \(\displaystyle Y\), which we will call \(\displaystyle b_0\), that generates \(\displaystyle s_0\) in \(\displaystyle S\). Since \(\displaystyle s_0\) is the minimal element of \(\displaystyle S\), there are no elements \(\displaystyle b_i < b_0, \ b_i \in Y\) such that \(\displaystyle b_i - m < s_0\) because every \(\displaystyle b_i \geq m\) so that if \(\displaystyle b_0\) creates the smallest difference in \(\displaystyle S\), no other element can generate a smaller difference, meaning that the other elements of \(\displaystyle Y\) must be greater than or equal to \(\displaystyle b_0\). We know that \(\displaystyle b_0 - m = s_0\), and so the minimum of \(\displaystyle Y\) is \(\displaystyle b_0 = s_0 + m\). Since every nonempty subset of \(\displaystyle X\), \(\displaystyle Y\), has a minimal element, we can conclude that \(\displaystyle X\) is well-ordered.
Let me know if it can be refined... This is only my second proof course, and so I'm still working on my composition.

You know that \(\displaystyle Y \ne \emptyset \) so \(\displaystyle \exists {y_0} \in Y \subseteq X \to m \le {y_0} \to 0 \le {y_0} - m \in S\).

So \(\displaystyle S \ne \emptyset \) thus has a first term.

 

[Aryth]

You know that \(\displaystyle Y \ne \emptyset \) so \(\displaystyle \exists {y_0} \in Y \subseteq X \to m \le {y_0} \to 0 \le {y_0} - m \in S\).

So \(\displaystyle S \ne \emptyset \) thus has a first term.

I'm not sure what you're doing here? We supposed that \(\displaystyle Y\) was nonempty, and so, by construction, \(\displaystyle S\) is nonempty... I'm not sure how what you said necessarily implies that \(\displaystyle S\) has a first term (aside from what you did in your earlier post when you implied it because \(\displaystyle S\) was well-ordered).

 

[pka]

I'm not sure what you're doing here? We supposed that \(\displaystyle Y\) was nonempty, and so, by construction, \(\displaystyle S\) is nonempty... I'm not sure how what you said necessarily implies that \(\displaystyle S\) has a first term (aside from what you did in your earlier post when you implied it because \(\displaystyle S\) was well-ordered).

Do you have a clue about any of this? You are either a troll or you are not thinking about this. Which is it?

Because \(\displaystyle S\subset\mathbb{N}\text{ and }S\ne\emptyset\text{ then }S\text{ has a first term.}\)

Call that first term \(\displaystyle s_0\). \(\displaystyle \text{Then }s_0+m\text{ is the first term of }Y\).

If you don't get that then I am sorry. You can hope that someone else may help you.

But I assure you that I am done with this.