Error in a bogus proof showing equivalence of Cartesian Product and Union of sets of pairs

77 Views Asked by At

This question is related to another answered question, but I am struggling to relate the two (as a self-learner, I have no other avenues to get some feedback).

The problem which I am trying is the one shown in the below screenshot. The red marked lines are where I think there could be a problem.

enter image description here

  • On the first red mark, I am wondering whether distributivity of OR over AND is missing something.

  • If there is no problem in that line (the linked answer for the related problem had assumed that line to be correct), then the error is in the last line. I suppose the reasoning $x \in (A \cup B) \space and \space y \in (C \cup D) \iff (x,y) \in L $ cannot be taken to conclude that the two sets $L$ and $R$ are equal.

  • But if my above reasoning is correct, how to fix the proof to show that $R \subseteq L$ ? Would a simple statement that $ (x,y) \in L \implies R \subseteq L$ enough?

1

There are 1 best solutions below

1
On BEST ANSWER

From

$x \in A$ or $x \in B$ and $y \in C$ or $y \in D$

you cannot reach the conclusion

$(x \in A$ and $y \in C)$ or else $(x \in B$ and $y \in D)$

so

$(x \in A$ and $y \in C)$ or else $(x \in B$ and $y \in D) \implies$ $x \in A$ or $x \in B$ and $y \in C$ or $y \in D$

but not the other way around, which explains both why the proof is bogus (the statements are not an joined by an iff) and why $R \subseteq L$