proof involving subests

Printable View

Oct 18th 2011, 04:03 PM
Jskid

proof involving subests

Prove or give a counter example. $A \subseteq C, B \subseteq D \to A \times B \subseteq C \times D$
I said
True.
let $x \in A$ then $x \in C$
let $y \in A$ then $y \in C$
$(x,y) \in C \times D$

is that enough of a proof?
Oct 18th 2011, 04:18 PM
Plato

Re: proof involving subests

Quote:

Originally Posted by Jskid

Prove or give a counter example. $A \subseteq C, B \subseteq D \to A \times B \subseteq C \times D$
I said
True.
let $x \in A$ then $x \in C$
let $y \in A$ then $y \in C$
$(x,y) \in C \times D$
is that enough of a proof?

You need to start with: suppose that $(x,y)\in A\times B$ .
then $x\in A~\&~y\in B$ .
Now what?
Oct 18th 2011, 07:03 PM
Jskid

Re: proof involving subests

Suppose it is an if and only if statment. Then I need to prove it forwards (which I did) and backwards. It really confuses me this direction thing. How would the backwards proof look like?
Wouldn't it be the same
Suppose $(x,y) \in A \times B$ ...
Oct 18th 2011, 09:15 PM
Deveno

Re: proof involving subests

the forward direction has 3 premises:
A ⊆ C, B ⊆ D, and (x,y) ∈ AxB

from which you derive (x,y) ∈ CxD showing the set containment AxB ⊆ CxD.

the reverse implication (backwards) also has 3 premises:

AxB ⊆ CxD, x ∈ A, y ∈ B

from which you derive the 2 conclusions x ∈ C, y ∈ D, showing the containments A ⊆ C, B ⊆ D.

do you see the difference?
Oct 18th 2011, 11:14 PM
issacnewton

Re: proof involving subests

Ok,

I have a related advice here. When the problem says to check the following statement , if its true then prove it. If its false give counterexample. In these kinds of problems, its difficult to figure whats the situation. The best approach which I have found is start proving the given statement. If its true, then you will prove it somehow. If its not true, then you will get stuck at some point in the proof. Its this place where you will get hints to come up with counterexample. I think this is the best approach when the problem asks for counterexample to some given statement.