The set {odd natural numbers greater than 0 }U {even natural numbers}

that is, the set

$\bigcup \{ \{1,3,5,7...\}, \{2,4,6,8...\} \}$

also strangely written

$\{1,3,5,7... ; 2,4,6,8...\}$ .

is often given as an example of a well-ordered set ( a set such that for all subset there is a first element).

I have some problems with this example.

(1) First, which relation orders this set? Could this relation be defined explicitly? Is this relation somewhat analogous to lexigraphic order? So I don't understand how this set can be an ordered set.

(2) Second, I don't understand how it is well-ordered. In order to be well ordered, every subset should have a first element. But apparently, the set $\{7,2\}$ is a subset of my set. What is the first element of $\{7,2\}$?


Sets have no "inherent order". They can have a natural order (such as $\Bbb N$ or $\Bbb R$ having a natural ordering that we consider somehow "part of the set"), but they do not have an inherent ordering.

Writing $\{1,3,5,\dots;0,2,4,\dots\}$ is a terrible abuse of notation.

But it is indeed a well-ordering of $\Bbb N$ which is not its natural ordering (which is also a well-ordering). Here is an explicit definition:

$$m\prec n\iff \begin{cases}m\text{ is odd and }n\text{ is even}, &\text{ or}\\m\equiv n\pmod 2\text{ and }m<n.\end{cases}$$

To see it is a well-ordering, note that each of the subsets, evens and odds, is ordered in the natural way which makes that part a well-order, and so given a non-empty set, it either has a smallest odd number or it is a subset of the even numbers.

  • 1
    $\begingroup$ @AsafKalaglia. Thanks a lot! So in the context of my question, putting first odd numbers and second even ones, the first element of { 7,2} is 7, am I right? $\endgroup$ – Ray LittleRock Apr 30 at 10:33
  • 1
    $\begingroup$ Yes. I misremembered between reading the question and writing my answer (mainly because whenever I gave that example, I would put the even numbers first. I'll edit to fix this.) $\endgroup$ – Asaf Karagila Apr 30 at 10:34
  • $\begingroup$ @AsafKalaglia. The set ( with its abusive notation) is given in my book as the union of {odds} and {even} to show, as example, that the union of a family of WOS is also a WOS. Does it really qualify as such a union? As noted JoséCarlosSantos in a previous answer, normally the union of these two sets is simply N with its natural ordering. $\endgroup$ – Ray LittleRock Apr 30 at 10:36
  • 1
    $\begingroup$ I don't know who wrote the book. There is a notion of summation of orders, and the sum of well-orders over a well-ordered index, is again a well-order. My guess is that this was their meaning. $\endgroup$ – Asaf Karagila Apr 30 at 10:37
  • $\begingroup$ @AsafKalaglia.The reference is Schaum's Outline of Set Theory. $\endgroup$ – Ray LittleRock Apr 30 at 10:40

As suggested, a well-ordered set is one in which each subset has a first element. The natural numbers $\mathbb{N}$ with their usual relation $\le$ form a prototypical example:

$$0 < 1 < 2 < 3 < 4 < 5 < \cdots$$

however what I believe your example, written as

$$\{ 1, 3, 5, 7, \cdots ; 2, 4, 6, 8, \cdots \}$$

is supposed to indicate (what book or other reference is this from?) is a well-ordered set in which the order looks like this:

$$1 < 3 < 5 < 7 < \cdots < 2 < 4 < 6 < 8 < \cdots$$

in other words, it's all the odd numbers ordered in the usual way, and then after ALL of them, all the even numbers, again, ordered in the usual way. The trick is that every odd number is "less" than every even number in this new ordering, and thus shows a well-order which is different from the usual ordering of the natural numbers. It's meant to show that there are more forms a well-order can take than one might at first expect. In particular, it is a well-order which has an "internal infinity" in that there are an infinite number of elements between any odd number and any even number.

With regard to the question of the initial element of the subset $\{7, 2\}$, the answer is simple: looking at the sequence as shown above and where 7 and 2 fall therein, it is seen at a glance to be 7 (not 2). In terms of the mathematical definition, since 7 is odd, and 2 is even, 2 must be "greater" than every odd number, hence also greater than 7 and 7 is the initial element.


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.