Does there exist a nonempty S ⊆ P(N) with no maximal elements?

Question

I have been trying to learn some set theory and I was wondering about the proof or disproof to this question. Intuitively, it seems like this statement is false, because all subsets have some maximal and minimal element. But I am not sure how to prove it using sets.

Answer 1

Any finite partially ordered set has maximal (and minimal) elements, and I think this is where your intuition is coming from; however, infinite partially ordered sets behave quite differently. E.g. $(\mathbb{Z},\le)$ is a partial order with no maximal or minimal elements.

Similarly, the answer to your question is: yes, you can quite easily. For example, let $S$ be the set of finite subsets of $\mathbb{N}$; is there a maximal finite set?

---

Indeed, the partial order $(\mathcal{P}(\mathbb{N}),\subseteq)$ has many odd subsets. My personal favorite example is a chain of size continuum. Fix some bijection $b:\mathbb{N}\rightarrow\mathbb{Q}$ (remember that $\mathbb{Q}$ is countable!). For each real number $r$, let $$D_r=\{q\in\mathbb{Q}: q<r\}$$ (this is basically a Dedekind cut). Let $A_r=\{b^{-1}(q): q\in D_r\}$. Then

For $r, s\in\mathbb{R}$, we have $A_r\subseteq A_s$ iff $r\le s$.

Answer 2

Assuming you mean you want a collection of subsets of $\mathbb{N}$ with no maximal element under inclusion; you can build such a collection very easily: for instance let $S$ be the set of finite initial segments of $\mathbb{N}$, i.e., $S = \{ \emptyset, \{0\},\{0,1\},\ldots\}$. The elements of $S$ form a countable chain with no upper bound in $S$.

However, more is true, you can get such an $S$ of size $\mathcal{P}(\mathbb{N})$ if you are clever. The way to do it is to look at $\mathbb{Q}$ instead. Try and modify the initial segments idea used about to build a size continuum chain.