0
$\begingroup$

I am having trouble deriving the property of Cartesian product of sets as shown here: enter image description here

I wanted to do it like this:

$A \times B = \{ (a, b) \in A\times B \vert a \in A \wedge b\in B\}$

Taking complement, $\overline {A \times B} = \{ (a, b) \notin A\times B \vert a \notin A \vee b\notin B\}$

Because $(a,b) \notin A \times B$ prevents me from going anywhere, I chose to do:

Let $A \times B \subseteq X \times Y$

Then, $A \times B = \{ (a, b) \in X\times Y \vert a \in A \wedge b\in B\}$

and $\overline {A \times B} = \{ (a, b) \in X\times Y \vert a \notin A \vee b\notin B\}$

But I'm unsure about the correctness of what I did from here.

$\overline {A \times B} = \{ (a, b) \in X\times Y \vert (a \notin A \wedge b\notin B) \vee (a\notin A \wedge b\in B) \vee (a\in A \wedge b\notin B)\}$

Therefore, $\overline {A \times B} = \{ (a, b) \in X\times Y \vert (a \notin A \wedge b\notin B)\} \cup \{ (a, b) \in X\times Y \vert (a\notin A \wedge b\in B)\} \cup \{ (a, b) \in X\times Y \vert (a\in A \wedge b\notin B)\}$, which gives

We know $ A\times B \subseteq A \times B$.

Hence, $\overline {A \times B} = ( \bar A \times \bar B) \cup (\bar A \times B) \cup (A \times \bar B)$

Is my logic correct here? Any help would be much appreciated :)

Edit: "derive" instead of "prove" because I don't need to prove the equivalence per se. I'm just trying to see how the LHS can lead to the RHS. I should've been more careful about the wording

$\endgroup$

2 Answers 2

1
$\begingroup$

Regarding the query in the title of the Q: Suppose $x\in A$ and $y\in A$ with $x\ne y.$ Let $B=C=\{x\}.$ Then $B\times C=\{(x,x)\}.$

Now the complement $X=(A\times A)\setminus (B\times C)$ is not the Cartesian product $D\times E$ for $any$ $D, E.$

Because if $X=D\times E$ then $(x,y)\in X\implies x\in D$ and also $(y,x)\in X\implies x\in E.$ Hence $(x\in D \land x\in E),$ so $(x,x)\in D\times E =X,$ which is absurd.

$\endgroup$
0
$\begingroup$

To demonstrate that 2 sets equal each other we need to show they're both subsets of each other. To do that, assume one side and derive the other.

Let's start with assuming $a\notin A\lor b\notin B$

To derive a conclusion from a disjunction we need to derive said conclusion from each disjunct. This is proof by cases, or disjunction elimination.

Case 1

  1. Assume $a\notin A$
  2. The conclusion contains a conjunction, so we need to add that in. We can only do that if we don't change the meaning of the formula. This is the logic equivalent of adding 0 to an equation.
  3. $a\notin A\wedge (b\notin B\lor b\in B)$, this is just $\phi\wedge\top$, which is equivalent to $\phi$
  4. Distribute to get $(a\notin A\wedge b\notin B)\lor(a\notin A\wedge b\in B)$
  5. Finally, disjoin the last disjunct and convert into the desired form

Case 2

  • Assume $b\notin B$ and follow a similar procedure to Case 1

  • From each disjunct we've derived the same conclusion, hence we've derived the conclusion from the disjunction

The details and the other direction I'll leave to you.

Edit:

If you prefer a more semantic approach, assume 1 side is true and the other is false and derive a contradiction. Repeat for the other direction.

Example:

If $a\notin A\lor b\notin B$ is false then $a\in A\wedge b\in B$. Notice that this isn't true for any disjunct in the formula we're saying is true, hence a contradiction. Again, I'll leave you to fill in the details

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .