3
$\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$

2 Answers 2

5
$\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
  • 1
    $\begingroup$ So simple, thank you. $\endgroup$
    – Joshhh
    Nov 3, 2015 at 21:46
  • 2
    $\begingroup$ It just so happened, that this is an exercise for my students for this week. $\endgroup$
    – Asaf Karagila
    Nov 3, 2015 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, 2015 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, 2015 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$ Sep 14, 2017 at 3:52
0
$\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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .