0
$\begingroup$

The Well ordering principle states that

A least element exists in every non empty set of positive integers

Use the well Ordering principle to prove the following statement

' Any nonempty subset of negative integers has the greatest element '.

What I tried

By contradiction

I assume the statement

Any nonempty subset of negative integers has the least element to be true.

This means that the least element $a$ must be a negative integer but this contradicts with the Well ordering principle which states that the least element must be a positive integer. Hence the least element cannot be positive and negative at the same time which thus proves the orginal statement. Is my proof correct. Could anyone explain. Thanks

$\endgroup$
1
$\begingroup$

The negation of "Any nonempty subset of negative integers has the greatest element " is not "Any nonempty subset of negative integers has the least element", but rather "there exists a nonempty subset of negative integers that does not have a greatest element."

In general, the negation of a statement that has the universal quantifier ("for all ... ") has an existence quantifier ("there exists ...").

I think it's easier to prove this directly.

Hint: Let $A$ be a nonempty set of negative integers and consider the set $B=\{-a: a \in A\}$.

What can you say about the set $B$?

$\endgroup$
  • $\begingroup$ The set B is a nonempty set of positive integers? $\endgroup$ – ys wong Jul 15 '15 at 9:42
  • $\begingroup$ Yes, so it has what property? $\endgroup$ – coldnumber Jul 15 '15 at 9:42
  • 1
    $\begingroup$ So it has a least element $\endgroup$ – ys wong Jul 15 '15 at 9:45
  • $\begingroup$ Can i also prove it in this way? Suppose "there exists a nonempty subset of negative integers that does not have a greatest element, hence there exist a least element that does not exists in the set $S$, where $S$ consists of all positive integers. But from the well ordering principle, there exist a least element in the set $S$ hence contradicting the assumption $\endgroup$ – ys wong Jul 16 '15 at 6:48
  • $\begingroup$ A proof by contradiction would definitely work, but not exactly as you stated it, because the set $S$ does have a least element (1). However, you could say "there exists a nonempty subset of negative integers $A$ that does not have a greatest element, hence the nonempty set $B=\{-a : a \in A\}$ of positive integers does not have a least element. But from the well ordering principle, there exist a least element in the set $B$ hence contradicting the assumption." $\endgroup$ – coldnumber Jul 16 '15 at 6:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.