Question about proof from a guy with a highschool education

[Fredrik]

Why is {a}⊆ A?

Because A={a,b} and every member of {a} is a member of {a,b}. (The only member of {a} is a, and it's a member of {a,b}).

Why is the use of ''{}'' magically appearing to transform element a into subset a?
Why not {a}⊆ ℘(A) instead?

For all x, x is a member of {a} if and only if x=a. So {a} denotes the set whose only member is a.

For all x, x is a member of {a,b} if and only if x=a or x=b. So {a,b} denotes the set whose only members are a and b.

A set is a member of ℘(A) if and only if it's a subset of A. You defined A = {a,b}. If a≠b, a subset of A has 0,1 or 2 members. For each of the numbers 0,1,2, we can easily list all the subsets that have that number of members:

0: ∅
1: {a},{b}
2: {a,b}

So we can immediately conclude that ℘(A) = {∅, {a}, {b}, {a,b}}. (If a=b, we would have ℘(A)={∅,{a}} instead, because A={a}).

The statement {a}⊆ ℘(A) is true if and only if a is equal to one of the sets ∅, {a}, {b}, {a,b}. (It's certainly possible that a=∅ or a={b}, but the equalities a={a} and a={a,b} may not make sense. I need to think about that).

Same confusion with ∅∉A vs ∅∈℘(A), is it only a matter of definitions?

∅ is a subset of every set, because for all x, every member of ∅ is a member of x. (The statement "every member of ∅ is a member of x" can't be false since ∅ doesn't have a member that's not a member of x. And a statement that isn't false is true).

∅ is a member of {a,b} if and only if a=∅ or b=∅.

So to make an analogy with integers , <1,2> = {{1} , {1,2}} but ≠ {{1} , {1,2} , {2}}.

That's right.

Are {1} and {1,2} elements of A , subsets of A or both?

What is A here? Did you mean A=<1,2>? I will assume that you did. {1} and {1,2} are elements of <1,2>, not subsets. 1 and 2 are however said to be components of <1,2>. The first component is 1, the second is 2.

Note however that if you say this to a typical physics student for example, they will not understand what you're talking about. They understand ordered pairs intuitively and have a lot of experience working with them, but they are not familiar with the definition <x,y>={{x},{x,y}}. They may not even be familiar with the notation <x,y>, because they're used to seeing the alternative notation (x,y) instead of <x,y>.

If we use the same technic , it would give us: {<a,∅> , <b,∅>} , but what does that even mean? Can a and ∅ be an ordered pairs?

I'm not sure what technique you're referring to. The definition of the power set? a and ∅ can certainly be the components of an ordered pair. (But I can't think of a situation where we would find this useful).

Last question , suppose you have two sets:

Set A = (1,2,3,4)
Set B = (3,4,5,6)

How do you deal with the intersection in A x B?

I will simplify the example. I assume that you meant {...} when you wrote (...) (I would interpret the latter as meaning the same thing as <...>). If A={1,2} and B={2,3}, then A×B = {<1,2>,<1,3>,<2,2>,<2,3>}, i.e. 2 isn't given any special treatment just because it's a member of both.

 

[reenmachine]

Sorry for answering so late , I had quite the week-end :)

Because A={a,b} and every member of {a} is a member of {a,b}. (The only member of {a} is a, and it's a member of {a,b}).

So basically {a} is a singleton?

For all x, x is a member of {a} if and only if x=a. So {a} denotes the set whose only member is a.

For all x, x is a member of {a,b} if and only if x=a or x=b. So {a,b} denotes the set whose only members are a and b.

A set is a member of ℘(A) if and only if it's a subset of A. You defined A = {a,b}. If a≠b, a subset of A has 0,1 or 2 members. For each of the numbers 0,1,2, we can easily list all the subsets that have that number of members:

0: ∅
1: {a},{b}
2: {a,b}

So we can immediately conclude that ℘(A) = {∅, {a}, {b}, {a,b}}. (If a=b, we would have ℘(A)={∅,{a}} instead, because A={a}).

At the beginning all of this was very confusing , but apparently sitting back for a day and coming back to it works wonders.

Just a very basic question for the sake of ultimate clearness:

If A = {a,b} , then why would {a,b} be a subset of A (therefore becoming an element of ℘(A))?

The statement {a}⊆ ℘(A) is true if and only if a is equal to one of the sets ∅, {a}, {b}, {a,b}. (It's certainly possible that a=∅ or a={b}, but the equalities a={a} and a={a,b} may not make sense. I need to think about that).

Hmm that's a little bit more confusing.

∅ is a subset of every set, because for all x, every member of ∅ is a member of x. (The statement "every member of ∅ is a member of x" can't be false since ∅ doesn't have a member that's not a member of x. And a statement that isn't false is true).

∅ is a member of {a,b} if and only if a=∅ or b=∅.

Very clear.

What is A here? Did you mean A=<1,2>? I will assume that you did. {1} and {1,2} are elements of <1,2>, not subsets. 1 and 2 are however said to be components of <1,2>. The first component is 1, the second is 2.

I'm not even sure what I truly meant LOL.

The way I see it this morning though , is that <1,2> is an ordered pair , which could be expressed as a set by {{1} , {1,2}} , making {1} and {1,2} elements of this set.

1 and 2 are components , but at their root they were elements of sets that were used to make the cartesian product is that correct? To create an ordered pair , you have to take elements from set(s) , and this is where ordered pairs comes from(?).

I'm not sure what technique you're referring to. The definition of the power set? a and ∅ can certainly be the components of an ordered pair. (But I can't think of a situation where we would find this useful).

OK , but what would A X B gives us if A={1,2} and B={∅}?

<1,∅> , <2,∅> ?

I will simplify the example. I assume that you meant {...} when you wrote (...) (I would interpret the latter as meaning the same thing as <...>). If A={1,2} and B={2,3}, then A×B = {<1,2>,<1,3>,<2,2>,<2,3>}, i.e. 2 isn't given any special treatment just because it's a member of both.

Yes I meant {...} , sorry about that.Very clear again.Can't thank you enough.

To conclude this post , I'm still having trouble understanding the use of cartesian products or where does ordered pairs should be.When you are saying that A×B = {<1,2>,<1,3>,<2,2>,<2,3>} , what are the ordered pairs here? Elements? Subsets? Do we keep the ordered pair symbols to ensure that we don't forget that <1,2> are placed in a specific order whereas with {1,2} there's no order?

Just for a quick update on my (slow) progress , I'm getting into relations now.

 

[micromass]

So basically {a} is a singleton?

Yes.

At the beginning all of this was very confusing , but apparently sitting back for a day and coming back to it works wonders.

It always works wonders in math! I don't know why, but coming back to the same question after a day usually works.

Just a very basic question for the sake of ultimate clearness:

If A = {a,b} , then why would {a,b} be a subset of A (therefore becoming an element of ℘(A))?

You say that $B\subseteq A$ if every element of $B$ is an element of $A$. In your case, you have $\{a,b\}\subseteq A$. Indeed: what are the elements of $A$? They are $a$ and $b$. What are the elements of $\{a,b\}$, they are $a$ and $b$. So every element of $\{a,b\}$ is an element of $A$.

The way I see it this morning though , is that <1,2> is an ordered pair , which could be expressed as a set by {{1} , {1,2}} , making {1} and {1,2} elements of this set.

1 and 2 are components , but at their root they were elements of sets is that correct? To create an ordered pair , you have to take elements from set(s) , and this is where ordered pairs comes from(?).

You can create an ordered pair just by taking two arbitrary elements. They don't need to be elements of the same set (but they often are).

For example, I can take a pig and I can take the number $2$ and I can form
$(2,\text{pig}) = \{\{2\}, \{2,\text{pig}\}\}$.
I do need to say that this only works in naive set theory, but formal set theory is more restrictive. Don't worry about that for now though.

OK , but what would A X B gives us if A={1,2} and B={∅}?

<1,∅> , <2,∅> ?

Yes, it would give $A\times B=\{(1,\emptyset),(2,\emptyset)\}$.

To conclude this post , I'm still having trouble understanding the use of cartesian products or where does ordered pairs should be.When you are saying that A×B = {<1,2>,<1,3>,<2,2>,<2,3>} , what are the ordered pairs here? Elements? Subsets?

They are elements of $A\times B$. So $(1,3)\in A\times B$.

Do we keep the ordered pair symbols to ensure that we don't forget that <1,2> are placed in a specific order whereas with {1,2} there's no order?

Yes, that is basically the only reason we bother with ordered pairs. We know that $(1,2)\neq (2,1)$ (you should try to prove this actually!). But we know that $\{1,2\}=\{2,1\}$. So we care about ordered pairs because they give some kind of order.

Just for a quick update on my (slow) progress , I'm getting into relations now.

I recommend you to make some exercises on the things you've already seen. If you want, I can give you good exercises that you should consider.

 

[reenmachine]

It always works wonders in math! I don't know why, but coming back to the same question after a day usually works.

That's good.What I like is doing a little bit of sport to clear the mind.

You say that $B\subseteq A$ if every element of $B$ is an element of $A$. In your case, you have $\{a,b\}\subseteq A$. Indeed: what are the elements of $A$? They are $a$ and $b$. What are the elements of $\{a,b\}$, they are $a$ and $b$. So every element of $\{a,b\}$ is an element of $A$.

So A ⊆ A?

You can create an ordered pair just by taking two arbitrary elements. They don't need to be elements of the same set (but they often are).

For example, I can take a pig and I can take the number $2$ and I can form
$(2,\text{pig}) = \{\{2\}, \{2,\text{pig}\}\}$.
I do need to say that this only works in naive set theory, but formal set theory is more restrictive. Don't worry about that for now though.

Very clear!

They are elements of $A\times B$. So $(1,3)\in A\times B$.

Can we name the A x B set , like A x B = Set C , so that (1,3) ∈ F?

Yes, that is basically the only reason we bother with ordered pairs. We know that $(1,2)\neq (2,1)$ (you should try to prove this actually!). But we know that $\{1,2\}=\{2,1\}$. So we care about ordered pairs because they give some kind of order.

Hmm , let me give it a quick try.

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} it proves that (1,2) ≠ (2,1).

(I'm not sure whether or not I have to prove that {1} ≠ {2})

I recommend you to make some exercises on the things you've already seen. If you want, I can give you good exercises that you should consider.

Of course! That would be fantastic! Thanks a lot!

 

[micromass]

So A ⊆ A?

Yes, this is always true. Here is something you should try to prove:

A=B ~\text{if and only if}~A\subseteq B~\text{and} ~B\subseteq A

So there are two directions here, you already proved one!

Can we name the A x B set , like A x B = Set C , so that (1,3) ∈ F?

What is $F$??

Yes, you can say $A\times B = C$, and then $(1,3)\in C$. Saying "= Set C" is not a good notation though, just say "=C", it is clear that it's a set from context.

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}}.

Both ordered pairs expressed as sets have unique elements ({1} in (1,2) and {2} in (2,1)) , and since {1} ≠ {2} , then (1,2) ≠ (2,1).

Hmmm, that is not enough. You indeed want to prove that $\{\{1,\},\{1,2\}\} \neq \{\{2\},\{2,1\}\}$. So you want to show this by saying that $\{1\}$ is an element of the LHS but not of the right hand side.

But to show this, you need to show that $\{1\}$ is not an element of $\{\{2\},\{2,1\}\}$. But to see that, you need that $\{1\} \neq \{2\}$ AND $\{1\}\neq \{1,2\}$. Just saying that $\{1\}\neq \{2\}$ is not enough.

Of course! That would be fantastic! Thanks a lot!

OK, here are some things you should try:

1) Remember that equality of sets is defined as follows: $A=B$ is true if all elements of $A$ are in $B$ and if all elements of $B$ are in $A$.
Prove:

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

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$.

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

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?)

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

6) Calculate $\mathcal{P}(A)$ explictely for

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

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.

 

[reenmachine]

What is $F$??

Just a typo.Meant C.

Hmmm, that is not enough. You indeed want to prove that $\{\{1,\},\{1,2\}\} \neq \{\{2\},\{2,1\}\}$. So you want to show this by saying that $\{1\}$ is an element of the LHS but not of the right hand side.

But to show this, you need to show that $\{1\}$ is not an element of $\{\{2\},\{2,1\}\}$. But to see that, you need that $\{1\} \neq \{2\}$ AND $\{1\}\neq \{1,2\}$. Just saying that $\{1\}\neq \{2\}$ is not enough.

I was editing my post as you wrote , but I questionned the completeness of {1} ≠ {2}.I don't understand how I can prove it.Or did you mean I had to write BOTH , and not just {1} ≠ {2}?

EDIT: On second thought , you could say that {1} ≠ {1,2} because set {1} has only one element in 1 and set {1,2} have 2 elements in 1 and 2.Since 2 isn't in {1} , then {1} ≠ {1,2}.

I have to go out for dinner so I will try your exercices later today or tomorrow and post my results.

Thanks!

 

[micromass]

Just a typo.Meant C.



I was editing my post as you wrote , but I questionned the completeness of {1} ≠ {2}.I don't understand how I can prove it.Or did you mean I had to write BOTH , and not just {1} ≠ {2}?

You, you had to write both.

EDIT: On second thought , you could say that {1} ≠ {1,2} because set {1} has only one element in 1 and set {1,2} have 2 elements in 1 and 2.Since 2 isn't in {1} , then {1} ≠ {1,2}.

That works. But I want to note that this can be tricky. For example, $\{1,1\}=\{1\}$ (prove it!). So apparently $\{1,1\}$ contains 2 elements, but it actually contains only one.

Your approach works of course since $1\neq 2$. So it's all good. But don't think that $\{x,y\}$ always contains two elements!

 

[reenmachine]

You, you had to write both.
That works. But I want to note that this can be tricky. For example, $\{1,1\}=\{1\}$ (prove it!). So apparently $\{1,1\}$ contains 2 elements, but it actually contains only one.

Your approach works of course since $1\neq 2$. So it's all good. But don't think that $\{x,y\}$ always contains two elements!

{1} = {1,1} because both sets have only one element in 1.They are composed of the same single element , making them identical sets and therefore the same set and singleton.

...or all elements of {1} are in {1,1} and all elements of {1,1} are in {1}.

{x,y} is not necessarily composed of 2 elements because it's possible that x=y or that x or y = ∅

 

[reenmachine]

delete this post

sorry.

 

[Fredrik]

{1} = {1,1} because both sets have only one element in 1.They are composed of the same single element , making them identical sets and therefore the same set and singleton.

...or all elements of {1} are in {1,1} and all elements of {1,1} are in {1}.

Correct.

{x,y} is not necessarily composed of 2 elements because it's possible that x=y or that x or y = ∅

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

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.

 

[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?