Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Proof By Contradiction

  1. Dec 7, 2008 #1
    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=[tex]\oslash[/tex].



    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[tex]\neq[/tex][tex]\oslash[/tex]
     
  2. jcsd
  3. Dec 7, 2008 #2

    statdad

    User Avatar
    Homework Helper

    Reasonable start. What would [tex] A \times B \ne \emptyset [/tex] mean?
     
  4. Dec 7, 2008 #3
    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?
     
  5. Dec 7, 2008 #4

    statdad

    User Avatar
    Homework Helper

    Close: if you assume [tex] A \times B \ne \emptyset[/tex], there must be at least
    one element [tex] (a,b) \in A \times B [/tex]. If you think about the definition of cartesian products, this will lead to a contradiction - about what? (Hint: what did you assume about [tex] A \text{ and } B [/tex]?)
     
  6. Dec 7, 2008 #5
    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.
     
  7. Dec 7, 2008 #6

    statdad

    User Avatar
    Homework Helper

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

    Assume [tex] A= \emptyset [/tex] ([tex] B [/tex] may or may not be empty: that is unimiportant).

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

    This means [tex] b \in B [/tex]. From where do you get the object [tex] a [/tex]?
    Answering the second question gives the contradiction.
     
  8. Dec 7, 2008 #7
    a is an element of A.
    Oh, but then that mean A is nonempt and this a contradicition?
     
  9. Dec 7, 2008 #8

    statdad

    User Avatar
    Homework Helper

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

    :smile: - yup - it contradicts [tex] A = \emptyset [/tex]
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook