6 replies to this topic

[anubis]

i can't get my head around this...
the cartesian product of two sets is defined as RxS = { (x,y) | x e R, y e S }
i now need to proof that :

|RxS| = |R| * |S|

obviously this is true. but i am clueless as to how a proper way to express it in a mathematical proof would look like. if anybody could help me i'd be very glad. thanks guys.

PS : | | means number of elements in the set

[Dia]

How about this:

Let R = A1
S = A2

For each (a1, a2) e (A1 * A2), for which P1(a1), P2(a1, a2), we have:

{ xi e Ai | Pi(a1, a2) } = {xi e Ai | xi e Ai} = Ai
where i=1,2

therefore mi = | {xi e Ai | Pi(a1, a2)} |
for i=1,2 (mi denotes size of set Ai)

Therefore:

C = { (a1, a2) e (Product,j=1 to 2) (Aj | P1(a1), P2(a1, a2) }
= { (a1, a2) e (Product,j=1 to 2) (Aj | a1 e A1, a2 e A2) }
= A1 * A2


Hope that makes sense. P() means power set.

[anubis]

my tutor told me that the proof is the easiest on the homework paper.
so i figured that they simply want to hear that i understood that, because the cartesian product is the combination of all elements xi in R with all elements yi in S, the number of elements must equal to |R| * |S|

[farmerTom]

This may not help, but it at least gave me a slight understanding of your discussion.


http://www.wordiq.co...rtesian_product

[anubis]

hehe, even if it would help i this was a homework from last year :D
thanks anyway

[Per Vognsen]

anubis said:

hehe, even if it would help i this was a homework from last year :D
thanks anyway

Resurrecting threads is fun so here's another way of proving it. Proving that |AxB| = |A| |B| means proving that a bijection exists between the elements of AxB and the set of integers S = {0, 1, ..., |A| |B| - 1}. We will do this by constructing an explicit bijection.

Let A = {A_0, A_1, ..., A_(m-1)} and B = (B_0, B_1, ..., B_(n-1)} where m = |A| and n = |B|. Define a function f : AxB -> S by f(A_i, B_j) = i + m j, where i = 0, 1, ..., m-1 and j = 0, 1, ..., n-1. I claim that this is the desired bijection. We have to prove injectivity and surjectivity.

Injectivity: Suppose that i + m j = k + m l. We wish to prove i = k and j = l. Dividing both sides by m, we find that i = k (mod m). Since 0 <= i, k < m it follows that i = k. Substitituting this back into the equation, we get m j = m l. Cancelling m, we find that j = l.

Surjectivity: Let p be an integer in S, i.e. p = 0, 1, ..., m n - 1. We have to prove that there exists i = 0, 1, ..., m-1 and j = 0, 1, ..., n-1 such that p = i + m j. This again follows from the division algorithm: i is the remainder and j the quotient when p is divided by m.

This kind of approach might seem overkill but it is very good practice to prepare for "bijection proofs" in combinatorics. Counting without constructing explicit bijections is lazy :)

[NomadRock]

Welcome to the board Per. As always, your handle on abstract maths is amazing.