# Power set of a finite set is finite proof, no cardinality of power set

Prove that $\mathcal{P}(A)$ of a finite set $A$ is finite.

I need to prove this without using the cardinality of $\mathcal{P}(A)$.

This is my attempt, which is by induction: $\newcommand{\lbrac}[1]{\left(#1\right)}$ $\newcommand{\sett}[1]{\left\{#1\right\}}$ $\newcommand{\pset}[1]{\mathcal{P}\lbrac{#1}}$ Proof by induction over cardinality.

If $A = \varnothing$, then $\pset{A} = \sett{\varnothing}$, which is finite.

Suppose that for a set $A$ of cardinality $n$, $\pset{A}$ is finite.

Let $A$ be a set of cardinality $n+1$. $A$ is not empty, since it is of cardinality $n+1 > 0$, and therefore pick some $x\in A$. It follows that $A = \lbrac{A-\sett{x}}\cup\sett{x}$. We claim that $$\pset{A} = \pset{\lbrac{A - \sett{x}}\cup\sett{x}} = \pset{A - \sett{x}}\cup\sett{C | C\in\pset{A}\wedge x\in C}$$ Suppose $B\in\pset{A} = \pset{\lbrac{A-\sett{x}}\cup{x}}$. Then either $x\in B$ or $x\not\in B$. If $x\in B$, then $x\in B \wedge B\in\pset{A}\Rightarrow B\in C$. If $x\not\in B$ then $B\subseteq A - \sett{x}$. \newline Either way, $B\in \pset{A - \sett{x}}\cup\sett{C | C\in\pset{A}\wedge x\in C}\Rightarrow \pset{A}\subseteq\pset{A - \sett{x}}\cup\sett{C | C\in\pset{A}\wedge x\in C}$.

Suppose $B\in\pset{A - \sett{x}}\cup\sett{C | C\in\pset{A}\wedge x\in C}$. Then either $B\in\pset{A-\sett{x}}$ or $B\in\sett{C | C\in\pset{A}\wedge x\in C}$ (or both).

If $B\in\pset{A-\sett{x}}$, then $B\subseteq(A-\sett{x})\cup\sett{x} = A$, and if $B\in\sett{C | C\in\pset{A}\wedge x\in C}$, then by definition, $B\subseteq A$. Either way, we get that $B\in\pset{A} \Rightarrow \pset{A - \sett{x}}\cup\sett{C | C\in\pset{A}\wedge x\in C} \subseteq \pset{A}$.

Since we have shown both sets are contained in each other, they are equal.

My goal is to now prove that $\sett{C|C\in\pset{A} \wedge x\in C}$ is finite. I didn't manage to do so without non rigorous claims that could also "prove" the main question.

If this set is finite, and by induction hypothesis $\pset{A - \sett{x}}$ is finite, I'll be done.

Any ideas on how to prove $\sett{C|C\in\pset{A} \wedge x\in C}$ is finite?

Note that there is a bijection between $\{C\mid C\subseteq A\land x\in C\}$ and $\mathcal P(A\setminus\{x\})$. Simply map $C$ to $C\setminus\{x\}$.