Proving the cartesian product.

[nvictor]

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:

19. |A X B| = |A|*|B|.
Proof by induction for finite sets.
Assume |B| = 0. Then B is the empty set and A X B = A X {} = {} by
definition. Thus on the left hand side we have |A| * 0 = 0 and on the right we
have |{}| = 0 (zero property of multiplication)

Assume these statements true |B| = k and |A X B| = |A| * |B| = |A| * k.
With Peano(1889) axiom for multiplication:
a * 0 = 0; a * S(b) = a + (a*b) with S being the successor function,
we prove that the statement remains true for |B| + 1 = k + 1.

For |B| + 1 = k + 1,
|A| * (|B| + 1) = |A| * (k + 1) = |A| * k + |A| = |A| * |B| + |A| = |A X B| + |A|
(because multiplication is distributive over addition of natural numbers)

Thus |A| * |B| + |A| = |A X B| + |A| eq. |A| * |B| = |A X B| (QED)
(by elimination)

and on a second attempt this:

20. |A X B| = |A|*|B|.
Proof using the principle of multiplication. (haffe @ #math).

By definition, A X B = all ordered pairs (a,b) with a in A and b in B.
The number of ways of choosing an element from A X B, is the number of ways of
choosing one element from A, which is |A| times the number of ways of choosing
one from B, which is |B|. Thus the number of elements in |A X B| = |A| * |B|
(QED).

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.

thanks

 

[vrmuth]

hello all,

i'm trying to prove 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.

thanks

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

 

[SteveL27]

hello all,

i'm trying to prove the cartesian product.

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?

 

[nvictor]

@SteveL27

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

@vrmuth

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"

i will look more into that function and retry the proof.

 

[Anonymous217]

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

 

[vrmuth]

Let's assume the property is true for lBl=k
then we will prove for lBl=k+1
let B_k+1={b₁,b₂,b₃,...b_k+1 }
let B_k={b₁,b₂,...b_k} then B_k+1=B_kU{b_k+1} and lB_kl=k
now using the property Ax(BUC)=(AxB)U(AxC)
we have lAxB_k+1l =l(AxB_k)U(Ax{b_k+1})l
=lAxB_kl+lAx{b_k+1}l since b_k+1 is not in B_k
then the proof follows from the fact that its true for k , am i right ?

 

[vrmuth]

@vrmuth

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"

i will look more into that function and retry the proof.

Tell me whether the above proof sounds good