2
$\begingroup$

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$
4
$\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$
  • $\begingroup$ So simple, thank you. $\endgroup$ – Joshhh Nov 3 '15 at 21:46
  • 1
    $\begingroup$ It just so happened, that this is an exercise for my students for this week. $\endgroup$ – Asaf Karagila Nov 3 '15 at 21:47
  • $\begingroup$ Maybe one of your students spent a lot of time thinking about this and was a bit frustrated he couldn't think about this last piece of the puzzle. $\endgroup$ – Joshhh Nov 3 '15 at 21:56
  • 1
    $\begingroup$ Maybe. If that is the case, I'm happy to see that said student has sat down to do their homework on the same day they received them. $\endgroup$ – Asaf Karagila Nov 3 '15 at 22:05
  • $\begingroup$ Also, it you go the Kuratowski finiteness route, you can change wording of OP's question to "... no cardinalities PERIOD". See Proposition 2.3 in 'Some Notes on Finite Sets' \C. Preston arxiv.org/pdf/1509.02747.pdf $\endgroup$ – CopyPasteIt Sep 14 '17 at 3:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.