1. Limited time only! Sign up for a free 30min personal 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!

Proving the cartesian product.

  1. Oct 8, 2011 #1
    hello all,

    i'm trying to prove the [STRIKE]cartesian product[/STRIKE] cardinality property of the cartesian product.

    on a first attempt i used this:

    and on a second attempt this:

    this is the first of many small exercises i'm doing for building a strong theoretical computer science background.

    i would like your criticism and comments. i don't have much math backgrounds.

    Last edited: Oct 8, 2011
  2. jcsd
  3. Oct 8, 2011 #2
    Hi i am a math student , in the first proof i think you started well but when you take lBl+1=k+1 it same as lBl=k , i think you have to prove for lBl=k+1, and i don't know what the successor function can you please explain ?
    The second proof is very simple
  4. Oct 8, 2011 #3
    It's helpful to your readers to say what you are trying to prove about it. Are you trying to prove that the Cartesian product exists? That for finite sets it has a particular cardinality? That it has the universal property that characterizes it in category theory?

    You have to say what you are trying to prove. In fact one of the key "tricks" for doing proofs is to state clearly and precisely exactly what it is you're trying to prove; and exactly what you have to show in order to prove it.

    When you state the problem in very clear and explicit terms, the solution often falls out directly.

    So: What are you trying to prove? And what do you have to show in order to prove it?
  5. Oct 8, 2011 #4

    it's the equality that i'm trying to prove. that |A X B| = |A| * |B|.


    i also don't know much about the successor function. it's just one of the requirement of http://en.wikipedia.org/wiki/Peano_axioms" [Broken]

    i will look more into that function and retry the proof.
    Last edited by a moderator: May 5, 2017
  6. Oct 8, 2011 #5
    Just to note, you're not proving the cartesian product, but the properties of cartesian products. Otherwise, you're claiming to prove a definition, which is logically impossible (?).
  7. Oct 11, 2011 #6
    Let's assume the property is true for lBl=k
    then we will prove for lBl=k+1
    let Bk+1={b1,b2,b3,......bk+1 }
    let Bk={b1,b2,...bk} then Bk+1=BkU{bk+1} and lBkl=k
    now using the property Ax(BUC)=(AxB)U(AxC)
    we have lAxBk+1l =l(AxBk)U(Ax{bk+1})l
    =lAxBkl+lAx{bk+1}l since bk+1 is not in Bk
    then the proof follows from the fact that its true for k , am i right ?
  8. Oct 11, 2011 #7
    Tell me whether the above proof sounds good
    Last edited by a moderator: May 5, 2017
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook