proof for cartesian product of two sets

F7a4a748ecf664f189bb704a660b3573
0
anubis 101 Oct 27, 2003 at 13:13

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

6 Replies

Please log in or register to post a reply.

Fdbdc4176840d77fe6a8deca457595ab
0
dk 158 Oct 27, 2003 at 16:44

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.

F7a4a748ecf664f189bb704a660b3573
0
anubis 101 Oct 27, 2003 at 20:01

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|

E813ba6ba564e1f10bc2bc5c9b757561
0
farmerTom 101 May 30, 2004 at 01:02

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

http://www.wordiq.com/definition/Cartesian_product

F7a4a748ecf664f189bb704a660b3573
0
anubis 101 May 30, 2004 at 12:18

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

Abdc56636d8d76cfb91fe792460c9699
0
Per_Vognsen 101 Oct 06, 2004 at 01:41

@anubis

hehe, even if it would help i this was a homework from last year :D
thanks anyway [snapback]8247[/snapback]

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

7543b5c50738e23b200e69fe697ea85a
0
NomadRock 101 Oct 06, 2004 at 02:23

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