1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Cartesian Product and Inclusion - Looking for a Proof

  1. Aug 24, 2012 #1
    1. The problem statement, all variables and given/known data

    Prove that

    [itex]A[/itex][itex]\times[/itex][itex]([/itex][itex]B[/itex][itex]\cap[/itex][itex]C[/itex][itex])[/itex][itex]=[/itex][itex]([/itex][itex]A[/itex][itex]\times[/itex][itex]B[/itex])[itex]\cap[/itex][itex]([/itex][itex]A[/itex][itex]\times[/itex][itex]C[/itex][itex])[/itex]

    In particular what I cannot prove is

    [itex]([/itex][itex]A[/itex][itex]\times[/itex][itex]B[/itex])[itex]\cap[/itex][itex]([/itex][itex]A[/itex][itex]\times[/itex][itex]C[/itex][itex])[/itex][itex]\subseteq[/itex][itex]A[/itex][itex]\times[/itex][itex]([/itex][itex]B[/itex][itex]\cap[/itex][itex]C[/itex][itex])[/itex]


    2. Relevant equations



    3. The attempt at a solution

    In order to learn how to deal with proofs I am reading How to prove it: a structured approach, and I am using Proof Designer. This is the main problem I think...

    First of all, I tried all possible approaches, but still I cannot figure out how to deal the problem I have, which I will explain.
    I found various direct proofs of this biconditional (even on the book itself) and, given

    [itex]\exists[/itex][itex]a[/itex][itex]\in[/itex][itex]A[/itex][itex]\exists[/itex][itex]b[/itex][itex]([/itex][itex]b[/itex][itex]\in[/itex][itex]B[/itex][itex]\wedge[/itex][itex]p[/itex][itex]=[/itex][itex]([/itex][itex]a[/itex][itex],[/itex][itex]b[/itex][itex])[/itex][itex])[/itex]

    [itex]\exists[/itex][itex]a[/itex][itex]\in[/itex][itex]A[/itex][itex]\exists[/itex][itex]b[/itex][itex]([/itex][itex]b[/itex][itex]\in[/itex][itex]C[/itex][itex]\wedge[/itex][itex]p[/itex][itex]=[/itex][itex]([/itex][itex]a[/itex][itex],[/itex][itex]b[/itex][itex])[/itex][itex])[/itex]

    all assume that this [itex]b[/itex] has to be the same for [itex]B[/itex] and [itex]C[/itex].

    Indeed, if this is the case, the proof is quite straightforward, BUT...we cannot assume so - at least using Proof Designer. As a matter of fact, the software, using the existential istantiation, asks you to choose a certain name (let's say [itex]a[/itex][itex]_{0}[/itex]) and that's the problem. In the first expression I can put [itex]a[/itex][itex]_{0}[/itex] and [itex]b[/itex][itex]_{0}[/itex], but in the second one, I cannot force the program to use the same variables, because they are already being used, so I have to use something like [itex]a[/itex][itex]_{1}[/itex] and [itex]b[/itex][itex]_{1}[/itex]. And that's the problem I guess, cause if I could put [itex]a[/itex][itex]_{0}[/itex] and [itex]b[/itex][itex]_{0}[/itex], the proof would be trivial.

    Quite instructive, in order not to use the same object for two different things simply because it helps us to get a wrong proof, but I cannot figure out how to get the right proof!
     
  2. jcsd
  3. Aug 24, 2012 #2

    Mark44

    Staff: Mentor

    Presumably, A, B, and C are sets.


    I don't know anything about Proof Designer, so I can't help you with that. This should be reasonably easy to prove using nothing more than paper and pencil.

    Let x = (u, v) be an ordered pair such that u ##\in## A and v ##\in## B ##\cap## C. Show that it must be true that ##x \in (A X B) \cap (A X C)##.

    Tip: When you're doing LaTeX, it's better to use a small number of tag pairs rather than a large number of tag pairs.
     
  4. Aug 24, 2012 #3
    First of all, thanks for your answer.


    Yeah, right!
    I start to think that micromass' recent thread was related with my crazy usage of LaTex...:smile:


    Ok, I think I know what you mean and - as I wrote - I found various proofs of this problem, but maybe I didn't make explicit the kind of problem I have. The problem does exist for me, Proof Designer simply makes it evident.

    So having the sets [itex]A[/itex], [itex]B[/itex] and [itex]C[/itex], we have to prove

    [tex] (A \times B) \cap (A \times C) \subseteq A \times ( B \cap C) [/tex]
    which means that

    [tex]\forall p (p \in (A \times B) \cap (A \times C) \rightarrow p \in A \times ( B \cap C)) [/tex].
    Now, we let p be arbitrary and then we proceed with a direct proof and assume the antecedent [itex]p \in (A \times B) \cap (A \times C)[/itex], which is nothing more than [itex] p \in (A \times B) \wedge p \in (A \times C) [/itex].

    For the conjunction elimination rule we get [itex] p \in (A \times B) [/itex] and [itex] p \in (A \times C) [/itex]. And here there is my problem...

    What you adviced me to do is to take a [itex]v \in B \cap C [/itex], however given the steps I have showed you, I cannot really do it, and that's exactly what the software makes explicit. In particular the two previous expressions can be rephrased in the following way

    [tex]\exists a \in A \exists b \in B (p=(a,b)) [/tex]
    [tex]\exists a \in A \exists b \in C (p=(a,b)) [/tex]
    but these [itex]b[/itex] are not really the same, as far as we don't prove it.
    [In terms of the software, with the existential instatiation rule, you insert in the first case [itex]a_{0}[/itex] and [itex]b_{0}[/itex], and in the second something else like [itex]a_{1}[/itex] and [itex]b_{1}[/itex]. Indeed, [itex]b_{0}[/itex] is not [itex]b_{1}[/itex].]

    I hope I clarified what my problem is.
     
  5. Aug 24, 2012 #4

    Mark44

    Staff: Mentor

    It seems to me that you are pushing symbols around, without realizing what the symbols represent. It might be helpful to draw a diagram or two to help you get thinking in the right way about this stuff.


    Why use LaTeX for A, B, and C?
    Right, and I would use different variables.

    Let p1 = (a, b)
    Let p2 = (a, c)

    Now it should be obvious what sets the elements a, b, and c belong to.
    Everything hinges on the 2nd coordinates of p1 and p2.
    (A X B) ##\cap## (A X C) could be the empty set (if B has no common elements with C), which is a subset of any other set.

    On the other hand, what do you get if B and C do have a common intersection?
     
  6. Aug 25, 2012 #5
    Thanks.
    In the end I found the proof. The problem is that, when I use the software, I want to find a proof that works there (it's a sort of competition between me and the machine).

    I would say it's a matter of taste.

    I completely agree on using [itex]b[/itex] and [itex]c[/itex]. I used [itex]b[/itex] in both cases simply to emphasize my problem.

    On the contrary, I don't agree on using the sub for [itex]p[/itex], cause I think it could be misleading. Indeed, as far as I found out, the final step that I couldn't see is that, given [itex]p=(a,b)[/itex] and [itex]p=(a,c)[/itex], we get [itex](a,b)=(a,c)[/itex], which is [itex]a=a[/itex] and [itex]b=c[/itex].

    Anyway, thanks again.
     
  7. Aug 26, 2012 #6

    Mark44

    Staff: Mentor

    I try to avoid the use of LaTeX unless it is necessary. I page with plain text loads pretty quickly, but a page with lots and lots of LaTeX has to be interpreted by the browser, which takes it longer to load, at least in my browser. With that in mind, it seems silly to me to write ##A## (in LaTeX) instead of just plain A.
    It's misleading to write p = (a, b) and p = (a, c). When you do this you are implying that b = c. You should not assume that an ordered pair (a, b) is the same ordered pair as (a, c). That's why I used subscripts on p.
     
  8. Aug 26, 2012 #7
    I have the same problem. If I'm posting and I say, Let A and B be sets ... then later I write some LaTeX expression involving A and B, it annoys me that A and B appear different when I don't LaTeX them. So I often enclose standalone letters in tags because I want the variables to look the same.

    After all, when reading math, one does not necessarily assume that A and [itex]A[/itex] represent the same object. It's commonplace to use a fancy font upper case letter to stand for a family of objects denoted by a plain-font version of the same letter. For example:

    Let [itex]\mathcal{A} = \{A_i\}[/itex]

    The different fonts applied to the two instances of the letter 'A' signal the reader that these are two distinct variables.

    So if I say: Let A and B be sets, and let [itex]A \cap B[/itex] denote their intersection; an experienced reader of math would regard this as a notational error or ambiguity.

    One of the reasons I participate here is to learn LaTeX, and I'd appreciate guidance on this issue. I've always assumed that you should mark up every occurrence of a variable the same way if you are implying the same meaning.
     
    Last edited: Aug 26, 2012
  9. Aug 27, 2012 #8

    Mark44

    Staff: Mentor

    I would be very surprised if someone on this forum would give this any thought at all.
    My objection still stands. There is a cost to the use of LaTeX. Some pages with lot of LaTeX (including copied passages) take a very long time to load. Speaking for myself, if it becomes too much of an effort to read what someone has written, I start to think that maybe my time could be better spent elsewhere.

    Don't get me wrong. I'm not saying that you (or the OP) shouldn't use LaTeX. But I am saying to use it judiciously.
     
  10. Aug 30, 2012 #9
    I see what you mean but in this case I think it's part of the assumptions I can take.

    If I use the subscripts, then I must assume something different, that I cannot really do (at least on Proof Designer), which is that both [itex]a[/itex] are equal.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Cartesian Product and Inclusion - Looking for a Proof
  1. Vectors product proof (Replies: 3)

Loading...