# 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 itself an element of $E$?

For context, I was working on the problem described in the link below, and got stuck after following the given hint:Prove: If $E$ is a nonempty subset of natural numbers , then there exists an element $k$ in $E$ such that $k\in$ m for any $m$ in $E$ and$m \ne k$

• At the point of the exposition of natural numbers, where you want to prove this, do you already know (or can show) that $n\in m$ $\Leftrightarrow$ $n\subsetneq m$? – Martin Sleziak Aug 13 '14 at 9:09
• Yes, we've proved this already. – Elliott Aug 13 '14 at 9:20

There is a proof on proofwiki that the intersection of any set of ordinals is the smallest ordinal in that set.

It proceeds as follows:

• Let $m$ be $\bigcap E$. It is easy to show that every element of a natural number is a natural number, so by definition of intersection, the intersection of a set of natural numbers must be a natural number.

• By the definition of intersection, $m \subseteq a$ for every $a$ in $E$.

• Now to show that $m \in E$, we consider the successor of $m$, $m^+$.

• For every $a$ in $E$, either $m^+ \subseteq a$ or $a \in m^+$. If $m^+ \subseteq a$ for all $a \in E$, then $m^+$ is in the intersection of $E$, so $m^+ \subseteq m$, i.e. $m \in m$ which contradicts the axiom of foundation. Hence there is some $e \in E$ such that $e \in m^+$.

• Either $e \in m$ or $e = m$ by definition of $m^+$ and the fact that $e$ is an element of it.

• So $e \subseteq m$ as if $e \in m$ then $e \subset m$ (if this fact is not established for natural numbers, it's easy to do so by induction).

• $e \subseteq m$ and $m \subseteq e$ so $m = e$.

• $e \in E$ so $m \in E$ as required.

$\square$

• Wait a second, E is not a set of ordinals, E is a set of natural numbers! – Elliott Aug 13 '14 at 9:22
• @Elliott In fact, the natural numbers are ordinals. But if you prefer, try to replace each occurrence of the word ordinal by natural number. – Martin Sleziak Aug 13 '14 at 9:28
• Elliott, I have removed all references to ordinals. @Martin thanks for spotting that, I fixed it. Also, as Martin points out, the natural numbers are ordinals (so properties of the ordinals apply to the natural numbers) — the ordinals are an interesting and natural extension of the natural numbers which I'm sure will come up soon in your set theory course if they haven't yet! – jfhc Aug 13 '14 at 9:31
• Thanks jfhc! This makes sense. Are we required to consider $m^+$ though? Could we instead have said "if m is a proper subset of a for every a in E, then m is an element of a for every a in E, so m is fact an element of the intersection, which is not allowed; thus m must be equal to a for some a in E"? – Elliott Aug 13 '14 at 9:36
• I agree that "every element of a natural number is a natural number", but how does it follow that the intersection of a set of natural numbers is a natural number? – Elliott Aug 13 '14 at 11:49