Basic Set theory question

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

 

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

 

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

 

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

 

[evagelos]

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

thanx

 

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

 

[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

 

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

 

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

 

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

 

[HallsofIvy]

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

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.

 

[HallsofIvy]

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 ?

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

 

[evagelos]

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.

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

 

[mistermath]

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

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

 

[evagelos]

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

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

 

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

 

[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

 

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

 

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

 

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

 

[mathaino]

I feel like there is ambiguity here.

The proofs in mathematics are informal proofs, thus there is always an ambiguity. Say goodbye to the idea that if you learn how to prove like most mathematicians do it you will learn anything not ambigious.

 

[statdad]

The proofs in mathematics are informal proofs, thus there is always an ambiguity. Say goodbye to the idea that if you learn how to prove like most mathematicians do it you will learn anything not ambigious.

Occasionally true, but to say that all proofs are informal, as this comment seems to imply, is foolish.