Halmos's set theory If $E$ is a non-empty set of natural numbers, exists some $k$ in $E$ such that $k \leqq m$ for all $m\in E$. Prove by intersection

Question

Update

I saw a similar question which provided a proof by using axiom of induction and I wrote an answer by adapting to one of the answers of that question. But I hope someone can give another proof by using the intersection approach which I have explained at the end of my question.

---

In Halmos set theory, page 52 there is an exercise. The last part of which reads:

Prove that if $E$ is a non-empty set of natural numbers, then there exists an element $k$ in $E$ such that $k \leqq m$ for all $m$ in $E$.

How can we prove this based on what we know so far in the book?

So far in the book we know the following which might be relevant for a proof:

1. For every natural number $n$ we have $n^+ = n \cup\{n\}$
2. No natural number is subset of any of its elements.
3. Every element of a natural number is a subset of it.
4. If $m$ and $n$ are distinct natural numbers then $m\in n$⟺$m \subset n$.
5. For every two natural numbers $m$ and $n$ we have exactly one of these: $m\in n$ or $n \in m$ or $m=n$.
6. if $m \in n$ or equivalently $m$ is a proper subset of $n$, we shall write $m \lt n$.
7. if $m$ is known to be either less than or equal to $n$ we write $m \leqq n$

Also we have five Peano axioms for the set of natural numbers $\omega$

1. $0 \in \omega$
2. if $n \in \omega$, then $n^+ \in \omega$
3. if $S \subset \omega$, if $0 \in S$, and if $n^+ \in S$ whenever $n \in S$, then $S = \omega$
4. $n^+ \neq 0$ for all $n$ in $\omega$
5. if $n$ and $m$ are in $\omega$ , and if $n^+ = m^+$, then $n=m$

ZF Axioms so far:

1. Extension
2. Specification
3. Pairing
4. Union
5. Powerset
6. Infinity

Possible proof sketch based on intersection of natural numbers:

1. define $s = \cap E$ (because $E$ is a non-empty collection of sets, its intersection is defined)
2. show that $s \in \omega$ (I'm stuck at this part)
3. show that $s \in E$
4. show that $s \leqq m$ for all m in $E$

Answer 1

The relevant property here is: If $n\neq m$ then either $n<m$ or $n>m$, and all elements of $n$ are subsets of $n$. So this means: $n$ contains exactly all natural numbers that are smaller than $n$.

Now consider a non-empty set of natural numbers $E$. Then we will show that the minimum of $E$ is the intersection $m$ of $E$. This then contains exactly all $n$ that are smaller than anything in $E$. Also as $m$ cannot be element of itself we’d get that $m$ must be in $E$ if we knew that $m$ is in fact a natural number. (Because then if it was not in $E$ it would either be smaller than anything in $E$, thus an element of itself, or it would be larger than one Element of $E$ which would thus be smaller than itself).

Since we do not know this, we walk a different path: Suppose $m\neq 0$ (if $m=0$ it is a natural number), then $m$ contains $0$. Suppose for one $n\in m$ we’d get $n^+\not\in m$. Then there must be a $k\in E$ so that $n^+\not < k$. But as $n<k$ this means that $k\not < n^+$. Thus $k=n^+$. But then $k$ contains all Elements smaller than $k$ and also only elements in $m$. Thus $m=k$.

Now if no such $n$ exists then by Peano we get $m=\mathbb N$, which would contradict to it’s definition and $E\neq\emptyset$.

Answer 2

We use the axiom of induction but first we need a lemma.

lemma:

$s \lt t^+ \implies s \leqq t$

proof: $s \lt t^+ \implies s\in t^+ \implies s\in t\cup\{t\} \implies s\in t \lor s=t \implies s\lt t \lor s=t\implies s \leqq t$

main proof by induction

Suppose $E$ is a non-empty set of natural numbers. Define $S$ as a subset of $\omega$ such that if any element of $S$ is a memeber of $E$ then there exists some $k\in E$ such that for all $m\in E$ we have $ k \leqq m$.

First we prove $0\in S$. Then we prove if $n\in S$ then $n^+ \in S$. And by using axiom of induction we get $S=\omega$ which means if any natural number is a member of $E$ then there exists some $k\in E$ such that for all $m\in E$ we have $k \leqq m$

$S = \{n\in\omega:$ if $n\in E$ then there exists an element $k \in E$ such that $k\leqq m$ for all $m \in E\}$.

(base case of induction)

$0 \in S$ because if $0 \in E$ then $k=0$ and $k\leqq m$ for all $m\in E$

(hypothesis of induction)

Suppose $n \in S$ means that if $n\in E$ then there exists some $k \in E$ such that $k \leqq m$ for all $m \in E$

(step of induction)

supposing that $n \in S$, we need to prove that $n^+ \in S$ which means if $n^+\in E$ then there exists some $k \in E$ such that $k \leqq m$ for all $m \in E$

Suppose $n^+ \in E$

If for all $m \in E$ we have $n^+ \leqq m$ then such $k$ exists and $k=n^+$

On the other hand $n^+$ does not satisfy and there exists some $j\in E$ such that $j < n^+$ then $j \leqq n$.

We consider the set $E'=E \cup \{n\}$. Now $E'$ is a non-empty subset of $\omega$ and $n \in E'$ so $E'$ satisfies induction hypothesis. So there exists $k' \in E'$ such that for all $m\in E'$ we have $k' \leqq m$. Now either $k' \in E$ or $k' = n$.

If $k'\in E$ then there is no problem. If $k' = n$ then we have $j \leqq n = k'$ and $k' \leqq j$ which gives $j\leqq k' \leqq j$ which gives $j = k' = n \in E$ and proof is done.