Hey there! Sign in to join this conversationNew here? Join for free

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

    • Thread Starter
    Offline

    2
    ReputationRep:
    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 !
    Offline

    2
    ReputationRep:
    (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) ?
    Offline

    2
    ReputationRep:
    For (a), the approach I would take is something like:

    (a, b)\in(P\times Q)\cap(R\times S)

    \Leftrightarrow (a,b)\in(P\times Q) \land (a,b)\in(R\times S)

    then show which sets a and b each have to be in and finish off by showing that (a,b)\in(P\cap R)\times(Q\cap S). 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 (w\land x)\lor(y\land z)\Leftrightarrow (w\lor y)\land(w\lor z)\land(x\lor y)\land(x\lor z). Use that to expand out your previous statement.

    Now if x and y are statements then x\land y\Rightarrow x 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.
    Offline

    2
    ReputationRep:
    (Original post by ttoby)
    For (a), the approach I would take is something like:

    (a, b)\in(P\times Q)\cap(R\times S)

    \Leftrightarrow (a,b)\in(P\times Q) \land (a,b)\in(R\times S)

    then show which sets a and b each have to be in and finish off by showing that (a,b)\in(P\cap R)\times(Q\cap S). 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 (w\land x)\lor(y\land z)\Leftrightarrow (w\lor y)\land(w\lor z)\land(x\lor y)\land(x\lor z). Use that to expand out your previous statement.

    Now if x and y are statements then x\land y\Rightarrow x 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.
    • Thread Starter
    Offline

    2
    ReputationRep:
    (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
    Offline

    2
    ReputationRep:
    (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.
    Offline

    2
    ReputationRep:
    (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
    Offline

    2
    ReputationRep:
    (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.
    • Thread Starter
    Offline

    2
    ReputationRep:
    (Original post by ttoby)
    Then use a distributivity law of logic which says (w\land x)\lor(y\land z)\Leftrightarrow (w\lor y)\land(w\lor z)\land(x\lor y)\land(x\lor z). Use that to expand out your previous statement.

    Now if x and y are statements then x\land y\Rightarrow x 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)
    Offline

    2
    ReputationRep:
    (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.
    Offline

    2
    ReputationRep:
    (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)
    x\land y 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: x\land y\Rightarrow x but going the other way, if you know x is true then you can't then claim that x\land y is true because you don't know anything about y.
 
 
 
  • 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
    Did TEF Bronze Award affect your UCAS choices?
    Useful resources

    Make your revision easier

    Maths

    Maths Forum posting guidelines

    Not sure where to post? Read the updated guidelines here

    Equations

    How to use LaTex

    Writing equations the easy way

    Student revising

    Study habits of A* students

    Top tips from students who have already aced their exams

    Study Planner

    Create your own Study Planner

    Never miss a deadline again

    Polling station sign

    Thinking about a maths degree?

    Chat with other maths applicants

    Can you help? Study help unanswered threads

    Groups associated with this forum:

    View associated groups
  • 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

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