# Proof By Contradiction

1. Dec 7, 2008

### kathrynag

1. The problem statement, all variables and given/known data
I just need to decide how to show this by contradiction.
If either A or B is the empty set then AxB=$$\oslash$$.

2. Relevant equations

3. The attempt at a solution
Here is how I started:
Assume either A or B is the empty set and AxB$$\neq$$$$\oslash$$

2. Dec 7, 2008

Reasonable start. What would $$A \times B \ne \emptyset$$ mean?

3. Dec 7, 2008

### kathrynag

Is that the correct way to do a proof by contradiciton?
AxB is defined as the set consisting of all ordered pairs (x,y) in which x is an element of A and y is an element of B. So, x and y exist?

4. Dec 7, 2008

Close: if you assume $$A \times B \ne \emptyset$$, there must be at least
one element $$(a,b) \in A \times B$$. If you think about the definition of cartesian products, this will lead to a contradiction - about what? (Hint: what did you assume about $$A \text{ and } B$$?)

5. Dec 7, 2008

### kathrynag

Ok here's my idea for the proof.
Let A = null set and B be arbitrary. Then AxB= null set because of the definition of AxB. But there is no x which is an element of A. Therefore AxB=null set. Thus, contradiciton.

6. Dec 7, 2008

No - you can't assume $$A \times B = \emptyset$$ and try to proceed with a proof by contradiction.

Assume $$A= \emptyset$$ ($$B$$ may or may not be empty: that is unimiportant).

If $$A \times B \ne \emptyset$$, then (by definition of the Cartesian Product and non-empty set)
you can find an element of the product, say $$(a,b) \in A \times B$$.

This means $$b \in B$$. From where do you get the object $$a$$?
Answering the second question gives the contradiction.

7. Dec 7, 2008

### kathrynag

a is an element of A.
Oh, but then that mean A is nonempt and this a contradicition?

8. Dec 7, 2008

- yup - it contradicts $$A = \emptyset$$