Power Set less Empty Set has no Smallest Element iff not Singleton

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a set which is non-empty.

Let $\CC = \powerset S \setminus \O$, that is, the power set of $S$ without the empty set.


Then the ordered structure $\struct {\CC, \subseteq}$ has no smallest element if and only if $S$ is not a singleton.


Proof

Necessary Condition

Let $S$ not be a singleton.

Then $\exists x, y \in S: x \ne y$.


Let $Z \in \CC$ be the smallest element of $\CC$.

Then:

$\forall T \in \CC: Z \subseteq T$

But by Singleton of Power Set less Empty Set is Minimal Subset, both $\set x$ and $\set y$ are minimal elements of $\struct {\CC, \subseteq}$.

Therefore it cannot be the case that $Z \subseteq \set x$ and $Z \subseteq \set y$.

Therefore $\struct {\CC, \subseteq}$ has no smallest element.

$\Box$


Sufficient Condition

Let the ordered structure $\struct {\CC, \subseteq}$ has no smallest element.

Aiming for a contradiction, suppose $S$ is a singleton.

Let $S = \set x$.

Then:

$\CC = \set {\set x}$

Then:

$\forall y \in \CC: y \subseteq \set x$

trivially.

Thus $\struct {\CC, \subseteq}$ has a smallest element which is $\set x$.

By Proof by Contradiction it follows that $S$ is not a singleton.

$\blacksquare$


Sources