Cartesian Product and Inclusion - Looking for a Proof

[Kolmin]

Homework Statement

Prove that

$A$$\times$$($$B$$\cap$$C$$)$$=$$($$A$$\times$$B$)$\cap$$($$A$$\times$$C$$)$

In particular what I cannot prove is

$($$A$$\times$$B$)$\cap$$($$A$$\times$$C$$)$$\subseteq$$A$$\times$$($$B$$\cap$$C$$)$

Homework Equations

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

$\exists$$a$$\in$$A$$\exists$$b$$($$b$$\in$$B$$\wedge$$p$$=$$($$a$$,$$b$$)$$)$

$\exists$$a$$\in$$A$$\exists$$b$$($$b$$\in$$C$$\wedge$$p$$=$$($$a$$,$$b$$)$$)$

all assume that this $b$ has to be the same for $B$ and $C$.

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 $a$$_{0}$) and that's the problem. In the first expression I can put $a$$_{0}$ and $b$$_{0}$, 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 $a$$_{1}$ and $b$$_{1}$. And that's the problem I guess, cause if I could put $a$$_{0}$ and $b$$_{0}$, 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!

 

[Mark44]

Homework Statement

Prove that

$A$$\times$$($$B$$\cap$$C$$)$$=$$($$A$$\times$$B$)$\cap$$($$A$$\times$$C$$)$

Presumably, A, B, and C are sets.

In particular what I cannot prove is

$($$A$$\times$$B$)$\cap$$($$A$$\times$$C$$)$$\subseteq$$A$$\times$$($$B$$\cap$$C$$)$

Homework Equations

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

$\exists$$a$$\in$$A$$\exists$$b$$($$b$$\in$$B$$\wedge$$p$$=$$($$a$$,$$b$$)$$)$

$\exists$$a$$\in$$A$$\exists$$b$$($$b$$\in$$C$$\wedge$$p$$=$$($$a$$,$$b$$)$$)$

all assume that this $b$ has to be the same for $B$ and $C$.

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 $a$$_{0}$) and that's the problem. In the first expression I can put $a$$_{0}$ and $b$$_{0}$, 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 $a$$_{1}$ and $b$$_{1}$. And that's the problem I guess, cause if I could put $a$$_{0}$ and $b$$_{0}$, 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!

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.

 

[Kolmin]

First of all, thanks for your answer.

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.

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

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

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 $A$, $B$ and $C$, we have to prove

$$(A \times B) \cap (A \times C) \subseteq A \times ( B \cap C)$$
which means that

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

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

What you adviced me to do is to take a $v \in B \cap C$, 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

$$\exists a \in A \exists b \in B (p=(a,b))$$
$$\exists a \in A \exists b \in C (p=(a,b))$$
but these $b$ 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 $a_{0}$ and $b_{0}$, and in the second something else like $a_{1}$ and $b_{1}$. Indeed, $b_{0}$ is not $b_{1}$.]

I hope I clarified what my problem is.

 

[Mark44]

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.

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 $A$, $B$ and $C$, we have to prove

Why use LaTeX for A, B, and C?

$$(A \times B) \cap (A \times C) \subseteq A \times ( B \cap C)$$
which means that

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

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

What you adviced me to do is to take a $v \in B \cap C$, 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

$$\exists a \in A \exists b \in B (p=(a,b))$$
$$\exists a \in A \exists b \in C (p=(a,b))$$

but these $b$ are not really the same, as far as we don't prove it.

Right, and I would use different variables.

Let p₁ = (a, b)
Let p₂ = (a, c)

Now it should be obvious what sets the elements a, b, and c belong to.
Everything hinges on the 2nd coordinates of p₁ and p₂.
(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?

[In terms of the software, with the existential instatiation rule, you insert in the first case $a_{0}$ and $b_{0}$, and in the second something else like $a_{1}$ and $b_{1}$. Indeed, $b_{0}$ is not $b_{1}$.]

I hope I clarified what my problem is.

 

[Kolmin]

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

Why use LaTeX for A, B, and C?

I would say it's a matter of taste.

Right, and I would use different variables.

Let p₁ = (a, b)
Let p₂ = (a, c)

I completely agree on using $b$ and $c$. I used $b$ in both cases simply to emphasize my problem.

On the contrary, I don't agree on using the sub for $p$, 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 $p=(a,b)$ and $p=(a,c)$, we get $(a,b)=(a,c)$, which is $a=a$ and $b=c$.

Anyway, thanks again.

 

[Mark44]

Why use LaTeX for A, B, and C?

I would say it's a matter of taste.

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.

Let p₁ = (a, b)
Let p₂ = (a, c)

On the contrary, I don't agree on using the sub for $p$, 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 $p=(a,b)$ and $p=(a,c)$, we get $(a,b)=(a,c)$, which is $a=a$ and $b=c$.

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.

 

[SteveL27]

Why use LaTeX for A, B, and C?

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 $A$ 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 $\mathcal{A} = \{A_i\}$

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 $A \cap B$ 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.

 

[Mark44]

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 $A$ 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 $\mathcal{A} = \{A_i\}$

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 $A \cap B$ denote their intersection; an experienced reader of math would regard this as a notational error or ambiguity.

I would be very surprised if someone on this forum would give this any thought at all.

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.

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.

 

[Kolmin]

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.

I see what you mean but in this case I think it's part of the assumptions I can take.

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.

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 $a$ are equal.