Quick question. Prove that an arbitrary set $\mathbf{A_n}$ where $n$ is the number of elements has a power-set with $2^n$ elements.

Question

parthkohli · Answer

Induction, but how?

parthkohli · Answer

Hmm, let's involve $n = 1 $ to start with.$$\mathcal{P}\{\emptyset\} =\{ \emptyset \} $$This has one element. True for $n =1$.

parthkohli · Answer

I still don't understand how to go about with assuming that this is true $n = k$ and $k + 1$ or not.

parthkohli · Answer

@amistre64 Your assistance is certainly needed, sire.

anonymous · Answer

Sorry for Not -my origin but anyway -wkp

anonymous · Answer

As you see the argument is as follows:
For n+1 the power set will be twice as numerous because - there will be 2 copies of each PREVOUS subset. One "copy" not including a new (n+1)-th member and one copy that does include the new member

anonymous · Answer

Mr asker @ParthKohli ?

anonymous · Answer

I get it - the Olympians reside in the olympus, and me - well not an olympian obviously.

amistre64 · Answer

by proving it for some specific "n", we are only proving it for one value; we assume its true for any k, which allows k to be equal to n at some point.  proving that it is true for k+1 allows us to deduce that since k=n at some point, then k+1 = n+1 as well

anonymous · Answer

Thanks @ganeshie8 , aren't you afraid to give  a medal  to अछूत ?

parthkohli · Answer

Well, is proving by using combinations a good idea?

ganeshie8 · Answer

lol i liked the logic given :) 2^n + 2^n thingy...  :)

amistre64 · Answer

combinations is proved by induction if i recall correctly:)

parthkohli · Answer

Does there even exist such a proof? For example, if a set has $4$ elements, then its powerset will have$$\sum_{i =0}^4 {^4C_i}$$

parthkohli · Answer

elements.

parthkohli · Answer

well, i = 1 is the lower limit.

anonymous · Answer

The elements of power set 2^S can be put in 1:1 correspondence  to characteristic functions from S to {Yes include, Not Include} = {1, 0} . Obviously the number of such choices is $$2^{|S|}$$

amistre64 · Answer

basis:  $$P\{A_0\} = \{\ \} = 2^0$$
assume:$$P\{A_k\} = \{\{\ \},\{1\},\{2\},\{3\},...,{} \} = 2^k$$
lol, showing a generic setup for that does look a bit tricky

amistre64 · Answer

{},{1},{2},{3},...,{k},
  {1,2},{1,3},{1,4},...,{1,k},
     {2,3},{2,4},{2,5},...,{2,k},

pfft .....

amistre64 · Answer

Would you have to reinvent how to define a power set?