# proof for cartesian product of two sets

6 replies to this topic

### #1anubis

Senior Member

• Members
• 2225 posts

Posted 27 October 2003 - 01:13 PM

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
If Prolog is the answer, what is the question ?

### #2Dia

DevMaster Staff

• 1121 posts

Posted 27 October 2003 - 04:44 PM

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.

### #3anubis

Senior Member

• Members
• 2225 posts

Posted 27 October 2003 - 08:01 PM

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|
If Prolog is the answer, what is the question ?

### #4farmerTom

Member

• Members
• 39 posts

Posted 30 May 2004 - 01:02 AM

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

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

### #5anubis

Senior Member

• Members
• 2225 posts

Posted 30 May 2004 - 12:18 PM

hehe, even if it would help i this was a homework from last year :D
thanks anyway
If Prolog is the answer, what is the question ?

### #6Per Vognsen

New Member

• Members
• 8 posts

Posted 06 October 2004 - 01:41 AM

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 :)

Senior Member

• Members
• 785 posts

Posted 06 October 2004 - 02:23 AM

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

#### 1 user(s) are reading this topic

0 members, 1 guests, 0 anonymous users