2

So, Is a cancellation possible for the Cartesian product? ex. if you have two Cartesian products that are equal to eachother, do the 2nd sets for each product equal eachother?

Lets say you have AxB=AxC for the sets A, B, and C. Does it then follow that B=C?

I think it does, because for AxB to = AxC, B and C must be identical sets. How can I prove that B=C? (I'm having trouble with all proofs for sets btw, so this may be something trivial).

I'm approaching the proof by first trying to define what AxB=AxC really means:

AxB = {(a,b) | (a∈A) and (b∈B)} AxC = {(a,c) | (a∈A) and (c∈C)}

Now, how can I prove that B=C?

user56763
  • 447

2 Answers2

5

Your intuition that the claim is true is correct. Notice however that just like for cancelation with real numbers you need some condition on $A$.

So, you can prove that if $A\ne \emptyset$ and $A\times B = A\times C$ then indeed $B=C$. However, you can also prove that without the restriction $A\ne \emptyset$ it is possible that $A\times B=A\times C$ yet $B\ne C$. To prove the former, work carefully with the definition of the cartesian product. To prove the latter, choose some explicit sets for $B$ and $C$, and figure out what $A\times B$ is when $A=\emptyset$. Good luck!

Ittay Weiss
  • 79,840
  • 7
  • 141
  • 236
  • For showing better the OP the claim fails when A is empty, could we denote A with 0 in numbers. I think, the OP gets the point so fast. +1 – Mikasa Feb 03 '13 at 05:45
  • How would I actually approach the proof? I mean, I get what I need to prove, but am not sure how I actually prove it! I always feel like I'm running in circles with this stuff... – user56763 Feb 04 '13 at 04:03
  • NM, I got it... when A != 0, the property holds. – user56763 Feb 05 '13 at 07:00
1

Hint: Use this fact that for two ordered pairs: $$(a,b)=(a,c)\Longleftrightarrow b=c, a\in A,~ b\in B,~ c\in C$$

Mikasa
  • 67,374