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?
Best Answer
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\}$.
Now use the fact that the range of a finite set is finite.