# Intersection of a non-empty set of natural numbers (set-theoretic definition) is a natural number?

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?

• 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$. – hardmath Aug 13 '14 at 12:02
• 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". – Elliott Aug 13 '14 at 12:03
• 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. – hardmath Aug 13 '14 at 12:09
• 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}$. – William Aug 13 '14 at 12:25
• Martin, this is indeed how the natural numbers are defined in the text I'm referencing (Halmos - Naive Set Theory). – Elliott Aug 13 '14 at 20:19

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?

• 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". – Elliott Aug 13 '14 at 20:18
• 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. – Elliott Aug 13 '14 at 21:18

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$.

• 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.) – Martin Sleziak Aug 13 '14 at 13:32
• 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$? – Elliott Aug 13 '14 at 20:14
• @Elliott I have tried to correct my proof. Probably there is more elegant way to do this. – Martin Sleziak Aug 13 '14 at 20:23
• 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. – Elliott Aug 13 '14 at 21:01
• 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 – Elliott Aug 13 '14 at 21:02