4
$\begingroup$

Explain why $(A × B) × (C × D)$ and $A × (B × C) × D$ are not the same.

My thinking is that you need to use the cardinality in some way to show that they have different cardinality, thus the sets are not the same. If this is correct, how could I solve it this way?

$\endgroup$
7
  • 8
    $\begingroup$ You'll have a hard time showing that, because the sets are isomorphic - there's a one-to-one mapping from either one to the other. (In particular, this implies that they have the same cardinality - in the case where all four sets are finite, for instance, this cardinality is $abcd$, where $a=|A|$, etc.) You'll do better exhibiting an element of one set and explaining why it's not an element of the other. (Also, the statement isn't strictly true; you need some nonemptiness, because the two are the same when $A=B=C=D=\emptyset$.) $\endgroup$ – Steven Stadnicki Mar 13 '15 at 18:26
  • 1
    $\begingroup$ Try an explicit example. What if $A=B=C=D=\{0\}$? $\endgroup$ – Akiva Weinberger Mar 13 '15 at 18:30
  • 1
    $\begingroup$ @StevenStadnicki I really have no idea how to prove this statement then. $\endgroup$ – ComputerLocus Mar 13 '15 at 18:30
  • 2
    $\begingroup$ They are different, but sometimes the elements of the two are identified with each other in the natural way. $\endgroup$ – Qudit Mar 13 '15 at 18:35
  • 4
    $\begingroup$ But what is $A \times (B \times C) \times D$? Is it $(A \times (B \times C)) \times D$ or $A \times ((B \times C) \times D)$? We cannot tell. $\endgroup$ – Jeppe Stig Nielsen Mar 13 '15 at 20:55
12
$\begingroup$

an element of $(A\times B)\times(C\times D)$ is of the form $$ \Big((a,b),(c,d)\Big) $$

Because "$\times$" is a binary operation on sets, $A\times(B\times C)\times D$ doesn't make sense UNLESS you defined it as ordered triples; in which case an element is of the form $$\Big(a,(b,c),d\Big)$$

There is a one-to-one onto function from one set to the other however. Namely $$ \Big((a,b),(c,d)\Big)\mapsto \Big(a,(b,c),d\Big) $$

Recall $(a,b)$ is notation for $\{\{a\},\{a,b\}\}$.

Following Endertons' Elements of Set Theory textbook, $n$-tuples are defined as follows $$ (x,y,z)\overset{\mathrm{def}}{=} ((x,y),z) $$ $$ (x,y,z,u)\overset{\mathrm{def}}{=} ((x,y,z),u) $$ $$\vdots$$

$\endgroup$
2
  • 1
    $\begingroup$ I was thinking this but I didn't know the terminology. I wanted to say one was an ordered pair of ordered pairs whilst the other was some form of triple. Is there a name for n-tuples that don't have the same type of elements in? Is that worth a question on its own? $\endgroup$ – Karl Mar 13 '15 at 18:37
  • 1
    $\begingroup$ @Karl, for what it's worth, I say "ordered pair" for an element of any product $A \times B$, even if $A$ and $B$ are "the same" in some way. $\endgroup$ – Vectornaut Mar 13 '15 at 22:15
5
$\begingroup$

You wouldn't use cardinality because they have the same cardinality.

In general..

What does an element of $(A \times B) \times(C \times D)$ look like? It looks like $((a,b),(c,d))$. What does an element of $A \times (B \times C) \times D$ look like? It looks like $(a,(b,c),d)$. It actually might look a little different depending on how your book defines multiple direct products. My suggestion is using your book's definition of a tuple, determine what is the actual set $((a,b),(c,d))$ vs the actual set $(a,(b,c),d)$.

Or specifically...

You can actually construct a pretty easy counter-example with $A=B=C=D=\{\{\}\}$. $(A \times B) \times(C \times D)$ and $A \times (B \times C) \times D$ both only have one element: $((\{\},\{\}),(\{\},\{\}))$ and $(\{\},(\{\},\{\}),\{\})$ respectively. So when you show those two elements aren't equal, then you've immediately shown $(A \times B) \times(C \times D)$ is not equal to $A \times (B \times C) \times D$.

$\endgroup$
3
$\begingroup$

No, this sets are of equal cardinality.

Use the definition of cartesian product of two sets (the set of all ordered pairs), and show that these two sets contain elements of different 'types' (something like 'pairs of type (A,B)' vs 'pairs of type (pairs of type (B,C), pairs of type (A, D))').

Actually, although these sets are not strictly equal, there always exists a natural bijection between them.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.