Is this a valid proof of the well-ordering principle?

67 Views Asked by At

Let $S \subset \mathbb{N}$

The well-ordering principle says: $\exists \ n \in S : n \leq k \ \forall k \in S$, right?

Let's assume that the negation of this proposition right above is true, that is:

$$\exists k \in S : n > k \ \forall n \in S$$

See that $n > k$ is false when $n = k$, so the initial proposition must be true.

2

There are 2 best solutions below

2
On BEST ANSWER

Your negation of the Well-ordering principle is not correct.

The well-ordering principle is that every non-empty set of natural numbers has a minimum element.

The negation is that, there exists a non-empty set of natural numbers which does not have a minimum element.

If S is such a set, then it has to have an element say $a_1$, which is not minimum.

Thus it has an element $a_2< a_1$ and an element $a_3< a_2$, and so on and so forth. Is it possible to have an infinite sequence of strictly decreasing natural numbers?

1
On

The negation is $\nexists \ n \in S : \forall k \in S : n \leq k $

which is equivalent to $\forall \ n \in S : \exists k \in S : n \not \leq k$

or in words, for each element of $S$ there is a different element of $S$ which is smaller (more precisely, not greater)

Your attempt at the negation is more like $\exists k \in S : \forall \ n \in S : n \not \leq k$ but this is not equivalent. The key point is that you choose $k$ after choosing $n$

As an example, consider strictly positive real numbers with the usual order. You can always find a smaller number $k$ than any particular element $n$, but the smaller number must be chosen second