Prove that a field of a set has $2^r$ elements if it has finite cardinality.

Question

Prove that a field of a set $A$ has $2^r$ elements if it has finite cardinality.

The definition of algebra is given here "https://en.wikipedia.org/wiki/Field_of_sets"

My try: I was trying to start from a simple example. Suppose $F:=\{\phi, X, a_1, a_1^c\}\subseteq A$ where $X$ is the total set.

Now $\exists b_1 \in A\setminus F$ then $b_1^c \in A\setminus F.$ If $ b_1 \subseteq a_1$ then $b_1^c \cup a_1\in A\setminus F$ and $(b_1^c \cup a_1)^c\in A\setminus F.$ From here the proof is getting clumsy. Is there any easy way to prove this?

Answer 1

Hints: Say that $x \sim y$ if the sets in the algebra that contain $x$ are precisely the one's that contain $y$. This is an equivalence relation. Let $[A_x]$ denote the equivalence class of $x$. Verify that $x \in A$ for some $A$ in the algebra implies that $[A_x] \subseteq A$. Now show that any set is a union of equivalence classes. It folows now that there is a bijection from the algebra onto the family of subsets of $\{1,2,...,n\}$ where $n$ is the number of equivalence classes.

Answer 2

We prove more generally that

Let $S$ be a finite Boolean algebra. Then $S \cong 2^n$ for some $n$, where $2$ is the 2-element Boolean algebra.

Proof: we proceed by strong induction on $|S|$.

If $|S| \leq 1$, then clearly $|S| = 1 = 2^0$ and we are done.

If $|S| > 1$, then let $f$ be a minimal element of $S \setminus \{0\}$. Such an $f$ exists since $S \setminus \{0\}$ is a finite nonempty partial order.

Consider $\neg f$. Note that $S_1 = \{x \in S \mid x \leq f\}$ and $S_2 = \{x \in S \mid x \leq \neg f\}$ are both Boolean algebras under the inherited order from $S$ (in general, $\{x \in S \mid x \leq w\}$ is a Boolean algebra for all $w$).

Note that $S_1 \cong 2$, since $S_1$ only has two elements, $f$ and $0$.

Furthermore, note that $|S_2| < |S|$, since $f \land \neg f = 0 < f$ and therefore $f \nleq \neg f$. Therefore, by the strong inductive hypothesis, we can take some $n$ such that $S_2 \cong 2^n$.

I claim that $S \cong S_1 \times S_2$ as Boolean algebras. Indeed, the isomorphism is $s \mapsto (s \land f, s \land \neg f)$, and the inverse is $(a, b) \mapsto a \lor b$. It's easy to verify that both directions are Boolean algebra homomorphisms and that they are inverse isomorphisms.

Therefore, $S \cong S_1 \times S_2 \cong 2 \times 2^n \cong 2^{n + 1}$.