A set $A$ is finite if, and only if every nonempty set of subsets of $A$ has a maximal element in the sense of $\subset$

Question

This exercise is rather simple. However, I am concerned that in the right hand side implication; I use highly nontrivial results such as the Mirimanoff-von Neumann theorem and Zermelo's well ordering theorem.

Can anyone check if my proof is right? How could I improve it? Any suggestions about the right hand side? Could there be a more elementary proof that does not involve choice?

My try:

$\implies$: Suppose $A$ is a finite set. Then it is known that $\mathcal{P}(A)$ is also a finite set. If $B$ is a nonempty set of subsets of $A$, then $B\subseteq\mathcal{P}(A)$, and therefore, $B$ is also a finite set. Let $n\in\mathbb{N}$ be the only natural number such that $B\approx n$.

Since $B$ is nonempty, $n\not=0$. Let:

$$N=\{m<n\,|\,\text{any subset of }B\text{ with }m+1\text{ elements has a} \subset\text{-maximal element}\}$$

• Clearly, $0\in N$

• Suppose that $m\in N$ and $m+1<n$. Let $\mathscr{B}=\{B_0,\dots,B_{m+1}\}$ be subset of $B$ with $m+2$ elements. Then $\mathscr{B}=\{B_0,\dots, B_{m}\}\cup\{B_{m+1}\}$. Since $m\in N$, there is a maximal element in the sense of the inclusion for the set $\{B_0,\dots,B_m\}$, which we shall denote by $\mathscr{A}$. If $\mathscr{A}\subset B_{m+1}$, then $B_{m+1}$ is the $\subset$-maximal element of $\mathscr{B}$. If, on the contrary, $A_{m+1}\subset\mathscr{A}$, then $\mathscr{A}$ remains as the $\subset$-maximal element of $\mathscr{B}$. If neither of this possibilities happen, i.e., if $\mathscr{A}$ and $B_{m+1}$ cannot be compared, $\mathscr{A}$ is still the $\subset$-maximal element of $\mathscr{B}$. In any case, $m+1\in N$

In conclusion, $N=n$. However, there is only one subset of $B$ with exactly $n$ elements, namely $B$ itself. Se we conclude that $B$ will have a maximal element, as required.

$\Longleftarrow$ : Suppose that $A$ is an infinite set. By Zermelo's well ordering theorem, we know there is a relation $<_{R}\,\subseteq A\times A$ that is a well-ordering of $A$. Let $\alpha$ be the only ordinal such that $\langle A,<_R\rangle\cong\langle\alpha,\in_{\alpha}\rangle$, and let $f:\alpha\longrightarrow A$ be the only isomorphism between these to well ordered structures. If $\alpha$ was finite, then $A$ would be equipotent to a natural number, so it would be a finite set. Therefore, $\omega\le\alpha$ and we can construct the sequence $(A_n)_{n\in\omega}$ of elements of $\mathcal{P}(A)$ defined by:

\begin{cases} A_0=\{f(0)\} \\ A_{n+1}=A_n\cup\{f(n+1)\} \end{cases}

Now, consider the set $\{A_n|n\in\omega\}$. Clearly, it is nonempty, and its elements are subsets of $A$. It is clear that:

$$A_0\subset\dots\subset A_n\subset\dots$$

And this chain never stabilizes, that is, there is no $n\in\omega$ such that $A_i\subset A_n$ for all $i\in\omega$, so we found a set of subsets of $A$ with no maximal element in the sense of $\subset$.

Thanks in advance for your time.

Answer 1

I would say your proof of $(\implies)$ is fine, although a rigorous proof should be done by induction on the cardinality of $B$. It's also good to abstract a bit and prove a more general fact: every nonempty finite partial order has a maximal element. This is also proved by induction on the cardinality of the order.

In the proof of $(\impliedby)$, the set

$$\bigcup \{ A_n : n \in \omega \}$$

is the same as $\{ f(n) : n \in \omega \}$ and is not a family of subsets of $A$, but a subset of $A$ itself. The right family to consider is $\{ A_n : n \in \omega \}$, in which case the rest of the proof is correct.

A simple proof of $(\impliedby)$ not using the axiom of choice or any other serious tool is as follows: let $\mathcal{A}$ be the family of all finite subsets of $X$. It is nonempty, since $\varnothing \in \mathcal{A}$. By the assumption, there is a maximal element $A$ in $\mathcal{A}$. We claim that $X = A$.

Suppose not. Then there is some $x \in X \setminus A$. The set $A^* = A \cup \{ x \}$ is a finite set with $A \subsetneq A^*$, which contradicts the maximality of $A$.

Answer 2

Here's how I would do it.

If $A$ is finite and $\mathcal B$ is a nonempty set of subsets of $A$, let $C$ be a member of $\mathcal B$ with largest cardinality (this exists since $\mathcal B$ is finite). Then $C$ must be maximal, as if $C \subset D \in \mathcal B$, $|D| > |C|$.

On the other hand, if $A$ is infinite it contains an infinite sequence of distinct elements $a_1, a_2, a_3, \ldots$. Let $\mathcal B$ consist of the sets $B_n = \{a_1,a_2, \ldots, a_n\}$. None of these is maximal because $B_n \subset B_{n+1}$.

Answer 3

You are on the right track, but $\mathcal P$(A) cannot be shown to be finite without first proving that all non-empty families of subsets of a finite set A have a maximal element.

The proof goes by contradiction: show that a non-empty family of subsets with no maximal element can be used to construct a non-empty family of subsets with no minimal element.

That contradicts the definition that all non-empty families of subsets have a minimal element, and thus, a maximal element must always exist.

Suppose F is a non-empty family of subsets of A, and F has no maximal element, then the set $G=\{z |\exists y \in F(z= \cup F \setminus y)\}$ is a non-empty family of subsets of A with no minimal element.