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 !

Lewk
 Follow
 3 followers
 2 badges
 Send a private message to Lewk
 Thread Starter
Offline2ReputationRep: Follow
 1
 08122010 16:03

Oh I Really Don't Care
 Follow
 2 followers
 2 badges
 Send a private message to Oh I Really Don't Care
Offline2ReputationRep: Follow
 2
 08122010 16:23
(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) ? 
 Follow
 3
 08122010 16:33
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.Last edited by ttoby; 08122010 at 16:35. 
Oh I Really Don't Care
 Follow
 2 followers
 2 badges
 Send a private message to Oh I Really Don't Care
Offline2ReputationRep: Follow
 4
 08122010 16:43
(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.
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. 
Lewk
 Follow
 3 followers
 2 badges
 Send a private message to Lewk
 Thread Starter
Offline2ReputationRep: Follow
 5
 08122010 17:09
(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.
& 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 helpLast edited by Lewk; 08122010 at 17:12. 
 Follow
 6
 08122010 17:15
(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.
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. 
 Follow
 7
 08122010 17:18
(Original post by Lewk)
Doesn't union mean either one or the other, but not both? 
Oh I Really Don't Care
 Follow
 2 followers
 2 badges
 Send a private message to Oh I Really Don't Care
Offline2ReputationRep: Follow
 8
 08122010 17:30
(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
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. 
Lewk
 Follow
 3 followers
 2 badges
 Send a private message to Lewk
 Thread Starter
Offline2ReputationRep: Follow
 9
 10122010 00:37
(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. 
Oh I Really Don't Care
 Follow
 2 followers
 2 badges
 Send a private message to Oh I Really Don't Care
Offline2ReputationRep: Follow
 10
 10122010 00:57
(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)
Or;
If x was false x and y would be false. But x and y is true. Hence x and y implies x. 
 Follow
 11
 10122010 01:36
(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)
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.
Reply
Submit reply
Related discussions:
 A Summer of Maths (ASoM) 2016
 Warwick Maths Chat
 MAT Prep Thread 2017 [2nd November 2017]
 faster than speed of light?
 Learning, Leisure and Lemur's Grade Growing Gateway to ...
 Will the real TeeEm please stand up!
 STEP Prep Thread 2014
 Year 12 Maths Help Thread
 STEP Prep Thread 2015
 Edexcel A2 C3 Mathematics 12th June 2015
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:
 SherlockHolmes
 Notnek
 charco
 Mr M
 TSR Moderator
 Nirgilis
 usycool1
 Changing Skies
 James A
 rayquaza17
 RDKGames
 randdom
 davros
 Gingerbread101
 Kvothe the Arcane
 The Financier
 The Empire Odyssey
 Protostar
 TheConfusedMedic
 nisha.sri
 Reality Check
 claireestelle
 Doonesbury
 furryface12
 Amefish
 harryleavey
 Lemur14
 brainzistheword
 Rexar
 Sonechka
 LeCroissant
 EstelOfTheEyrie
 CoffeeAndPolitics
 an_atheist
 Leviathan1741
 Moltenmo
Updated: December 10, 2010
Share this discussion:
Tweet