1
$\begingroup$

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$

$\endgroup$
  • 2
    $\begingroup$ 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$? $\endgroup$ – Martin Sleziak Aug 13 '14 at 9:09
  • $\begingroup$ Yes, we've proved this already. $\endgroup$ – Elliott Aug 13 '14 at 9:20
4
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ Wait a second, E is not a set of ordinals, E is a set of natural numbers! $\endgroup$ – Elliott Aug 13 '14 at 9:22
  • 1
    $\begingroup$ @Elliott In fact, the natural numbers are ordinals. But if you prefer, try to replace each occurrence of the word ordinal by natural number. $\endgroup$ – Martin Sleziak Aug 13 '14 at 9:28
  • 2
    $\begingroup$ 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! $\endgroup$ – jfhc Aug 13 '14 at 9:31
  • 1
    $\begingroup$ 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"? $\endgroup$ – Elliott Aug 13 '14 at 9:36
  • $\begingroup$ 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? $\endgroup$ – Elliott Aug 13 '14 at 11:49

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.