# Basic Set theory question

1. Sep 14, 2008

### Diffy

Hi!

I am having trouble constructing the sentences in this proof.

Its very simple, proof that $$A \cup \left( B \cap C \right) = \left( A \cup B \right) \cap \left( A \cup B \right)$$

So basically I need to show that if $$x \in A \cup \left( B \cap C \right)$$ then $$x \in \left( A \cup B \right) \cap \left( A \cup B \right)$$

Here is what I got:

If $$x \in A \cup \left( B \cap C \right)$$ then $$x \in A$$ or $$x \in \left( B \cap C \right)$$. Which means that either $$x \in A$$, or $$x \in B$$ and $$x \in C$$...

-----------------------------------------
First Question,

I feel like there is ambiguity here. "Either x in A, or x in B and x in C " can be interpreted two ways right? You could read it: $$x \in \left( A \cup B \right) \cap C$$ or you could read it as intended $$x \in A \cup \left( B \cap C \right)$$ How can I make the sentence clear that I want the latter?

Second question,

From here is it ok for me to make the jump to x in A or B, and x in A or C? It seems clear to me that this is the case, but I am not sure if something is left to be said before I make this claim.

Thanks for help!

2. Sep 14, 2008

### PowerIso

I'll do my best to answer.
First off while yes you need to show what you say you need to show, but you also have to show that if $$x \in \left( A \cup B \right) \cap \left( A \cup B \right)$$ then $$x \in A \cup \left( B \cap C \right)$$. This is because = is essentially a bi-conditional statement, so you need to show that the left side is a subset of the right side but also that the right side is a subset of the left side. If that is true, then they are equal.

Secondly, I would simply write "x is a member of A or x is a member of the intersection of B and C." Do you have to write that part in words? Seems like symbolic would be better.

I think you can make that jump, but you should clarify why you are making the jump.

3. Sep 15, 2008

### Diffy

Thanks that helps, I have finished it and I think made it perfectly clear. And yes I am aware that I have to show it both ways. If I can get it one way going backwards is usually very easy.

I have another one, that I am stuck on at the moment and maybe you would be so kind to help. Latex was taking too long so I am going to try to write it out using no Latex.

Show that (A - B) x C = (A x C) - (B x C)

So I start the same way

let (x, y) /in (A - B) x C.

This is the set {(x,y) | x in A and x not in B, y in C}

I Want to be able to say the following:

This is the same as saying all x in A and y in C, and all x not in B and y not in C.

But I am not sure I can make this leap, does this need justification?

4. Sep 16, 2008

### Diffy

Ok things were a bit more complicated than I thought they would be...

But that was because I didn't understand what the complement of BxC was until I drew myself a picture.

But I solved it, and now I am moving on, thanks!

5. Sep 16, 2008

### evagelos

WOULD you care to give a short proof of the above i am just curious

thanx

6. Sep 19, 2008

### mistermath

One direction is:
(A - B) x C = (A x C) - (B x C)

Let (a,c) in (A - B) x C then a in A - B and c in C.

a in A - B -> a in A and A not in B.

a in A and c in C -> (a,c) in A x C.

a not in B -> (a , x) not in B x C for all x. (in particular our c).

therefore (a, c) in (A x C) - (B x C) as (a, c) in A x C and (a, c) not in B x C.

7. Sep 19, 2008

### evagelos

According to what theorem axiom or law of logic do you get and i quote;

.........a not in B -> (a , x) not in B x C for all x. (in particular our c)..........................

I am sorry i can make no justification for that step

8. Sep 19, 2008

### Diffy

Let A and B be a set.
Assume for some a, a is not contained in A.

AxB = all (x, y) such that x in A and y in B.

since a is not in A (a, y) can not be in AxB for any y.

9. Sep 19, 2008

### mistermath

Yeah what Diffy said. In other more formal terms:
By definition A x B = { (a,b) | a in A and b in B }

For a given (x, y) to be in A x B, x must be in A and y must be in B, so if (x , y) is not in A x B, then either x not in A or y not in B, or both of course, but we take that for granted :)

10. Sep 19, 2008

### evagelos

Each step in amathematical proof is justified by either a theorem ,an axiom,a definition or a law of logic words like because.......but of course.......obviously.............can you see ..............its easy e.t.c have no place at all.

Things that you may understand or you think you understand other people may not, so how are you going to convince them ?

11. Sep 20, 2008

### HallsofIvy

Staff Emeritus
The justification is the definition of "B x C".

B x C is defined as the set of all pairs (x, y) such that x is in B and y is in C. If a is not in B, then there is no pair in B x C with first member a- i.e. (a, x) is not in B x C for any x.

12. Sep 20, 2008

### HallsofIvy

Staff Emeritus
Which post was this in response to? No one has said any thing like that.

13. Sep 20, 2008

### evagelos

so how do we prove:

~aεB ====> ~(a,x)ε(B x C) ,for all x?

your reasoning is rather intuitive is just like saying can 2+2 be other than 4?

but this can be proved too

14. Sep 20, 2008

### mistermath

Are you ok with the following statement?
If a is not in B, then there is no pair in B x C with first member a.

I would say it's by definition, but suppose there exists a c such that (a, c) in B x C, then
a in B and c in C by definition.

Contradition because we said a not in B by assumption. I bolded the 2 contradictory things.
The c was chosen as any arbitraty element of C, therefore no c in C works.

That's where I got the statement:
(a, x) is not in B x C for any x. (and in particular, the x's in C since x not in C would be "even more" not in B x C).

15. Oct 3, 2008

### evagelos

..........................................correct.....................................................

after all there is a proof by contradiction.

another way to show that ~(a,c)ε(BxC) i.e (a,c)does not belong to BxC IS THE following:

~aεΒ ===> ~aεB v ~cεC ( BY disjunction introduction) ===> ~( aεA^ cεC ) ( BY de morgan) ====> ~(a,c)ε(ΒxC)

16. Oct 3, 2008

### statdad

\begin{align*} (x,y) & \in (A-B) \times C \quad \text{means}\\ x \in A-B, & y \in C \quad \text{so}\\ x \in A, x \not \in B & y \in C \quad \text{so}\\ (x,y) & \in A \times C, (x,y) \not \in B \times C \quad \text{so}\\ (A-B) \times C & \subseteq (A \times C) - (B \times C) \end{align*}

To go the other way

\begin{align*} (x,y) & \in (A \times C) - (B \times C) \quad \text{means}\\ (x,y) \in A \times C, & (x,y) \not \in B \times C \quad \text{so} \\ \left(x \in A \text{ and } y \in C \right) & \text{ and } \left(x \not \in B \text{ and } y \in C\right) \quad \text{so}\\ x \in A-B & \text{ and } y \in C \quad \text{which gives}\\ x \in (A-B) \times C \end{align*}

so that

$$(A \times C) - (B \times C) \subseteq (A-B) \times C$$

These two give the equality of the sets - no need for reference to quantifiers or symbolic logic - just the definitions of Cartesian product, set equality, and subsets.

17. Oct 3, 2008

### evagelos

Nearly all proofs in set theory after dropping quantifiers are based on proofs in symbolic logic .

And in our example this can be shown in the following way.

(A-B)xC= (AxC)-(BxC) <===> {(x,y)ε[(A-B)xC] <====> {(x,y)ε[(AxC)-(BxC)]} <====>

{ [(xεA & ~xεB) & yεC] <=====> [ ( xεA & yεC) & ~(xεB & yεC)]},and if we put now, xεA=P , xεB=q, yεC=r the above becomes.

p & ~q & r <====> p & r & ~( q & r) and this is problem in propositional calculus

Hence a virtuoso in symbolic logic will not miss a proof in set theory,after dropping quantifiers that is

18. Oct 4, 2008

### statdad

"Hence a virtuoso in symbolic logic"

If I ever see anything written by one I'll be impressed.
I am aware (probably more than you) of the relationships. However, I am also aware that people who ask for guidance in one area are typically not interested in showmanship, which is all you seem intent on offering.

If this post is "beyond the pale" as our locale saying goes, I expect the moderators will delete it; I accept their decision in advance.

19. Oct 4, 2008

### evagelos

I am sorry for the sentence "hence a virtuoso in sumbolic................."

My intentions are not showmanship.

But is not a fact that in the heart of the proof of each set problem is symbolic logic??

20. Oct 4, 2008

### statdad

Thank you for your apology - I owe a larger one to you.
There is no doubt that set theory and symbolic logic are deeply intertwined - I stress the similarities when I teach our only class (unfortunately a survey class) that covers both topics.
The point I wanted make (and which, re-reading, bollixed tremendously) is that elegant as it may be, a brief proof of the result written in the language and notation of logic might not provide a glimpse at the mechanics a person studying an introduction to set theory needs.
It wasn't a comment on ability, or elegance, but on suitability at this level.

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?