Explanation of a proof of $\mathbb{N}$ being well-ordered by $\in$

58 Views Asked by At

This is purely self-study, I tried to read set theory from J. Malitz, Introduction to Mathematical Logic. In the chapter, "Transfinite Numbers", theorem 10.3 states - $$\text{Each } n\in \mathbb{N} \text{ is well-ordered by} \in, \text{ and so in } \mathbb{N}$$

1) I believe the last "in" is a typo and it should be "is", but if not what does the statement mean?

2) The proof given below says $x\notin x$. Because otherwise $\{x\}$ would be a subset of $x$ having no $\in$-minimal member. Why does a singleton set have no $\in$-minimal member? I mean can't we choose $x$ itself to be the minimal member? I believe this is where I screw up logically, but I can't really see it. I have similar questions for the claim "there is no $y\in x$ such that $x\in y$". I hope solving the former would help me out in this case.

3) The proof claims further that $\in$ linearly orders $x\cup \{x\}$. It seems obvious but can we say that for any $x, y$ at least one of $x\in y$ and $y\in x$ holds true? It seems obvious from the construction, but I am not very sure.

4) The proof ends with "$y\cap x\ne \emptyset$ then $y$ has minimal..." which I think is okay. Then if "$y\cap x=\emptyset$ then $y=\{x\}$ and $x$ is the $\in$-minimal member. " Why can we say $x$ is the minimal member in this case, whereas in the beginning $\{x\}$ had no $\in$-minimal member.

Finally, they didn't prove whether $\mathbb{N}$ is well-ordered or not. I would be grateful if someone could provide some hints. I must apologize for not understanding so many parts in the proof, I am only beginning to learn this. I hope someone can help me understanding the rigor behind this. Thanks to everyone.

enter image description here

1

There are 1 best solutions below

0
On BEST ANSWER

$(1)$ Yes, the in in the statement of the theorem should be is.

$(2)$ Suppose that $x\in x$; then $\{x\}\subseteq x$. (This is just an instance of a general fact: if $a\in x$, then $\{a\}\subseteq x$.) Recall that $x\in X$, so $x$ is well-ordered by $\in$; by definition this means that every non-empty subset of $x$ has an $\in$-minimal member. Thus, $\{x\}$, being a non-empty subset of $x$, must have an $\in$-minimal member. The only element of $\{x\}$ is $x$, so $x$ must be the $\in$-minimal member of $\{x\}$. By his definition that means that there is no $y\in\{x\}$ such that $y\in x$. But in fact there is such a $y\in\{x\}$: take $y=x$. Thus, $x$ is not in fact $\in$-minimal in $\{x\}$, and $\{x\}$ therefore has no $\in$-minimal element. Since $x\in X$, this is impossible, and the contradiction shows that $x\notin x$. Since $x\in\Bbb N$, we know that $x$ is transitive; if there were a $y\in x$ such that $x\in y$, transitivity would imply that $x\in x$; we’ve just seen that this is not the case, so there cannot be such a $y$.

$(3)$ The author actually gives the argument that $\in$ linearly orders $x\cup\{x\}$; he just doesn’t make it very clear that this is what he’s doing. We already know that it linearly orders $x$. Suppose that $y\in x$. Then $y\ne x$ (since we’ve seen that $x\notin x$). Moreover, we just showed that $x\notin y$. Thus, exactly one of $x\in y$, $x=y$, and $y\in x$ is true, namely, the last. All that remains is to verify that $\in$ is transitive on $x\cup\{x\}$. We already know that it’s transitive on $x$, so the only instances of transitivity that need to be checked are those involving $x$: if $y\in x$ and $z\in y$, is it true that $z\in x$? The answer is yes by the previous lemma, in which it was shown that each $x\in\Bbb N$ is transitive. (It’s probably worth noting explicitly that when this author talks about a linear order, he means a strict linear order, one like $<$, not $\le$.)

$(4)$ The author never said that $\{x\}$ has no $\in$-minimal member; quite the opposite, actually. His argument was that if $x$ were an element of $x$, then $\{x\}$ would have no $\in$-minimal member. But this is impossible, since we already know that $\{x\}$ does have an $\in$-minimal member (because it’s a non-empty subset of $x$, and $x\in X$), and therefore $x$ is not an element of $x$.

$(5)$ The proof that $\Bbb N$ is well-ordered by $\in$ is, as the author suggests, very much like the proof that $x\cup\{x\}$ is well-ordered by $\in$. Let $x$ be a non-empty subset of $\Bbb N$, and let $y\in x$.

  • If $y\cap x=\varnothing$, then no member of $x$ is a member of $y$, and $y$ is therefore $\in$-minimal in $x$.

  • If $y\cap x\ne\varnothing$, then $y\cap x$ is a non-empty subset of $x$, which we just proved is well-ordered by $\in$, so $y\cap x$ has an $\in$-minimal element $z$. Clearly $z\in x$. Suppose that $u\in z\cap x$; then $u\in z\in y$, and $y$ is transitive, so $u\in y$, and therefore $u\in z\cap(y\cap x)$. But $z$ is $\in$-minimal in $y\cap x$, so $z\cap(y\cap x)=\varnothing$: no member of $y\cap x$ is a member of $z$. This contradiction shows that no such $u$ can exist, i.e., that $z\cap x=\varnothing$: no member of $x$ is a member of $z$. Thus, $z$ is an $\in$-minimal member of $x$, as desired.