I am working with the set theoretic natural numbers and trying to do an exercise from Halmos's Naive Set Theory. The exercise is to show that if $E$ is a nonempty subset of a natural number, then there is $k\in E$ such that for every $m\neq k$ in $E$, we have $k\in m$.

I am trying to show that $\bigcap E$ is the $k$ we seek. I have already shown that $\bigcap E$ has the "minimality" property, and am now just trying to prove that $\bigcap E \in E$, but am stuck. How should I go about this?

  • 2
    $\begingroup$ @Mauro: This was the essence of my answer, but the OP remarked that Halmos doesn't define the order at that point, so this is not the way to go (and therefore I have deleted my answer). $\endgroup$
    – Asaf Karagila
    Jul 14, 2014 at 21:45

1 Answer 1


Use induction to prove that $$\forall n\in\omega\left[E\subseteq n\wedge E\neq\emptyset\Rightarrow\bigcap E\in E\right]$$

If $n=0$ then it is vacuously true.

If $E\subseteq n+1\wedge E\neq\emptyset$ then $E\subseteq n\wedge E\neq\emptyset$ or $n\in E\subseteq n+1$.

In the first case $\bigcap E\in E$ by induction.

In the second case $E=E'\cup\left\{ n\right\} $ with $E'\subset n$. If $E'\neq\emptyset$ then $\bigcap E=\bigcap E'\in E'\subset E$ again by induction and if $E'=\emptyset$ then $\bigcap E=\bigcap\left\{ n\right\} =n\in E$.

  • $\begingroup$ Why is $\bigcap E = n$ in the second case? $\endgroup$
    – IssaRice
    Jul 15, 2014 at 0:17
  • $\begingroup$ Sorry, I overlooked something (and repaired). The second case needs a split up in two cases and in my original answer I only mentioned one them. $\endgroup$
    – drhab
    Jul 15, 2014 at 8:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .