You are Here: Home >< Maths

# Set Theory- a couple of questions im stuck with to do with cartesian products... Watch

1. Suppose P, Q, R, and S are sets. Prove the following statements about Cartesian products.

(I'm going to use 'n' to mean intersection, 'u' to mean union, and 'E' to mean a member of)

(a) (P × Q) n (R × S) = (P n R) × (Q n S)

and

(b) (P × Q) u (R × S) [is a subset of] (P u R) × (Q u S)

With (a) .. umm .. I've lost the paper with my attempt on it but , I think all I was able to show was that

((pEP) n (qEQ)) n ((rER) n (sES))
but I have no idea how to arrive at (P n R) x (Q n S) , I know how to illustrate them using graphs but I don't know what laws I am allowed to use to manipulate the above equation & my course notes/book don't explain it well at all, I'm a little weak in set theory.

and with (b) I don't know how to begin

any help appreciated + rep !
2. (b) is probably slightly less easier than (a) and also better to demonstrate what you should be doing.

Equality of sets is intimately related to their extension, viz. two sets are determined equal when they have the same elements. If A is a subset of B then every element of A is an element of B and if B is a subset of A then every element of B is an element of A whence A and B are equal.

It is not too difficult to show that if A = B then A is a subset of B and B is a subset of A.

So for (a) you need to prove that LHS is a subset of the RHS and conversely the RHS is a subset of the LHS.

(b);

Let x be an element of (PxQ) u (RxS). It follows that x is either an element of PxQ or RxS (or both), hence x = (p,q) or x = (r,s) for some p in P, q in Q or r in R and s in S (or potentially both, but once again this doesn't really matter because if an element is in both it is in one so we can deal with it then).

If x = (p,q) then the first coordinate is an element of P and the second coordinate is an element of Q. Hence the first coordinate is an element of P or R (potentially adding things is just making our set even bigger!) and similarly q is an element of Q or S whence x is a subset of (P u R) x (Q u S).

If x = (r,s) then the first coordinate is an element of R and the second coordinate is an element of S. Hence the first coordinate is an element of P or R (potentially adding things is just making our set even bigger!) and similarly q is an element of Q or S whence x is a subset of (P u R) x (Q u S).

I hope this has aided you and also showed you why we have inclusion - consider the effect of an element in R but not P and in S but not Q - will this be an element of (P x Q) u (R x S) ?
3. For (a), the approach I would take is something like:

then show which sets a and b each have to be in and finish off by showing that . Make sure to use the double arrows in your working so that you can show that the equivilance works both ways.

(b) Here you want to show that (a,b) in the left hand set implies (a,b) is in the right hand set but your argument will only need to work one way.

I would start this question off with a similar approach to part (a), showing (a in P and b in Q) or (a in R and b in S).

Then use a distributivity law of logic which says . Use that to expand out your previous statement.

Now if x and y are statements then so you can use that law to delete some of your terms in the previous statement. Try and choose terms to delete that will leave you with a statement saying something along the lines of "a is in P or R and b is in Q or S". That way, you'll just have a couple more lines of working to eventually say that (a,b) is in the set given on the right hand side of the question.
4. (Original post by ttoby)
For (a), the approach I would take is something like:

then show which sets a and b each have to be in and finish off by showing that . Make sure to use the double arrows in your working so that you can show that the equivilance works both ways.

(b) Here you want to show that (a,b) in the left hand set implies (a,b) is in the right hand set but your argument will only need to work one way.

I would start this question off with a similar approach to part (a), showing (a in P and b in Q) or (a in R and b in S).

Then use a distributivity law of logic which says . Use that to expand out your previous statement.

Now if x and y are statements then so you can use that law to delete some of your terms in the previous statement. Try and choose terms to delete that will leave you with a statement saying something along the lines of "a is in P or R and b is in Q or S". That way, you'll just have a couple more lines of working to eventually say that (a,b) is in the set given on the right hand side of the question.
Maybe would result in a possibly correct answer but the entirely wrong way to think about proving general propositions in mathematics.

For instance - how do you know you would be able to get an argument to containing nothing but logical equivalences at every step? Usually a single direction is trivial and the reverse is non trivial.

But most importantly you won't be able to prove anything of reasonable depth if you try to push everything in terms of logic.
5. (Original post by ttoby)
.
(Original post by DeanK22)
Maybe would result in a possibly correct answer but the entirely wrong way to think about proving general propositions in mathematics.

For instance - how do you know you would be able to get an argument to containing nothing but logical equivalences at every step? Usually a single direction is trivial and the reverse is non trivial.

But most importantly you won't be able to prove anything of reasonable depth if you try to push everything in terms of logic.
while that is most likely true, i should'v mentioned that this unit im doing is heavily based around logic and so would likely be expected to use logic in the answer here,

& one other thing i notice you mentioned...
"It follows that x is either an element of PxQ or RxS (or both)"
Doesn't union mean either one or the other, but not both?

& thanks to both of you for taking the time to help
6. (Original post by DeanK22)
Maybe would result in a possibly correct answer but the entirely wrong way to think about proving general propositions in mathematics.

For instance - how do you know you would be able to get an argument to containing nothing but logical equivalences at every step? Usually a single direction is trivial and the reverse is non trivial.

But most importantly you won't be able to prove anything of reasonable depth if you try to push everything in terms of logic.
I've often found this sort of approach to be effective on this sort of question. Obviously I don't solve every question I see in this way and yes, there are questions which I find are easier to answer with a wordy explanation. But the advantage with this approach is that if you get it correct then it's correct but with an explanation you risk losing marks if the marker feels that something wasn't explained clearly enough.

But yeah, your answer works well and for a more complicated question like this where it's harder to manipulate the logic, I would have probably done something more similar to what you're suggesting.
7. (Original post by Lewk)
Doesn't union mean either one or the other, but not both?
No that's symmetric difference. http://en.wikipedia.org/wiki/Symmetric_difference
8. (Original post by Lewk)
while that is most likely true, i should'v mentioned that this unit im doing is heavily based around logic and so would likely be expected to use logic in the answer here,

& one other thing i notice you mentioned...
"It follows that x is either an element of PxQ or RxS (or both)"
Doesn't union mean either one or the other, but not both?

& thanks to both of you for taking the time to help
Well we are using the same logic! The trouble is ttoby is erring on the side of super formal logic where you just push symbols around - you do need to know what these symbols mean in order to prove that a v (b v c) is equivalent to (a v b) v c - but after that you are just oushing symbols around.

I STRESS there is no difference in logic and in mathematics more thana nything else we use full English words as logical symbols are extremely difficult tor ead n
and don't offer as much - for instance by adding words for (b) it was simple to see WHY the reverse implication of inclusion (i.e. the LHS is a subset of the RHS) is false but pretty difficult to read a chain of symbols and see that.

The logical operator 'or' includes the case of both.
9. (Original post by ttoby)
Then use a distributivity law of logic which says . Use that to expand out your previous statement.

Now if x and y are statements then so you can use that law to delete some of your terms in the previous statement. Try and choose terms to delete that will leave you with a statement saying something along the lines of "a is in P or R and b is in Q or S". That way, you'll just have a couple more lines of working to eventually say that (a,b) is in the set given on the right hand side of the question.
i don't understand this bit , i can't see how x^y => x if x and y are statements , or in this case, (aEP)^(bEQ) => (aEP)
10. (Original post by Lewk)
i don't understand this bit , i can't see how x^y => x if x and y are statements , or in this case, (aEP)^(bEQ) => (aEP)
If x and y x must be true (and y). Hence x and y implies x.

Or;

If x was false x and y would be false. But x and y is true. Hence x and y implies x.
11. (Original post by Lewk)
i don't understand this bit , i can't see how x^y =&gt; x if x and y are statements , or in this case, (aEP)^(bEQ) =&gt; (aEP)
is true means x and y are both true, so certainly x is true.

This is the step where the implication only holds one way: but going the other way, if you know x is true then you can't then claim that is true because you don't know anything about y.

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: December 10, 2010
Today on TSR

### Degrees to get rich!

... and the ones that won't

### Women equal with Men?

Discussions on TSR

• Latest
• ## See more of what you like on The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

• Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams

## Groups associated with this forum:

View associated groups
Discussions on TSR

• Latest
• ## See more of what you like on The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

• The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.