2
$\begingroup$

This question is very similar to Intersection of a non-empty set of natural numbers (set-theoretic definition) gives an element of that set?

Consider the following set-theoretic definition of natural numbers:

  • $0$ is defined as $\emptyset$
  • If $n$ is defined, then the successor of $n$ is defined as $n^+ = \{n\} \cup n$

Thus $1 = \{0\}$, $2 = \{0, 1\}$, and so on.

Let $\omega$ be the set of all natural numbers defined as above, and let $E$ be an arbitrary non-empty subset of $\omega$.

How can we show that that the intersection of $E$ is a natural number?

$\endgroup$
  • $\begingroup$ I'm sure you noticed that the "natural numbers" so constructed (the finite von Neumann ordinals) are ordered by inclusion, i.e. nested. So a smallest entry of $E$ would become the intersection over $E$. $\endgroup$ – hardmath Aug 13 '14 at 12:02
  • $\begingroup$ Unfortunately I need to use this to prove that E has a smallest entry in the first place, so I can't just say "take the smallest entry of E". $\endgroup$ – Elliott Aug 13 '14 at 12:03
  • $\begingroup$ Unfortunately you haven't really presented the full "set-theoretic" definition of "natural numbers", so it's guesswork at this point to say how you would get a handle on finiteness. One approach would be to use nonemptiness of $E$ and pick an element in it, say $n$. Then $n$ should be finite, and $n$ should contain the intersection over $E$. Since there are only finitely many "natural numbers" less than $n$, the intersection of $E$ and $n$ must be finite. The finite sets are well-ordered, so the least element of $E$ must be one of them. $\endgroup$ – hardmath Aug 13 '14 at 12:09
  • $\begingroup$ Your definition of $\omega$ is not exactly correct. Let $\mathbb{N}$ denote the natural number in our universe (the one everyone is familiar with). For each $n \in \mathbb{N}$, in any set theoretical universe, there exists the set $\hat{n}$ as you defined above. You suggest to define $\omega = \{\hat{n} : n \in \mathbb{N}\}$. However using the usual set theory axiom, you can not define a set this way since $\mathbb{N}$ is what you think of the natural number in our universe. In fact, by a compactness argument, there is a set theoretic universe where $\omega$ does not look like $\mathbb{N}$. $\endgroup$ – William Aug 13 '14 at 12:25
  • 1
    $\begingroup$ Martin, this is indeed how the natural numbers are defined in the text I'm referencing (Halmos - Naive Set Theory). $\endgroup$ – Elliott Aug 13 '14 at 20:19
2
$\begingroup$

Let $x$ be $\bigcap E$. All elements of $E$ are natural numbers and thus all elements of $E$ are sets of natural numbers. So, $x$ is a set of natural numbers.

As $E$ is not empty, there's a natural number $n_0 \in E$. Clearly, $x \subseteq n_0$.

If $y \in x$, then $y \in n$ for all $n \in E$. As all $n \in E$ are transitive, we have $y \subseteq n$ for all $n \in E$, so $y \subseteq \bigcap E = x$, i.e. $x$ is transitive.

Now you have that $x$ is a transitive set of natural numbers which is a subset of some natural number $n_0$. Does that suffice?

$\endgroup$
  • $\begingroup$ I feel like this should suffice, but I still need to convince myself that "a transitive set of natural numbers which is a subset of some natural number is itself a natural number". $\endgroup$ – Elliott Aug 13 '14 at 20:18
  • $\begingroup$ Yup, this suffices. Let $S$ be the set of natural numbers for which every transitive subset is a natural number. $0 \in S$ since the only possible subset of $0$ is just $0$. Suppose $n \in S$, and let $x$ be a transitive subset of $n^+$. If $n$ is not an element of $x$, then $x \subset n$, and we just use the inductive hypothesis. Otherwise, $n \in x$, and transitivity implies $n \subset x$, so in fact $n^+ \subset x$, and $n^+ = x$. Either way, $x$ is a natural number, and the proof is complete. $\endgroup$ – Elliott Aug 13 '14 at 21:18
1
$\begingroup$

EDIT: As pointed out in Eliott's comment, the proof I have suggested is not correct:

I feel like this should suffice, but I still need to convince myself that "a transitive set of natural numbers which is a subset of some natural number is itself a natural number"

However, he also suggests how the proof can be corrected:

I ended up doing something like this: (1) prove by induction that if X is a non-empty subset of a natural number, then the intersection of X is a natural number; (2) find a set F such that the intersection of F is the same as the intersection of E, but F is a subset of a natural number.


We can prove by induction on $n$ that $$a\in n \qquad \Rightarrow \qquad a\in\omega,$$ i.e., every element of a natural number is also a natural number.

We also know that for two natural number we have $$m\in n \qquad \Leftrightarrow \qquad m\subsetneq n.$$


Now if you have $E\subseteq\omega$, $E\ne\emptyset$, and $a=\bigcap E$, then $a\subseteq n$ for each $n\in E$.

If there is an $n\in E$ such that $n\ne a$, we get $a\in n$. So by the above claim, $a$ is a natural number.

The other possibility is that $E=\{a\}$. In this case we have $a\in E\subseteq\omega$ which, clearly, means that $a\in\omega$.

$\endgroup$
  • $\begingroup$ This is repost of my (now deleted) answer to the previous question. (I have misread that question and I have only discussed the proof that the intersection is a natural number, not that it belongs to the given set. So I have deleted my answer there, but I think it fits this question.) $\endgroup$ – Martin Sleziak Aug 13 '14 at 13:32
  • 1
    $\begingroup$ Thanks Martin! I agree that $a \subset n$ for each $n \in E$, but how did you then conclude that $a \in n$ for each $n \in E$? $\endgroup$ – Elliott Aug 13 '14 at 20:14
  • $\begingroup$ @Elliott I have tried to correct my proof. Probably there is more elegant way to do this. $\endgroup$ – Martin Sleziak Aug 13 '14 at 20:23
  • 1
    $\begingroup$ Martin, I'm still not fully convinced, since to me it looks like you're using the assumption that $a \in n$ if and only if $a$ is a proper subset of $n$ before you've proved that $a$ is a natural number. $\endgroup$ – Elliott Aug 13 '14 at 21:01
  • 1
    $\begingroup$ That said, all this discussion has been immensely helpful anyway! I ended up doing something like this: (1) prove by induction that if X is a non-empty subset of a natural number, then the intersection of X is a natural number; (2) find a set F such that the intersection of F is the same as the intersection of E, but F is a subset of a natural number $\endgroup$ – Elliott Aug 13 '14 at 21:02

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.