Set theory question

[battletoad]

Started off with graph theory with some elementary things. There's one thing however that i cant wrap my head around, the order of the edges. I get that if the vertices of a graph were included in a set S, the number of edges is equal to the order of the power set of S. For the life of me i cant remember the proof if i did it or not.

 

Can someone please provide the proof of |P(S)|=2^(nC2), where P(S) is the power set of set S, |S|=n and C refers to the combination function? Much appreciated

[the tree]

Can someone please provide the proof of |P(S)|=2^(nC2), where P(S) is the power set of set S, |S|=n and C refers to the combination function? Much appreciated

For any and all sets S with |S|=n, |P(S)|=2ⁿ. So I'm assuming you stumbled over what you meant there.

 

[imath]2^{n \choose 2}[/imath] would be the cardinality of the set of possible edgings for [imath]n[/imath] vertices.

[battletoad]

For any and all sets S with |S|=n, |P(S)|=2ⁿ. So I'm assuming you stumbled over what you meant there.

 

[imath]2^{n \choose 2}[/imath] would be the cardinality of the set of possible edgings for [imath]n[/imath] vertices.

 

Yip, tripped up over there. Thanks for the reply. But why is |P(S)|=2ⁿ? Is there a proof for it?

---

Merged post follows:

Consecutive posts merged

Its fine i got it. If anyone's interested its binary basically. For a set with n elements, draw n columns, a column for each element in the set. Then for every combination, add 1 if the element is in ur subset, 0 if not. Clearly there will be 2ⁿ combinations

Edited January 28, 2010 by battletoad
Consecutive posts merged.

[the tree]

Proof by induction always seems a fair shot with combinatorics.

 

Let your base of induction be a set S with one element a₁. Then clearly P(S) = { {} , {a₁} }. So |P(S)| = 2 = 2¹.

 

For the inductive step, say you have a set S with n-1 elements and |P(S)| = 2^n-1. Then add another a_n element to S: define S' := S U {a_n}, now P(S') contains every element of P(S) and each one of those elements again but with an a_n added. So |P(S')| = |P(S)| + |P(S)| = 2|P(S)| = 2ⁿ.

 

So by the inductive principle, |P(S)| = 2ⁿ for all sets S with a cardinality n > 0.

[battletoad]

Proof by induction always seems a fair shot with combinatorics.

.

.

.

 

Thanks. Your proof puts the matter to rest. Strange, im usually the first one to shout 'proof by induction' yet the idea alluded me. Meh, six months of working has made me soft!