Prove $S$ has a least element.

Question

Can anyone help me with my proof, please? I only got half points, but my professor won't tell me what I am doing wrong. My proof is:

Let $z$ $\in \mathbb{Z}$. If $S$ is a nonempty set of integers that are all greater than or equal to $z$, then $S$ has a least element.

And this is what I have:

First note that $S$ is the nonempty set of integers greater than or equal to $z$. We will create and use the alternative set $Q$, where $Q=\{x\in \mathbb{Z}\mid x=g+(-z), g\in S\}$ for some integer $g$. $Q$ is in the set of whole numbers because all elements of $S$ are greater than $z$ and $g$ is in $S$, so our lowest possible result from this is zero, therefore $Q$ is in the set of whole numbers and know it has a least element because of the least ordering principle and the set of whole numbers non-empty and positive. Since we added -$z$ to $S$ to get to the set of whole numbers, we must add $z$ to get back to the set of integers. Since $g+(-z)$ was the least element in the set $Q$ and we added $z$ to get back to the set $S$, we suspect that $k+z$ is the least element in $S$ for some integer $k \in S$. We must now prove $k+z \in S$, and we will do this by using proof by contradiction. That is, we will assume $k+z$ is less than some integer $r$ in $S$ and show that $k+z$ is not less than or equal to $r$. We begin with $r>k+z$. We begin by subtracting $z$ from both sides to get $r-z>k$. Since both $k$ and $r$ are in $S$, they are greater than or equal to $z$, so $r-z$ would be less than $k$ and we have come to a contradiction of our assumption that $k+z$ is less than some integer $r$ in $S$ which proves $k+z$ is the least element in $S$ and completes the proof.

Answer 1

You never picked what the least element was. Let's say you meant for $k$ to be the least element. What you then want to prove is not that $k+z\in S$, which is obvious, but rather that $k+z$ is the least element of $S$. You seem to have attempted to do that, but never succeeded.

I'm not sure exactly what you're trying to say with "We will assume $k+z$ is less than some integer $r$ in $S$ and show that $k+z$ is not less than or equal to $r$." But you want $k+z$ to be less than or equal to $r$. Perhaps you meant that $k+z$ is less than $r$, but this need not be true as we could take $r=k+z$. Reading before that, you assume that $k+z$ is less than $r$ from the outset, which is what you actually want to show.

The way to complete it would be to prove that if $r\in S$, then $k+z\leq r$. To do this, we note that $k\leq r-z$ because $r-z\in Q$ and $k$ is the least element of $Q$, hence $k+z\leq r=(r-z)+z$.

Answer 2

If z is in S then we are done. If z is not in S, then see if z+1 is in S. If so then z+1 is the least element. Else see if z+2 is in S. If so then it is the least element. Keep adding 1 until you get an element in S.

If you keep adding 1 and never reach an element in S then S is not a nonempty set of integers all >= k, a contradiction.

Therefore, if you keep adding 1 to k, you will, at some point, get to the lowest integer in S.

Answer 3

Let $S=P \cup N$, where $P$ is the set of non-negative elements of $S$ and $N$ is the set of negative elements of $S$. If $N \neq \emptyset$, then $N$ is finite so it has a least element. Moreover, every element of $N$ is less than every element of $P$, so the least element of $N$ is necessarily the least element of $S$.

If $N = \emptyset$, then $P \neq \emptyset$. Since $P$ is a non-empty set of natural numbers, by the well-ordering principle $P$ has a least element, and since $N = \emptyset \Rightarrow P=S$, that means $S$ has a least element.

The problem with your proof is that you have not defined $S$ correctly. You have defined it as all integers $k \geq z$. That's not correct. Although all of the elements of $k \in S$ have the property $k \geq z$, as $S$ is defined in the problem, it's not in general true that $S$ contains all such integers.

For example, it's possible that $z=-5$ and $S=\{3, 8\}$. You're trying to define it as $T= \{ k \in \Bbb Z \mid k \geq z \} = \{-5, -4, -3, \ldots \}$, and while it's true that $S \subset T$ and you have proved the result for $T$, the inclusion can be proper so you haven't yet proved it for all possible $S$.