Welcome to our community

Be a part of something great, join today!

Proving that not every non-empty set of integers has a least element

skatenerd

Active member
Oct 3, 2012
114
I have a problem asking to prove the following statement is false:
"Every non-empty set of integers has a least element".
This seems pretty intuitively false, and so I tried to sum that up in the following way:
Suppose we have a subset \(A\) in the "universe" \(X\).
Let \(A=\{-n: n\in{N}\}\), a non-empty set ( \(N\) denotes the set of all natural numbers).
So \(A=\{-1, -2, -3, ..., -n\}\).
It is evident that there is no limit to how low the elements in \(A\) can become.
Since \(A\) is a non-empty set with no least element, we have arrived at the desired conclusion. Q.E.D.

My professor gave me one out of three points on this problem and I just can't figure out why...
 

ZaidAlyafey

Well-known member
MHB Math Helper
Jan 17, 2013
1,667
Re: proving that not every non-empty set of integers has a least element

You must ask your teacher to know what is your mistake . A counter example should work out since for the non-empty set it has to have a least element . Choose the set to be The set $A$ as you did then this set has to be bounded by some element in $A$ from below let it be $-k \,\, , k\in \mathbb{N}$ but adding $-1$ will make $-(k+1)$ a lower bound , since $-(k+1)$ is already in the set $A$ this contradicts the result that $A$ has a least element.
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
My professor gave me one out of three points on this problem and I just can't figure out why...
A week ago a Ukrainian boxer Wladimir Klitschko beat a Russian boxer Alexander Povetkin in a much-anticipated match. The match lasted all twelve rounds, and there was never a knockout, but Klitschko won on points by a unanimous decision. Similarly, you had the right idea about this problem, but there are several shortcomings in your argument that may have made your professor give you that grade.

Suppose we have a subset \(A\) in the "universe" \(X\).
Here $X$ is undefined. You probably meant that $A$ is a subset of $\mathbb{Z}$.

Let \(A=\{-n: n\in{N}\}\)
It's not good to say, "Let \(A=\{-n: n\in{N}\}\)" after "Suppose $A\subseteq\mathbb{Z}$". The phrase "Suppose $A\subseteq\mathbb{Z}$" is equivalent to "Fix an arbitrary $A\subseteq\mathbb{Z}$". It has already chosen some subset of integers. After that, there is no reason why this subset has to be \(\{-n: n\in\mathbb{N}\}\); it could be \(\{-n-5: n\in\mathbb{N}\}\), for example. The only allowed thing after an object has been fixed is to give names to some parts of the object. For example, if you had said, "Suppose $A$ is an infinite subset of $\mathbb{Z}$, you could then say, "Let $A=\{a_1,a_2,\dots\}$"; this does not impose any new constraint on $A$.

So \(A=\{-1, -2, -3, ..., -n\}\).
This is not good because you selected an infinite $A$, but now you describe it as finite. You could say \(A=\{-1, -2, -3, \dots, -n,\dots\}\), but this does not add any new information.

It is evident that there is no limit to how low the elements in \(A\) can become.
Yes, it is evident, but since the problem is so basic, there is an expectation that you explain steps in more detail. Here Zaid's explanation fits: no $k\in A$ can be the least element because $k-1\in A$ and $k-1<k$.

Edit: Replaced $-k$ with $k$.
 
Last edited:

ZaidAlyafey

Well-known member
MHB Math Helper
Jan 17, 2013
1,667
Yes, it is evident, but since the problem is so basic, there is an expectation that you explain steps in more detail. Here Zaid's explanation fits: no $k\in A$ can be the least element because $-k-1\in A$ and $-k-1<k$.
Great explanation as usual , just pointing out the typo \(\displaystyle -k\in A , \,\, -k-1 <-k, \,\,\, k \in \mathbb{N}\).
 

skatenerd

Active member
Oct 3, 2012
114
Wow, thank you so much, that was a really helpful explanation. This whole mathematical proofs subject is pretty new to me, but you outlining all the unacceptable statements in my proof really helped me understand what is needed.