Question about proof from a guy with a highschool education

[micromass]

I'm not sure if you want me to prove the first one or just formulate something analogous for unions?

I want both. And perhaps try to prove the thing for unions too.

1)

A∪(B∪C) = (A∪B)∪C

If you want the proof of YOUR first statements (with the intersections) , I would try:

We accept the ZFC axioms.We will attempt to prove that A∩(B∩C) = (A∩B)∩C.

There is no need to keep saying that you use the ZFC axioms. I said before that you should always make clear what axioms you accept, but my point is that you should make it clear only once (and maybe again if you change axioms). So in a mathematical document, they will often state in the beginning what axioms they use (or more often: just give a reference, or just make it clear by context). But you shouldn't say it in the beginning of every proof.

Let x ∈ A∩(B∩C) be arbitrary.This implies that x ∈ A and that x ∈ (B∩C) , which in turn implies that x ∈ B and x ∈ C.Since x ∈ A and x ∈ B , it also implies that x ∈ (A∩B).And since x ∈ C and x ∈ (A∩B) , it implies that x ∈ (A∩B)∩C.

Now let x ∈ (A∩B)∩C be arbitrary.It implies that x ∈ (A∩B) and that x ∈ C.This implies that x ∈ A and x ∈ B.Since x ∈ C and x ∈ B , it implies that x ∈ (B∩C) , and since x ∈ A , it implies that x ∈ A∩(B∩C) , therefore proving that A∩(B∩C) = (A∩B)∩C.

OK

----------------------
2)

We will attempt to prove that A∩(B∪C) = (A∩B) ∪ (A∩C).

We accept the ZFC axioms.

Let x ∈ A∩(B∪C) be arbitrary.This implies that x ∈ A and that x ∈ (B∪C) , which implies that x ∈ B and x ∈ C.

Are you certain that it implies that $x\in B$ and $x\in C$??

Since x ∈ A , x ∈ B and x ∈ C , it implies that x ∈ (A∩B) and x ∈ (A∩C) , which implies that x ∈ (A∩B) ∪ (A∩C).

Now let x ∈ (A∩B) ∪ (A∩C) be arbitrary.This implies that x ∈ (A∩B) and x ∈ (A∩C)

Again: are you certain about the "and"??

which implies that x ∈ A , x ∈ B and x ∈ C.Since x ∈ B and x ∈ C , it implies that x ∈ (B∪C) , and since x ∈ A , it implies that x ∈ A∩(B∪C) , therefore proving that A∩(B∪C) = (A∩B) ∪ (A∩C).

----------------------
3)

We will attempt to prove that A∩A = A and A∪A = A.

We accept the ZFC axioms.

Let x ∈ A∩A be arbitrary.It implies that x ∈ A.

Let x ∈ A be arbitrary , it implies that x ∈ A∩A , therefore proving that A∩A = A.

Let x ∈ A∪A be arbitrary.It implies that x ∈ A.

Let x ∈ A be arbitrary , it implies that x ∈ A∪A , therefore proving that A∪A = A.

----------------------

OK.

4)

We will attempt to prove that (A∩B) × C = (A×C) ∩ (B×C).

We accept the ZFC axioms.

Note: I started a long x ∈ A and x ∈ B , x ∉ A' and x ∉ B' proof but it went nowhere.Can I simply use algebra?

(A∩B) × C = (A×C) ∩ (B×C)
A∩B = (A×C)/C ∩ (B×C)/C
A∩B = A∩B

First of all, a minor notation issue. The set difference is written as \ and not as /. Writing / denotes a quotient.

I don't know what you did here. First of all, you seem to think that $(A\times C)\setminus C$. This is false.

Second of all, you start from something that you want to prove. You can't do that.
Look at this: I want to prove that 1=2.

1=2
1*0 = 2*0
0 = 0

Therefore we have proven it.

Clearly this is false. This illustrates that the proof you have given can not be right. You can't start from something you need to prove, end up with something true and then say that this proves it. This is an incorrect method. They use the method in high school a lot and this confuses many people.

If you want to prove something, you should reverse your direction. For example, a correct proof would be like

0 = 0
Thus 1*0 = 2*0
Thus 1=2

This would be a correct proof. But alas, the third step is wrong (because we divide by 0).

Anyway, to prove $(A\cap B)\times C = (A\times C)\cap (B\times C)$. We should just use the methods you know. I'll prove one direction:

Take an arbitrary element $z$ of $(A\cap B)\times C$. This element has the form $z=(x,y)$, where $x\in A\cap B$ and $y\in C$. So we see that $z=(x,y)$ with $x\in A$ and $y\in C$. Thus $z\in A\times C$. Analogously, we see that $z=(x,y)$ with $x\in B$ and $y\in C$. Thus $z\in B\times C$. Since $z\in A\times C$ and $z\in B\times C$, we get that $z\in (A\times C)\cap (B\times C)$.

If you're more comfortable with proofs then you can leave out $z$ entirely and just do:

Take an arbitrary element $(x,y)$ of $(A\cap B)\times C$. And so on.

 

[reenmachine]

There is no need to keep saying that you use the ZFC axioms. I said before that you should always make clear what axioms you accept, but my point is that you should make it clear only once (and maybe again if you change axioms). So in a mathematical document, they will often state in the beginning what axioms they use (or more often: just give a reference, or just make it clear by context). But you shouldn't say it in the beginning of every proof.

ok that's good

Are you certain that it implies that $x\in B$ and $x\in C$??

woops , this pretty much destroy the whole thing doesn't it? :X

 

[reenmachine]

Take an arbitrary element $z$ of $(A\cap B)\times C$. This element has the form $z=(x,y)$, where $x\in A\cap B$ and $y\in C$. So we see that $z=(x,y)$ with $x\in A$ and $y\in C$. Thus $z\in A\times C$. Analogously, we see that $z=(x,y)$ with $x\in B$ and $y\in C$. Thus $z\in B\times C$. Since $z\in A\times C$ and $z\in B\times C$, we get that $z\in (A\times C)\cap (B\times C)$.

If you're more comfortable with proofs then you can leave out $z$ entirely and just do:

Take an arbitrary element $(x,y)$ of $(A\cap B)\times C$. And so on.

that's great , I thought about using two elements in x and y but finally just used algebra.

What I did was indeed a quotient.I just took the multiplication from the left side and transformed it into a division on the right side like in basic algebra , but I guess that doesn't work :X

 

[micromass]

woops , this pretty much destroy the whole thing doesn't it? :X

Yes, I'm afraid so

Do you know about truth tables?? Because they are a helpful tool in these kind of proofs.

 

[micromass]

that's great , I thought about using two elements in x and y but finally just used algebra.

What I did was indeed a quotient.I just took the multiplication from the left side and transformed it into a division on the right side like in basic algebra , but I guess that doesn't work :X

OK, but what is a quotient?? How do you define A/C for A and C sets?? I don't think such a thing exists.

 

[reenmachine]

2nd try on the 2nd problem:

We will attempt to prove that A∩(B∪C) = (A∩B) ∪ (A∩C).

Let x ∈ A∩(B∪C) be arbitrary.This implies that x ∈ A and that x ∈ (B∪C) , which implies that x ∈ B or C or both.Since x ∈ A , x ∈ B or C or both , it implies that x ∈ (A∩B) or (A∩C) or both , which implies that (A∩B) ∪ (A∩C).

Now let x ∈ (A∩B) ∪ (A∩C) be arbitrary.This implies that x ∈ A and x ∈ B or C or both.Since x ∈ B or C or both , it implies that x ∈ (B∪C) , and since x ∈ A , it implies that x ∈ A∩(B∪C) , therefore proving that A∩(B∪C) = (A∩B) ∪ (A∩C).

thoughts? I think it fix the problem :D

edit: btw no , I don't know what a truth table is :X

 

[reenmachine]

OK, but what is a quotient?? How do you define A/C for A and C sets?? I don't think such a thing exists.

What about substracting all elements of C on both side of the = ? It would gives us (A∩B) = (A∩B).

 

[micromass]

2nd try on the 2nd problem:

We will attempt to prove that A∩(B∪C) = (A∩B) ∪ (A∩C).

Let x ∈ A∩(B∪C) be arbitrary.This implies that x ∈ A and that x ∈ (B∪C) , which implies that x ∈ B or C or both.Since x ∈ A , x ∈ B or C or both , it implies that x ∈ (A∩B) or (A∩C) or both , which implies that (A∩B) ∪ (A∩C).

Now let x ∈ (A∩B) ∪ (A∩C) be arbitrary.This implies that x ∈ A and x ∈ B or C or both.Since x ∈ B or C or both , it implies that x ∈ (B∪C) , and since x ∈ A , it implies that x ∈ A∩(B∪C) , therefore proving that A∩(B∪C) = (A∩B) ∪ (A∩C).

thoughts? I think it fix the problem :D

OK, that's fine.

You say "x in A or x in B or both". There is no reason to say "or both". This is a huge difference with "or" in real life. Or in real life means either one or the other and usually not both. For example: "do you want brown bread or white bread". You usually don't want both.
However, "or" in mathematics is slightly different. "Or" here means that you either want one or the other or both. So the "or" in mathematics already implies that both is a possibility.
For example, we can say things like: we know that x>2 or x<4. Possible values for x are x=1 (then only x<4 is satisfied). But x=3 is also allowed (then both x>2 and x<4 is satisfied). In real life, x=3 were not allowed.

A popular math joke that deals with this is the following: "Should I open or close the window?" Answer: "Yes".

 

[micromass]

What about substracting all elements of C on both side of the = ? It would gives us (A∩B) = (A∩B).

But then you're dealing with set difference, no? But the claim $(A\times C)\setminus C = A$ is simply not true. You should try to find a counterexample.

 

[reenmachine]

OK, that's fine.

You say "x in A or x in B or both". There is no reason to say "or both". This is a huge difference with "or" in real life. Or in real life means either one or the other and usually not both. For example: "do you want brown bread or white bread". You usually don't want both.
However, "or" in mathematics is slightly different. "Or" here means that you either want one or the other or both. So the "or" in mathematics already implies that both is a possibility.
For example, we can say things like: we know that x>2 or x<4. Possible values for x are x=1 (then only x<4 is satisfied). But x=3 is also allowed (then both x>2 and x<4 is satisfied). In real life, x=3 were not allowed.

A popular math joke that deals with this is the following: "Should I open or close the window?" Answer: "Yes".

lol math humor , never gets old

Good to know about ''or''.

 

[reenmachine]

But then you're dealing with set difference, no? But the claim $(A\times C)\setminus C = A$ is simply not true. You should try to find a counterexample.

ok then what about (A × C) - (all elements of C) = A?

Sure that would leave all the elements of A that were previously inside ordered pairs , but since it doesn't matter how many times you write the same element in one set , then even if (A × C) = (1,2) , (1,3) where 2 and 3 are from C you're still left with A = 1.(I know i didnt use the set brackets , but couldn't find them quick enough for this short post)

 

[micromass]

ok then what about (A × C) - (all elements of C) = A?

Sure that would leave all the elements of A that were previously inside ordered pairs , but since it doesn't matter how many times you write the same element in one set , then even if (A × C) = (1,2) , (1,3) where 2 and 3 are from C you're still left with A = 1.(I know i didnt use the set brackets , but couldn't find them quick enough for this short post)

OK, I see what you mean. But I want you to realize that (A × C) - (all elements of C) = A is not what you want.

For example, take $A = \{1\}$ and $C=\{2\}$. Then $A\times C = \{(1,2)\}$. Now you want to remove all elements of $C$. But the only element in $C$ is $2$. And $2$ is not an element of $A\times C$. The only element of $A\times C$ is $(1,2)$. So if I remove $2$, then I just get $\{(1,2)\}$ again.

What you want to do is different. You want to obtain a set that is just the first coordinates of elements of $A\times C$. The best (and I guess, the only) way to write this down is by set-builder notation. It is written as follows

D=\{x\in A~\vert~\text{there exists an}~y\in C~\text{such that}~(x,y)\in A\times C\}

You should read this as follows: $D$ is the set of all elements $x$ in A such that there exists a $y\in C$ such that $(x,y)\in A\times C$.

This is the set you want. And indeed, this set is equal to $A$!

However, the proof you are trying to give is still incorrect even with this modification. The reason is again that you can't start from what you're trying to prove. Again, see the example

If 1=2, then 1*0 = 2*0, then 0=0.

What I wrote above is completely correct. But it would be incorrect to say that this proves that 1=2.

if (A × C) = (1,2) , (1,3) where

Don't forget the brackets! It should be

A\times C = \{(1,2), (1,3)\}

You might find it silly that I give so much criticism on your notation. But I think it's absolutely necessary to root out bad notations from the beginning. Bad notations may seem harmless now. But later on, bad notations will actually harm your understanding and make things very difficult.

 

[reenmachine]

OK, I see what you mean. But I want you to realize that (A × C) - (all elements of C) = A is not what you want.

For example, take $A = \{1\}$ and $C=\{2\}$. Then $A\times C = \{(1,2)\}$. Now you want to remove all elements of $C$. But the only element in $C$ is $2$. And $2$ is not an element of $A\times C$. The only element of $A\times C$ is $(1,2)$. So if I remove $2$, then I just get $\{(1,2)\}$ again.

What you want to do is different. You want to obtain a set that is just the first coordinates of elements of $A\times C$. The best (and I guess, the only) way to write this down is by set-builder notation. It is written as follows

D=\{x\in A~\vert~\text{there exists an}~y\in C~\text{such that}~(x,y)\in A\times C\}

You should read this as follows: $D$ is the set of all elements $x$ in A such that there exists a $y\in C$ such that $(x,y)\in A\times C$.

This is the set you want. And indeed, this set is equal to $A$!

However, the proof you are trying to give is still incorrect even with this modification. The reason is again that you can't start from what you're trying to prove. Again, see the example

If 1=2, then 1*0 = 2*0, then 0=0.

What I wrote above is completely correct. But it would be incorrect to say that this proves that 1=2.
Don't forget the brackets! It should be

A\times C = \{(1,2), (1,3)\}

You might find it silly that I give so much criticism on your notation. But I think it's absolutely necessary to root out bad notations from the beginning. Bad notations may seem harmless now. But later on, bad notations will actually harm your understanding and make things very difficult.

Ok I see where i was wrong now.Not sure I understand your ''modification'' but I guess i t doesn't matter for the moment as it stays irrelevant to the proof.

As for the notation , I mentionned I left them out on purpose , but I guess that was cheap on my part :X But no , I don't find anything you guys are saying silly , I'm here to learn and learning is both fun and painful.

Will try to prove the next exercises later.

thanks!

 

[micromass]

Ok I see where i was wrong now.Not sure I understand your ''modification'' but I guess i t doesn't matter for the moment as it stays irrelevant to the proof.

Set builder notation is important though. It comes up everywhere. I admit that the example above is not the easiest possible example of set builder notation though.

As for the notation , I mentionned I left them out on purpose , but I guess that was cheap on my part :X But no , I don't find anything you guys are saying silly , I'm here to learn and learning is both fun and painful.

It's perfectly ok to find something silly. You shouldn't blindly accept whatever we are telling you. Whenever something seems silly or unmotivated to you, it's better that you tell us. That way we can motivate what we're saying and help you ever further.
The problem with explaining this is that we have a lot of experience with proofs and set theory. This makes it very difficult to put ourselves in the shoes of somebody for who all of this is new. So any feedback is really important in order to allow us to adjust our explanations.

 

[reenmachine]

5) If $A\subseteq B$, is it true that $\mathcal{P}(A)\subseteq \mathcal{P}(B)$?

That was a tougher one , trickier.

Here I go:

We will attempt to prove that if A ⊆ B , then ℘(A) ⊆ ℘(B).

Let x ∈ A be arbitrary.If x ∈ A , then {x}⊆ A.

If A ⊆ B , then x ∈ B , therefore {x}⊆ B.

Since {x}⊆ A , then {x}∈ ℘(A) , and since {x}⊆ B , then {x}∈ ℘(B).

Since all subsets of A are subsets of B , all elements of ℘(A) are elements of ℘(B) , proving that if A ⊆ B , then ℘(A) ⊆ ℘(B).

 

[lugita15]

Since all subsets of A are subsets of B

Wait a minute, you didn't prove that all subsets of A are subsets of B. You just proved that all *singleton* subsets of A are subsets of B. What about subsets of A that have more than one element?

 

[reenmachine]

How about that?

We will attempt to prove that if A ⊆ B , then ℘(A) ⊆ ℘(B).

Let x and y ∈ A be arbitrary.If x and y ∈ A , then {x or y}⊆ A.

If A ⊆ B , then x and y ∈ B , therefore {x or y}⊆ B.

Since {x or y}⊆ A , then {x or y}∈ ℘(A) , and since {x or y}⊆ B , then {x or y}∈ ℘(B).

Since all subsets of A are subsets of B , all elements of ℘(A) are elements of ℘(B) , proving that if A ⊆ B , then ℘(A) ⊆ ℘(B).

Take note that by {x or y} , I mean {x} , {y} and {x , y}.

Is that better?

 

[lugita15]

Since all subsets of A are subsets of B

You still haven't proved this. All you've proved is that all subsets of A which have one element or two elements are subsets of B. What about subsets of A that have more than two eleements?

Is that better?

It's better than before, but still not good enough. Here's a hint: Instead of just taking a subset of A that has one or two elements, consider an arbitrary subset of A.

 

[reenmachine]

You still haven't proved this. All you've proved is that all subsets of A which have one element or two elements are subsets of B. What about subsets of A that have more than two eleements?
It's better than before, but still not good enough. Here's a hint: Instead of just taking a subset of A that has one or two elements, consider an arbitrary subset of A.

So just start by saying : Let {x}⊆ A be arbitrary?

Let {x}⊆ A be arbitrary.Since A ⊆ B , it means that all elements of {x} are elements of B , therefore {x}⊆ B.Since {x}⊆ A , then {x}∈ ℘(A) , and since {x}⊆ B , then {x}∈ ℘(B).

Since all subsets of A are subsets of B , all elements of ℘(A) are elements of ℘(B) , proving that if A ⊆ B , then ℘(A) ⊆ ℘(B).

Does that work? If {x}⊆ A is arbitrary , it isn't necessarily a singleton anymore but a subset including an unknown number of elements?

Does this part:''Let {x}⊆ A be arbitrary.Since A ⊆ B , it means that all elements of {x} are elements of B , therefore {x}⊆ B'' proves that all subsets of A are subsets of B?

Another question , I wrote {x} instead of x since it was a subSET , but I didn't want to imply that {x} had only one element of x.Should I say ''Let x ⊆ A be arbitrary'' instead?

 

[Fredrik]

So just start by saying : Let {x}⊆ A be arbitrary?

Since you want to prove that ℘(A)⊆℘(B), you should start by saying "let x∈℘(A) be arbitrary", or equivalently, "let x⊆A be arbitrary".

To let {x}⊆ A be arbitrary is to consider an arbitrary singleton subset of A.

You seem to have the right idea about how to prove this, but the notation makes the proof weird.

 

[reenmachine]

Since you want to prove that ℘(A)⊆℘(B), you should start by saying "let x∈℘(A) be arbitrary", or equivalently, "let x⊆A be arbitrary".

To let {x}⊆ A be arbitrary is to consider an arbitrary singleton subset of A.

You seem to have the right idea about how to prove this, but the notation makes the proof weird.

Let x ⊆ A be arbitrary.Since A ⊆ B , it means that all elements of x are elements of B , which implies that x ⊆ B.Since x ⊆ A , it implies that x ∈ ℘(A) , and since x ⊆ B , it implies that x ∈ ℘(B).

Since all subsets of A are subsets of B , all elements of ℘(A) are elements of ℘(B) , proving that if A ⊆ B , then ℘(A) ⊆ ℘(B).

is that correct?

Hey I really need to start getting them right on the first try :X , for all my mistakes I had the knowledge to realize it but didn't.

 

[reenmachine]

6) calculate $\mathcal{p}(a)$ explictely for

• $a=\emptyset$
• $a = \{0\}$
• $a=\{0,1\}$
• $a=\{0,1,2\}$

1) ℘(a): {∅}
2) ℘(a): {∅}
3) ℘(a): {∅,{1}}
4) ℘(a): {∅,{1},{2},{1,2}}

 

[lugita15]

Let x ⊆ A be arbitrary.Since A ⊆ B , it means that all elements of x are elements of B , which implies that x ⊆ B.Since x ⊆ A , it implies that x ∈ ℘(A) , and since x ⊆ B , it implies that x ∈ ℘(B).

Since all subsets of A are subsets of B , all elements of ℘(A) are elements of ℘(B) , proving that if A ⊆ B , then ℘(A) ⊆ ℘(B).

is that correct?

It's fine for the most part, but if you want to be a bit more precise you can start by saying "let x ∈ ℘(A) be arbitrary", then say that x ⊆ A, then show that x ⊆ B, then say that x ∈ ℘(B), and then say that since all elements of ℘(A) are elements of ℘(B), it follows that ℘(A) ⊆ ℘(B).

 

[lugita15]

1) ℘(A): {∅}
2) ℘(A): {∅}
3) ℘(A): {∅,{1}}
4) ℘(A): {∅,{1},{2},{1,2}}

What about all the subsets that have 0's in them? Also, you seem to have forgotten that for any set A, A is always a subset of itself.

 

[reenmachine]

What about all the subsets that have 0's in them? Also, you seem to have forgotten that for any set A, A is always a subset of itself.

6) calculate $\mathcal{p}(a)$ explictely for

• $a=\emptyset$
• $a = \{0\}$
• $a=\{0,1\}$
• $a=\{0,1,2\}$

Woops! I thought 0 = ∅ but I already knew it was not the case , another brain cramp on my part :X

Corrected version:

1) ℘(A): {∅}
2) ℘(A): {∅ ,{0}}
3) ℘(A): {∅,{0},{1},{0,1}}
4) ℘(A): {∅,{0},{1},{2},{0,1}{0,2}{1,2}{0,1,2}}

 

[reenmachine]

How many elements does $\mathcal{P}(A)$ have if $A=\{0,1,...,n\}$?? With other words: how many subsets does $\{0,1,...,n\}$ have? Just make an educated guess without proof. Proving that your guess is true is quite difficult! It requiress the technique of proof by induction.

Is 2^(n+1) an acceptable answer?

This would complete the exercises you gave me.

 

[lugita15]

Is 2^(n+1) an acceptable answer?

Yes.

 

[Fredrik]

Let x ⊆ A be arbitrary.Since A ⊆ B , it means that all elements of x are elements of B , which implies that x ⊆ B.Since x ⊆ A , it implies that x ∈ ℘(A) , and since x ⊆ B , it implies that x ∈ ℘(B).

Since all subsets of A are subsets of B , all elements of ℘(A) are elements of ℘(B) , proving that if A ⊆ B , then ℘(A) ⊆ ℘(B).

This is good, but some of your statements are a bit awkward. Let me show you how I would do it, before I say anything specific. The statement we want to prove is this one: For all A, if A⊆B, then ℘(A)⊆℘(B). My proof:

Let A be an arbitrary set. Let x∈℘(A) be arbitrary. Since x⊆A and A⊆B, we have x⊆B. This implies that x∈℘(B).​

Compare these two parts of your proof:

Let x ⊆ A be arbitrary.Since A ⊆ B , it means that all elements of x are elements of B,​

which implies that x ⊆ B.Since x ⊆ A , it implies that x ∈ ℘(A)​

The first "it" refers to the thing you said in the previous sentence, but the second "it" refers to the thing you're saying in the first part of the current sentence. There's no need for an "it" in the second sentence. Just write "Since x ⊆ A, we have x ∈ ℘(A)". There's also a big overlap between the statements in the first paragraph (in the quote above) and the statements in the second paragraph. If you're going to say the things in the second paragraph, all of this is unnecessary: "Since x ⊆ A , it implies that x ∈ ℘(A) , and since x ⊆ B , it implies that x ∈ ℘(B)."

 

[reenmachine]

This is good, but some of your statements are a bit awkward. Let me show you how I would do it, before I say anything specific. The statement we want to prove is this one: For all A, if A⊆B, then ℘(A)⊆℘(B). My proof:

Let A be an arbitrary set. Let x∈℘(A) be arbitrary. Since x⊆A and A⊆B, we have x⊆B. This implies that x∈℘(B).​

Compare these two parts of your proof:

Let x ⊆ A be arbitrary.Since A ⊆ B , it means that all elements of x are elements of B,​

which implies that x ⊆ B.Since x ⊆ A , it implies that x ∈ ℘(A)​

The first "it" refers to the thing you said in the previous sentence, but the second "it" refers to the thing you're saying in the first part of the current sentence. There's no need for an "it" in the second sentence. Just write "Since x ⊆ A, we have x ∈ ℘(A)". There's also a big overlap between the statements in the first paragraph (in the quote above) and the statements in the second paragraph. If you're going to say the things in the second paragraph, all of this is unnecessary: "Since x ⊆ A , it implies that x ∈ ℘(A) , and since x ⊆ B , it implies that x ∈ ℘(B)."

What do you mean by ''Let A be an arbitrary set.'' and why is it important?

I get your other points , thanks!

What should I do next? Continue the textbook and start learning about relations? Have I done enough proof of this part of the textbook? I'm getting hungry for some new concepts :D

Also was the 2^(n+1) answer to the micromass question hard to find?

Anyway , thanks again Fredrik , your help is greatly appreciated (same with everybody else helping me here).

 

[Fredrik]

What do you mean by ''Let A be an arbitrary set.'' and why is it important?

It's not. It's just that several times recently, I've found myself saying that the most common mistake made by people who lack experience with proofs, is to not make it clear which ones of their variables have been assigned values, and which ones are targets of a "for all" or a "there exists". So I wanted to make it clear that A is the target of a "for all". Of course, so is B. It doesn't make sense to include the statement "Let A be an arbitrary set" unless we also include something similar for B.

Note that this is the theorem we want to prove: For all A and all B, if A⊆B, we have ℘(A)⊆℘(B). This is an alternative way of saying the same thing: For all A and B such that A⊆B, we have ℘(A)⊆℘(B).

A good way to start the proof is this:

Let A and B be arbitrary sets such that A⊆B. Let x∈℘(A) be arbitrary.​

Here we are explicitly stating the assumptions in the proof. That's never a bad thing. But it's not always required. Since the theorem makes it clear that A and B are arbitrary sets such that A⊆B, it's also OK to just start the proof like this:

Let x∈℘(A) be arbitrary.​

What should I do next? Continue the textbook and start learning about relations? Have I done enough proof of this part of the textbook? I'm getting hungry for some new concepts :D

You should move on. You will have to use these same techniques to prove statements about relations and functions, so it's not like we're leaving them behind.

Also was the 2^(n+1) answer to the micromass question hard to find?

It's fairly easy to guess, if you just count the number of subsets for each of the cases n=1, n=2, n=3. But it's somewhat hard to prove the formula for arbitrary n rigorously, since you have to know how to prove infinitely many statements in a finite number of steps. This is what induction is for. The idea is this: For each non-negative integer k, let P(k) denote the statement "{0,1,...,k} has 2^k+1 subsets". We want to prove the infinitely many statements

P(0)
P(1)
P(2)
...

Induction is the trick to do it by proving only the following two statements:

P(0)
For all integers k such that k≥0, if P(k), then P(k+1).