Why is this sequence of equalities wrong?

Question

If $A, B, C$ and $D$ are sets, then $(A\times B)\cup(C\times D) = (A\cup C)\times(B\cup D)$. I managed to prove this wrong statement by using a sequence of equalities:

$$(A\times B)\cup(C\times D)\ .$$

$a,b$ element of $A\times B$ or $a,b$ element of $C\times D$.

$a$ element of $A$ and $b$ element of $B$ or $a$ element of $C$ and $b$ element of $D$.

(and now I rearranged which I suppose is wrong when dealing with ordered pairs of a cartesian product.)

$a$ element of $A$ or $a$ element of $C$ and $b$ element of $B$ or $b$ element of $D$.

$a$ element of $A\cup C$ and $b$ element of $B\cup D$.

$$(A\cup C)\times(B\cup D)$$

I know that this is wrong I would just like to know how much of it is wrong.

Answer 1

You are claiming that $$(R\wedge S)\vee (T\wedge V) \tag{1}$$ is the same as $$(R\vee T)\wedge (S\vee V).\tag{2}$$ This happens precisely where you guessed, where you "rearrange". (Here, $R$ stands for $a\in A$; $S$ stands for $b\in B$, $T$ stands for $a\in C$, and $V$ stands for $b\in D$.)

But that is just not true. It is true that (1) implies (2); but (2) does not imply (1). In other words, you have an inclusion: $(A\times B)\cup (C\times D) \subseteq (A\cup C)\times (B\cup D)$. But you don't have equality.

Note that "or" distributes over "and" and vice versa. So (1) can be explicitly rewritten as $$(R\vee T)\wedge (R\vee V)\wedge (S\vee T) \wedge (S\vee V).\tag{3}$$ Whereas (2) can be rewritten as $$(R\wedge S)\vee (R\wedge V)\vee(T\wedge S)\vee (T\wedge V).\tag{4}$$ It should be clear that they are not equivalent. For example, (4) is true if $R$ and $V$ are true and $S$ and $T$ are false; but in that case, (3) is false because the term $(S\vee T)$ would be false in that case.

Answer 2

You went from $(a \in A \wedge b \in B) \vee (a \in C \wedge b \in D)$ to $a \in A \vee a \in C \wedge b \in B \vee b \in D$ In the second you did not indicate where the parentheses should go, but you seem to assume you can commute and associate them arbitrarily. That is not true. If you have $a \in A$ and $b \in D$ the first is false and the second is true.

Answer 3

Actually what you have proven is that $(A\times B)\cup (C\cup D) \subset (A\cup C) \times (B\cup D)$.

......

If $(a,b) \in (A\times B)\cup (C\cup D)$ then $a\in A$ and $b \in B$ or $a\in C$ and $b \in D$.

So $a\in A$ or $a \in C$ so so $a \in A\cup C$. And $b \in B$ or $b \in D$. So $b\in B\cup D$.

So $(a,b) \in (A\cup C) \times (B\cup D)$.

So $(A\times B)\cup (C\cup D) \subset (A\cup C) \times (B\cup D)$. QED

======

But it is not bidirectional.

($a\in A$ and $b\in B$) OR ($a\in C$ and $b\in D$) $\implies$ ($a\in A$ or $a\in C$) and ($b \in B$ or $b\in D$).

But ($a\in A$ and $b\in B$) OR ($a\in C$ and $b\in D$) $\ne$ ($a\in A$ or $a\in C$) and ($b \in B$ or $b\in D$)

because ($a\in A$ and $b\in B$) OR ($a\in C$ and $b\in D$) $\not \Leftarrow$ ($a\in A$ or $a\in C$) and ($b \in B$ or $b\in D$).

.........

Consider $a\in A\setminus C$ and $ b\in D\setminus B$.

Then $(a,b) \in (A\cup C) \times (B\cup D)$ and it is true that $(a\in A$ or $a\in C$) [because $a \in A$]. ANd it is true that $(b\in B$ or $b \in D$) [because $b \in D$].

But it is not true that $a \in A$ and $b \in B$. [because $b \not \in B$] and it is not true that $a\in C$ and $b \in D$. [because $a \not \in C$].

And $(a,b) \not \in (A\times B)\cup (C\cup D)$ and $(A\cup C) \times (B\cup D)\not \subset (A\times B)\cup (C\cup D)$.