Question about proof from a guy with a highschool education

[reenmachine]

Correct, but I need to add that if x=∅ and y≠∅, then {x,y} has two elements.

Hmmmm , I thought ∅ wasn't an element of any set except if it's used as a {∅} in a powerset.So ∅ is an element of a set? Thought it was only a subset of every set.

Little bit confused here.

edit: in fact you already explained this to me by saying in a earlier post that ∅ is a member of {x,y} iff x=∅ or y=∅.I'm not sure I understand the logic behind it , but I understand the rule.

If you want more exercises, you can just try to prove the identities in section 1.8 of the document you're reading. http://people.umass.edu/partee/NZ_2006/Set Theory Basics.pdf. The solutions should all look a lot like what I did in post #37. Several of the exercises that micromass suggested can be dealt with using the same method.

That's great , I already saw that there was more exercices in those textbooks , just not there yet , but I'll try exercises later today and tomorrow and post some results for verification :D

thanks!

 

[reenmachine]

Prove:

• $A=A$
• If $A=B$, then $B=A$
• If $A=B$ and $B=C$, then $A=C$

First try at the first proof:

In this proof we are accepting the axioms of Zermelo–Fraenkel set theory with choice.We will attempt to prove that if A = B and B = C , then A = C.

All the elements of A are elements of A and all elements of A are elements of A (which means the same thing) , therefore A = A.

All elements of A are elements of B and all elements of B are elements of A , therefore A = B and B = A.

All elements of B are elements of C and all elements of C are elements of B , therefore B = C.

All elements of B(= A) are elements of C and all elements of C are elements of B(= A) , proving that if A = B and B = C , then A = C.

edit: (sorry I had a brain cramp and didn't use the symbols . will use them for the others)

edit2: also I'm not sure whether you ask me to prove the three of them or simply the last one?

 

[reenmachine]

2) Show that for any sets $A,B,C$ holds that

• $A\subseteq A$ (you already done this)
• If $A\subseteq B$ and $B\subseteq A$, then $A=B$. (again: remember the definition of equality of sets)
• If $A\subseteq B$ and $B\subseteq C$, then $A = C$.

I have problems understanding how the third one could be right.

Can I try to disprove?

We will attempt here to disprove that if A = B , A ⊆ B and B ⊆ C , then A = C.We are accepting the axioms of Zermelo–Fraenkel set theory with choice.

If A ⊆ B and B ⊆ A , then by definition A = B since all elements of A are elements of B and all elements of B are elements of A.

If A ⊆ B and B ⊆ C , it means that all elements of A and B are elements of C.

If A = {1,2} and A = B , then B = {1,2}.Since B ⊆ C , {1,2} are elements of C.

But if C is {1,2,3,4} , then A ≠ C , because not all elements of C are elements of A.

A = {1,2} ⊆ B since B = {1,2}.Same thing with B ⊆ A.If B = {1,2} and C = {1,2,3,4} , then B ⊆ C.

But since A = {1,2} and C = {1,2,3,4} , elements 3 and 4 aren't elements of A , therefore the statement ''if A = B , A ⊆ B and B ⊆ C , then A = C'' is incorrect.

(The correct statement would be ''if A = B , A ⊆ B and B ⊆ C , then A ⊆ C).

The (dis)proof would still be correct if A ≠ B.If A = {1,2} , B = {1,2,3,4} and C = {1,2,3,4,5,6} , the same logical steps would apply.

 

[reenmachine]

3) Is it always true that $A\times B = B\times A$??

No , because if A = {1} and B = {2} , then A x B = (1,2) and B x A = (2,1).

Since (1,2) ≠ (2,1) (proved below) , then A x B ≠ B x A.

Proof of (1,2) ≠ (2,1):

In this proof we are accepting the axioms of Zermelo–Fraenkel set theory with choice.We will attempt to prove that (1,2) ≠ (2,1).

First let's express the ordered pairs into sets: (1,2) = {{1},{1,2}} and (2,1) = {{2},{2,1}}.

As we can see , both ordered pairs expressed as sets have unique elements ({1} in (1,2) but not in (2,1) and {2} in (2,1) but not in (1,2)) , and since {1} ≠ {2} and {1} ≠ {1,2} it proves that (1,2) ≠ (2,1).

I will wait for your response and try the others tomorrow or later tonight if you respond today.

 

[reenmachine]

Ah I confused it all , I was supposed to prove each of the statements , not just the last one :X

Tell me what you think when you have the time :)

 

[Fredrik]

All the elements of A are elements of A and all elements of A are elements of A (which means the same thing) , therefore A = A.

Correct.

All elements of A are elements of B and all elements of B are elements of A , therefore A = B and B = A.

Here you haven't made it clear what's the assumption and what's the conclusion. You should have said that since A=B, your first statement holds, and this result implies that B=A. You could also have said that your first statement is equivalent to both A=B and B=A.

All elements of B are elements of C and all elements of C are elements of B , therefore B = C.

Why does the first statement hold? It holds if B=C. So it looks like what you're proving here is that if B=C, then B=C.

All elements of B(= A) are elements of C and all elements of C are elements of B(= A) , proving that if A = B and B = C , then A = C.

It's not clear what you're doing here. However, since all elements of A are elements of B (this follows from A=B), and all elements of B are elements of C (this follows from B=C), all elements of A are elements of C. The proof that all elements of C are elements of A is similar. These two results imply that A=C.

When the statement you're proving is more complicated, it's going to be very hard to read the proof if it's structured like what I just did (long sentences in plain English). It will be easier to follow if you start by saying: Let $x\in A$ be arbitrary. (This means "let x be an arbitrary element of A"). Then you can continue: Since A=B, this implies that $x\in B$. Since B=C, this implies that $x\in C$.

Then you can say "Now let $x\in C$ be arbitrary" and prove that $x\in A$.

 

[Fredrik]

I have problems understanding how the third one could be right.

Can I try to disprove?

We will attempt here to disprove that if A = B , A ⊆ B and B ⊆ C , then A = C.We are accepting the axioms of Zermelo–Fraenkel set theory with choice.

If A ⊆ B and B ⊆ A , then by definition A = B since all elements of A are elements of B and all elements of B are elements of A.

If A ⊆ B and B ⊆ C , it means that all elements of A and B are elements of C.

If A = {1,2} and A = B , then B = {1,2}.Since B ⊆ C , {1,2} are elements of C.

But if C is {1,2,3,4} , then A ≠ C , because not all elements of C are elements of A.

A = {1,2} ⊆ B since B = {1,2}.Same thing with B ⊆ A.If B = {1,2} and C = {1,2,3,4} , then B ⊆ C.

But since A = {1,2} and C = {1,2,3,4} , elements 3 and 4 aren't elements of A , therefore the statement ''if A = B , A ⊆ B and B ⊆ C , then A = C'' is incorrect.

(The correct statement would be ''if A = B , A ⊆ B and B ⊆ C , then A ⊆ C).

The (dis)proof would still be correct if A ≠ B.If A = {1,2} , B = {1,2,3,4} and C = {1,2,3,4,5,6} , the same logical steps would apply.

I see that you were a bit confused about what you were supposed to prove. The three statements on the list are three theorems that don't have anything to do with each other. So the fact that the conclusion in the second one is A=B doesn't mean that you can use A=B as an assumption in the third one.

You're right that the third one is wrong. It should be

If $A\subseteq B$ and $B\subseteq C$, then $A\subseteq C$.​

All you have to do to disprove the mistyped statement (the one that ends with A=C) is to find one example of sets A,B,C such that this doesn't hold. You can make it very simple: A={0}, B={0,1}, C={0,1,2}. We have $A\subseteq B$, $B\subseteq C$, and $A\neq C$.

Note that all of the statements you were asked to prove are really "for all" statements, where the "for all" has been omitted out of habit. These are the full statements:

• For all A, we have $A\subseteq A$.
• For all A, B, if $A\subseteq B$ and $B\subseteq A$, then $A=B$.
• For all A,B,C, if $A\subseteq B$ and $B\subseteq C$, then $A\subseteq C$.

The best way to start a proof of the last one is: Let A,B,C be arbitrary sets such that $A\subseteq B$ and $B\subseteq C$. (This way you make it clear what the assumption is). Let x be an arbitrary element of A.

Then you use the assumptions to prove that x is an element of C.

 

[Fredrik]

No , because if A = {1} and B = {2} , then A x B = (1,2) and B x A = (2,1).

Since (1,2) ≠ (2,1) (proved below) , then A x B ≠ B x A.

Proof of (1,2) ≠ (2,1):

In this proof we are accepting the axioms of Zermelo–Fraenkel set theory with choice.We will attempt to prove that (1,2) ≠ (2,1).

First let's express the ordered pairs into sets: (1,2) = {{1},{1,2}} and (2,1) = {{2},{2,1}}.

As we can see , both ordered pairs expressed as sets have unique elements ({1} in (1,2) but not in (2,1) and {2} in (2,1) but not in (1,2)) , and since {1} ≠ {2} and {1} ≠ {1,2} it proves that (1,2) ≠ (2,1).

I will wait for your response and try the others tomorrow or later tonight if you respond today.

This is fine. (Edit: Except for a mistake in the notation. See micromass' post below). The reason why a counterexample is sufficient is that we're disproving a "for all A,B" statement. You could however have ended the proof after noting that {1} is in (1,2), but not in (2,1). It wasn't necessary to also point out that {2} is in (2,1) but not in (1,2).

You could also have ended the proof right after showing that A×B={(1,2)} and B×A={(2,1)}, by referring to a theorem that says that (a,b)=(c,d) if and only if a=c and b=d. This is proved in all the set theory books. I know I've seen the proof in Goldrei, and I would be very surprised if it's not in Hrbacek and Jech as well.

By the way, you don't have to type an x. When you type a post (in advanced mode), there's a field of "quick symbols" to the right. You can insert an × by clicking on that symbol there.

 

[micromass]

No , because if A = {1} and B = {2} , then A x B = (1,2) and B x A = (2,1).

The notation is off. It should be $A\times B = \{(1,2)\}$ and not $A\times B = (1,2)$. Same for $B\times A$.

A natural question: "determine" all $A$ and $B$ such that equality holds.

 

[Fredrik]

The notation is off. It should be $A\times B = \{(1,2)\}$ and not $A\times B = (1,2)$.

Oops, I didn't even notice that.

 

[micromass]

Oops, I didn't even notice that.

You might want to correct your post too

 

[Fredrik]

You might want to correct your post too

Yes, I just typed the same thing reenmachine did and didn't even notice. I have edited it now.

 

[reenmachine]

Hey guys I just woke up so I'll wait a little bit before going into details with the previous exercises , but I wanted to ask you how you were using all the symbols without copy-pasta? I know there's 42 symbols in the advanced mode but there's some missing like ''is a subset of''.

thanks , will get back at you later today :D

cheers

 

[Fredrik]

We use LaTeX. The code for $\subseteq$ is \subseteq. More information here.

If you want to see how we do it, you can just hit the quote button next to the post where we did it.

 

[reenmachine]

Here you haven't made it clear what's the assumption and what's the conclusion. You should have said that since A=B, your first statement holds, and this result implies that B=A. You could also have said that your first statement is equivalent to both A=B and B=A.

So simply saying: Since A=B , all elements of A are elements of B and vice versa , and this result implies that B=A?

Why does the first statement hold? It holds if B=C. So it looks like what you're proving here is that if B=C, then B=C.

Should've said: Since B=C , then all elements of B are elements of C and all elements of C are elements of B?

When the statement you're proving is more complicated, it's going to be very hard to read the proof if it's structured like what I just did (long sentences in plain English). It will be easier to follow if you start by saying: Let $x\in A$ be arbitrary. (This means "let x be an arbitrary element of A"). Then you can continue: Since A=B, this implies that $x\in B$. Since B=C, this implies that $x\in C$.

Then you can say "Now let $x\in C$ be arbitrary" and prove that $x\in A$.

Yeah even when I re-read myself I admit this wasn't clear , I still have troubles clearly expressing my train of thoughts.In my mind the proof is clear.

Just for the sake of ultimate clearness , when you say "let x be an arbitrary element of A" , what does arbitrary means?

 

[reenmachine]

I see that you were a bit confused about what you were supposed to prove. The three statements on the list are three theorems that don't have anything to do with each other. So the fact that the conclusion in the second one is A=B doesn't mean that you can use A=B as an assumption in the third one.

I saw that afterward , just didn't have time to re-do everything.I noticed I was suppose to prove all three statements separately.As far as the A=B being out of place , I did mentionned that the (dis?)proof still worked even if A ≠ B at the end of my post.

You're right that the third one is wrong. It should be

If $A\subseteq B$ and $B\subseteq C$, then $A\subseteq C$.​

All you have to do to disprove the mistyped statement (the one that ends with A=C) is to find one example of sets A,B,C such that this doesn't hold. You can make it very simple: A={0}, B={0,1}, C={0,1,2}. We have $A\subseteq B$, $B\subseteq C$, and $A\neq C$.

I did this didn't I? Except the misplaced A=B error , I think I did all of the above.

Note that all of the statements you were asked to prove are really "for all" statements, where the "for all" has been omitted out of habit. These are the full statements:

• For all A, we have $A\subseteq A$.
• For all A, B, if $A\subseteq B$ and $B\subseteq A$, then $A=B$.
• For all A,B,C, if $A\subseteq B$ and $B\subseteq C$, then $A\subseteq C$.

OK , it was already implied in my mind too.

 

[reenmachine]

The notation is off. It should be $A\times B = \{(1,2)\}$ and not $A\times B = (1,2)$. Same for $B\times A$.

A natural question: "determine" all $A$ and $B$ such that equality holds.

True.Just a brain cramp on my part.

 

[reenmachine]

We use LaTeX. The code for $\subseteq$ is \subseteq. More information here.

If you want to see how we do it, you can just hit the quote button next to the post where we did it.

Great , I'll try to learn them all but it might take me a couple of weeks.For the moment I might or might not use it but I'll try to be as clean and clear as possible in my posts.

Will try the other exercises soon and post the result , they look fun to try to prove.

thanks

 

[micromass]

So simply saying: Since A=B , all elements of A are elements of B and vice versa , and this result implies that B=A?

First I want to say that your proof is completely fine. But the point Fredrik wants to make is that proofs have a very distinct style that you need to get used to. This might seem tedious and unnecessary for these kind of proofs (and you're right), but it's the way we do things. Plus: it makes more difficult proofs easier.

Let's say that I want to prove B=A when I'm given A=B.
I want to prove B=A. So I want to prove that all elements of B are in A and that all elements of A are in B.
So take an arbitrary element x of B. But since A=B, we know that all elements of A are in B and that all elements of B are in A. The latter implies that x is in A. So all elements of B are in A.
Now, take an arbitrary element x of A. Since A=B, we know that all elements of A are in B and that all elements of B are in A. The former implies that x is in B. So all elements of A are in B.
Thus we get B=A.

This is a very longwinded way to prove this simple thing. But this is the style we always prove things.
So let's say that we want to prove something like C=D. A "meta"-proof would look like this:

Take an arbitrary element x in C. Use what you know about C and about D. Conclude that x is in D.
Take an arbitrary element x in D. Use what you know about C and about D. Conclude that x is in C.

Just for the sake of ultimate clearness , when you say "let x be an arbitrary element of A" , what does arbitrary means?

It means that the only thing you know is that x is in A. You can't use anything else.

So, if I say: take x an arbitrary element of $\mathbb{R}$. Then I only know that x is a real number. So I can't say that x=0 or x=1. You don't know any of those specifics.

 

[reenmachine]

4) Prove the following (again: remember the definition of equality)

• $A\cap (B\cap C) = (A\cap B)\cap C$. Formulate something analogous for unions
• $A\cap (B\cup C) = (A\cap B)\cup (A\cap C)$.
• $A\cap A = A$ and $A\cup A=A$
• $(A\cap B)\times C = (A\times C)\cap (B\times C)$. Is the same true if we replace intersection by union?)

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

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

If you want the proof , I would try:

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

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.

----------------------
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.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) , 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.

----------------------
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∩Bthoughts?

 

[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).