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?
$\endgroup$2 Answers
$\begingroup$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.
$\endgroup$ 9 $\begingroup$Another approach -:
A set S is finite if there is an injective map $ \phi : S \rightarrow ${${1,2,...,n}$} for some $n \in \mathbb{N}$.
Suppose A has cardinality N in your problem.
Now show that,
(i) There exit a bijection between $\mathcal{P}(A)$ and $ X^{N}$ where X={0, 1}.
(ii) $\phi : X^{N} \rightarrow$ {$ {1, 2,..., 2^{N}}$} such that $\phi(x) = 1 + \sum_{i=0}^{N-1}i*x_{i}$ is an injective map.
Draw the conclusion from (i), (ii) and definition I've mentioned above.
$\endgroup$
