Mathematical Induction.. WTF?

[Hacp]

n(A) is the cardinality of set A.
P(A) is the power set of A.

Can someone explain the step "Then P(B) consists of all subsets of {a1, a2, · · · , an} together with all subsets of {a1, a2, · · · , an} with the element an+1 added to them. "
Why is this the case?

Shouldn't P(B) just all the subsets {a1,a2,...,an,an+1)?
That is equal to the power set of {a1,a2,...,an} + power set of X.
We know n*P({a1,a2,...,an})= 2^n but what is n*P(x)?? The answer suggests that it is also 2^n but how do we know that?

 

[Vegitto]

A power set isn't just {a1, a2, a3, etc..}, it's all of the possible sets, including sets of sets (as in {empty, {empty, a1}, {a1, a2} {a1, a2, a3}} etc..

 

[Red Squirrel]

I think trying to understand that just caused a vein to pop in my brain.

 

[PieIsAwesome]

I am still on winter break not gonna think about that right now.

 

[Hacp]

A power set isn't just {a1, a2, a3, etc..}, it's all of the possible sets, including sets of sets (as in {empty, {empty, a1}, {a1, a2} {a1, a2, a3}} etc..

Yes I already know that. My question however isn't answered -_-.

 

[Vegitto]

Let me just translate the proof from my course and explain for a bit:

Let us assume a set A with A = {1,2,3}.

The power set of A, P(A) would have cardinality 2^3 (=8), because all of its possible subsets are:

{empty}, {1}, {2}, {3}, {1,2}, {2,3}, {1,3} and {1,2,3}

Set A contains 3 elements, and its cardinality was 2^3.

Let us now assume set B with B = {1,2,3,4}

The power set of B, P(B) should now have cardinality 2^4 (=16). Let us see why by showing all of its subsets. It should, in any case, share all of P(A)'s subsets, which were:

{empty}, {1}, {2}, {3}, {1,2}, {2,3}, {1,3} and {1,2,3}

Furthermore, it should contain subsets carrying the additional element, namely 4. These subsets are:

{4}, {1,4}, {2,4}, {3,4}, {1,2,4}, {1,3,4}, {2,3,4} and {1,2,3,4}

These are also 8 elements, enabling us to say:

n(A) = 3
n(P(A)) = 2^3

n(B) = 4
n(P(B)) = 2^4 = 2^(3+1) = 2 * 2^3

QED

 

[rocadelpunk]

QED my ass.

If you only had to prove every math problem with 2 examples and not for all natural numbers/every possibility there would be a lot of fuzzy math out there.

If you don't understand induction than start off with easier induction problems than working with power sets.

Say like the tried and true proving the formula for adding the first n natural numbers...

 

[Hacp]

Let me just translate the proof from my course and explain for a bit:

Let us assume a set A with A = {1,2,3}.

The power set of A, P(A) would have cardinality 2^3 (=8), because all of its possible subsets are:

{empty}, {1}, {2}, {3}, {1,2}, {2,3}, {1,3} and {1,2,3}

Set A contains 3 elements, and its cardinality was 2^3.

Let us now assume set B with B = {1,2,3,4}

The power set of B, P(B) should now have cardinality 2^4 (=16). Let us see why by showing all of its subsets. It should, in any case, share all of P(A)'s subsets, which were:

{empty}, {1}, {2}, {3}, {1,2}, {2,3}, {1,3} and {1,2,3}

Furthermore, it should contain subsets carrying the additional element, namely 4. These subsets are:

{4}, {1,4}, {2,4}, {3,4}, {1,2,4}, {1,3,4}, {2,3,4} and {1,2,3,4}

These are also 8 elements, enabling us to say:

n(A) = 3
n(P(A)) = 2^3

n(B) = 4
n(P(B)) = 2^4 = 2^(3+1) = 2 * 2^3

QED

I revised the question to make it clearer. Maybe you can explain it now? What you stated before hand made sense but I don't think that's a proof...

 

[Vegitto]

QED my ass.

If you only had to prove every math problem with 2 examples and not EVERY possibility there would be a lot of fuzzy math out there.

That's true, but I used numbers instead of variables for this proof, to make it easier to understand. This theorem has been proven a loooooong-ass time ago by people a lot smarter than you and me combined.

Just trying to help.

EDIT: Hacp: It's not a complete proof, but it should make the point more obvious to you. I'll take a look at your revised question.

 

[Vegitto]

Ah, I see what you're getting at. Well, that's what I tried to explain, actually.

If A consists of {1,2}, then it's power set is

{empty}, {1}, {2}, and {1,2}

If you add 1 element to A, say 3, then you could add the single element 3 to the elements of the power set, add it with the original power set and it'll give you the new power set.

The original power set of A was

{empty}, {1}, {2}, and {1,2}

Let's say we add the element '3' to each of these:

{empty,3} (this just becomes {3}, since {empty, 3} isn't empty at all),
{1,3},
{2,3}, and
{1,2,3}

This partially powered set also has 4 elements, just like the original A power set. If you add this new set to the original, you get

{empty}, {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3}, the powerset of A+{3}.

 

[rocadelpunk]

Yeah...I don't think he understands the steps of induction / idea behind it, hence start off with more basic problems.

read read read, do more and more problems. Induction is just one tool you'll have to have in your math utility belt.

 

[Vegitto]

I see complainin' but no explainin'.

 

[Hacp]

Ah, I see what you're getting at. Well, that's what I tried to explain, actually.

If A consists of {1,2}, then it's power set is

{empty}, {1}, {2}, and {1,2}

If you add 1 element to A, say 3, then you could add the single element 3 to the elements of the power set, add it with the original power set and it'll give you the new power set.

The original power set of A was

{empty}, {1}, {2}, and {1,2}

Let's say we add the element '3' to each of these:

{empty,3} (this just becomes {3}, since {empty, 3} isn't empty at all),
{1,3},
{2,3}, and
{1,2,3}

This partially powered set also has 4 elements, just like the original A power set. If you add this new set to the original, you get

{empty}, {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3}, the powerset of A+{3}.

Yes it makes sense but that step seems like a conjecture.

 

[Vegitto]

Yes it makes sense but that step seems like a conjecture.

That's true, but that's because I used numbers instead of variables and didn't completely follow induction rules.

I'm just trying to explain the concept of these power sets to you.

 

[rocadelpunk]

I see complainin' but no explainin'.

Um, the answer was already given in his book. It's self explanatory if you understand basic induction. If you don't understand this you need to go back to simpler problems, nuf' said.

 

[Hacp]

Um, the answer was already given in his book. It's self explanatory if you understand basic induction. If you don't understand this you need to go back to simpler problems, nuf' said.

I did the example problems before that just fine thank you. Would you care to explain why
all subsets {a1,a2,..,an} with the element an+1 added to them is equal to 2^n? Which induction step did you use to get 2^n?

 

[Hacp]

That's true, but that's because I used numbers instead of variables and didn't completely follow induction rules.

I'm just trying to explain the concept of these power sets to you.

I think the problem I'm having is splitting p(B) into two. I know how you did it and it makes sense when you use worked examples, but what is the underlying theorem that says you can actually take that step?

 

[Vegitto]

I think the problem I'm having is splitting p(B) into two. I know how you did it and it makes sense when you use worked examples, but what is the underlying theorem that says you can actually take that step?

It's just like your OP says. If you add ONE element to the set, you can take the first set, copy it, as it were, and add the one added element to every subset. Then you add both these partially powered sets and you have one full powerset, namely that of the set plus the one element.

I suggest you look for a translation of one of E.J. Weijdeveld's books (he's Dutch, just like me, but I know his work has been translated in French, German and English). His books (he's got like 12 on a wide variety of mathemetical subjects) are lenghty, but provide an in-depth and understandable analysis.

You won't like it when you start page 1, you'll love me when you finish at page 202.

 

[Hacp]

It's just like your OP says. If you add ONE element to the set, you can take the first set, copy it, as it were, and add the one added element to every subset. Then you add both these partially powered sets and you have one full powerset, namely that of the set plus the one element.

Is that a basic rule of set theory? We haven't done set theory yet, the instructor just gave us a practice worksheet to gauge our understanding of induction.

 

[Vegitto]

Is that a basic rule of set theory? We haven't done set theory yet, the instructor is just gave us a practice worksheet to gauge our understanding of induction.

Well, the basic rule deals with set addition instead of element addition, but yeah, that's basically it. In essence, if you add q elements to a set of n elements, the cardinality of the power set of the set with the addition is 2^(n+q).

 

[Hacp]

Well, the basic rule deals with set addition instead of element addition, but yeah, that's basically it. In essence, if you add q elements to a set of n elements, the cardinality of the power set of the set with the addition is 2^(n+q).

Ok that really helps. I can already tell I'm not going to have fun in this course

 

[Vegitto]

Ok that really helps. I can already tell I'm not going to have fun in this course

Nope, you aren't. Set theory is a bitch. I'd take getting stabbed in the balls over ever attending that course again any day..

 

[Hacp]

Nope, you aren't. Set theory is a bitch. I'd take getting stabbed in the balls over ever attending that course again any day..

Hmm it isn't a set theory course. Just introduction to higher math, I think its called intro to pure math/abstract math in other universities.

 

[Vegitto]

Ah, okay. Mathemetical induction can be quite hard, but it doesn't have to be.. I'm not all that great at math either.

Work at it, you'll manage.

 

[MovingTarget]

Is your question more about power sets/set theory or about the construct of proof by induction? If the latter, then it should be easier to describe in the context of number theory.

For a statemtent/conjecture P(), you first verify that a base case P(1) is true. The solution you linked to does this as n=1 is this base case, i.e. where A is the null set. You then assume P(n) is true for some natural number n. You then use this to verify that P(n + 1) must also be true. This proves that conjecture P(N) is true for all natural numbers N. In a sense, if you say that any case b is true, then the successor case b+1 must also be true. So, if case 1 is true, then case 2 must be true. If case 2 is true, then case 3 must be true, and so forth. In part (b), you simply apply the result of the conjecture you have proven.

Consider this conjecture: Any number written in the form 4b+1 must be odd, where b is some natural number. P(1): 4(1)+1=5, which is odd. P(n): 4n+1 is assumed true (i.e. that it must be an odd number). But 4(n+1)+1=4n+4+1=4m+1, which also must be odd as it is another case of P(n), which is true. Thus, by induction, the conjecture is true.

I know I'm getting a bit rusty on the subject, but I don't have my notes with me right now to give a better example. What course are you taking again? You could easily see this again when taking Topology or Algebra on the grad level.