For every non-empty subset $E$ of a natural number, there exists an element $k \in E$ such that $k \in m$ for all $ m \in E $ distinct from $k$

Question

I was reading Naive Set Theory by Halmos and the question stated in the title is Exercise at the end of Section 12 in the book. So, everything I write in the question is in this context, and proofs I can accept will only be those which assume as axioms only as much as is assumed in the Sections 1-12 of the book (Sorry if I sound arrogant, I couldn't find words). I already looked up the following question:

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$

But the answer is incomplete. I had also thought of taking intersection of sets in $E$ and taking that to be $k$, but I was stuck when I tried showing that $k \in E$. At this point, I had to again look up on this site and found this:

Intersection of a non-empty set of natural numbers (set-theoretic definition) gives an element of that set?

However, again to my dissatisfaction, I couldn't understand the proof, given in the only answer to this question, which I will henceforth refer to as Ans.2, completely. Here are the problems I have with it:

1. I understand that we can prove by induction that every element of a natural number is a natural number. But, I didn't understand why intersection of natural numbers is natural. In one of the comments to this answer, the author addresses this by saying that once you have the fact that "a natural number contains every natural number smaller than it", you can prove this. I don't understand what "smaller" means here. In the book, we have not yet defined any arithmetic on Natural numbers, so this doesn't make sense to me. So, I don't know yet if $k$ (in the notation of question) is a natural number.
2. I don't understand why "For every $a$ in $E$, either $k^{+} \subseteq a$ or $a \in k^{+}$ ". (The answer in the 2nd link uses $m$ in place of of $k$).
3. In my attempt to answer this question, I actually tried proving first that $k \in E$ as done in Ans.2 without using the first point in Ans.2. If we prove this, then we can say that $k \in E$, so $k \in n$ (where $n$ is the natural number whose non-empty subset $E$ we are considering), but as every element of a natural number is a natural number, $k$ is a natural number. After this, we know that $k \subsetneq a$ for every $a \in E, a \neq k$, from the definition of $k$ as intersection. And then I thought to use "if $n$ and $m$ are distinct natural numbers, then $n \in m \iff n \subsetneq m$". But I could only prove $n \in m \implies n \subsetneq m$. Below is my attempt to prove $n \subsetneq m \implies n \in m$ :

My attempt: Here, $\omega$ denotes the set of natural numbers. Let $S = \{ m \in \omega : n \subsetneq m \implies n \in m\}$. Then, we want to show that $S$ is an inductive set.

1. $0 \in S$ because there is no proper subset of $0$.
2. Suppose $m \in S$. Now, proper subsets of $m^{+}$ are (a) proper subsets of $m$ or (b) proper subsets of $m$ union ${m}$. For any $n \subsetneq m^{+}$ such that $n$ is of type (a), we have $ n \in m$, which implies $ n \in m^{+} $. So, we are done for (a). I couldn't prove it for (b) type of subsets.

I appreciate any kind of help.

Answer 1

Inspired by and develpoing on the comments, I was able to figure out the answers to my questions, which I state here chronogically :

1. First, I prove that $k$ is a natural number. I will use the following result often, so without proving it, I will just state it for reference(proof can be easily done by induction):

Trichotomy: If $m, n \in \omega$, then exactly one of $ m \in n, m=n$ or $n \in m$ holds.

Definition: If $m, n \in \omega$, then $ m$ is said to be smaller than $n$ if $ m \in n$.

Proposition 1 : $m \in n \iff m \subsetneq n $

Proof: Suppose $m \in n$, we prove $ m \subsetneq n $ by induction on $n$. Of course if $m \in 0$, then $ m \subsetneq 0 $. Suppose the claim is true for $n$. Then, if $m \in n^{+}$, either $m \in n$ or $ m =n$ because $n^{+} := n \cup \{n\}$. If $m \in n$, then $m \subsetneq n $ by induction hypothesis, whereby $ m \subsetneq n^{+}$. If $m =n$, then of course $m\subsetneq n^{+} $ (equality is not there on RHS in this case, because "a natural number is not a subset of one of its elements", which is again easily proved by induction.)

Conversely, suppose $m \subsetneq n $, then from trichomoty, either $m \in n$ or $ n \in m$. If $n \in m$, then we get a contradiction, again because "a natural number is not a subset of one of its elements". So, we must have $m \in n$.

One more result easily derived from induction that I use is:

Proposition 2: Every element of a natural number is a natural number.

Now, suppose $E$ in the question was a non-empty subset of a natural number $n$, then $k = \cap E \subsetneq n$, so by Proposition 1, we have $k \in n$, which means $k$ is a natural number by Proposition 2.

2. "For every $a$ in $E$, either $k^{+} \subseteq a$ or $a \in k^{+}$", follows from Trichotomy for natural numbers (now that we have proved that $k$ is a natural number) and Proposition 1.
3. Now we want to show that $k \in E$. For every $a$ in $E$, we have either $k^{+} \subseteq a$ or $a \in k^{+}$. Suppose $k^{+} \subseteq a$ for all $a$ in $E$, then $k^{+} \subseteq k$, because intersection is the largest subset containing all $a \in E$. This is a contradiction to "a natural number is not a subset of one of its elements". So, there exists an $ a \in E$ such that $ a \in k^{+}$. Then, $ a \in k$ or $a=k$. If $ a \in k$, then since $k \subseteq a$, we get a contradiction to the fact that "a natural number is not a subset of one of its elements". So, $ k =a $ and thus $k \in E$.

This completes the proof. I hope it helps other people.