Question

Prove: If A,B and C are non-empty sets and A X C = B X C, then A = B

Answer 1

Let A,B,C be sets such that A and B are the same size. I.e, |A| = |B| = n. Set A and set B have n elements each. Set C has m elements


so,

A = {a1,a2,a3,...,an}
B = {b1,b2,b3,...,bn}
C = {c1,c2,c3,...,cm}


Now cross set A and set C to get
A x C = {
(a1,c1), (a1,c2), (a1,c3), ..., (a1,cm),
(a2,c1), (a2,c2), (a2,c3), ..., (a2,cm),
(a3,c1), (a3,c2), (a3,c3), ..., (a3,cm),
...
...
...
(an,c1), (an,c2), (an,c3), ..., (an,cm)
}
this may be easier to see if you set up a table


cross set B and set C to get
B x C = {
(b1,c1), (b1,c2), (b1,c3), ..., (b1,cm),
(b2,c1), (b2,c2), (b2,c3), ..., (b2,cm),
(b3,c1), (b3,c2), (b3,c3), ..., (b3,cm),
...
...
...
(bn,c1), (bn,c2), (bn,c3), ..., (bn,cm)
}


if we equate A x C and B x C, then we'll find that


(ai, ci) = (bi, ci)


for every i such that 0 <= i <= m*n, where i is an integer


clearly ci = ci, so (ai, ci) = (bi, ci) is only true if and only if ai = bi for every integer i 0 <= i <= n

but that forces A = B to be true, so if A x C = B x C, then A = B