How to show that the complement of Cartesian product of two non-empty sets is not the same as the Ca

Ellie Benjamin

Ellie Benjamin

Answered question

2022-07-10

How to show that the complement of Cartesian product of two non-empty sets is not the same as the Cartesian product of their complements?
( A × B ) C = ( A C × B C ) ( A C × B ) ( A × B C )
I wanted to do it like this:
A × B = { ( a , b ) A × B | a A b B }
Taking complement, A × B ¯ = { ( a , b ) A × B | a A b B }
Because ( a , b ) A × B prevents me from going anywhere, I chose to do:
Let A × B X × Y
Then, A × B = { ( a , b ) X × Y | a A b B } and A × B ¯ = { ( a , b ) X × Y | a A b B }
But I'm unsure about the correctness of what I did from here.
A × B ¯ = { ( a , b ) X × Y | ( a A b B ) ( a A b B ) ( a A b B ) }
Therefore, A × B ¯ = { ( a , b ) X × Y | ( a A b B ) } { ( a , b ) X × Y | ( a A b B ) } { ( a , b ) X × Y | ( a A b B ) } which gives
We know A × B A × B.
Hence, A × B ¯ = ( A ¯ × B ¯ ) ( A ¯ × B ) ( A × B ¯ ).
"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

Answer & Explanation

talhekh

talhekh

Beginner2022-07-11Added 15 answers

Step 1
Regarding the query in the title of the Q: Suppose x A and y A with x y .. Let B = C = { x } .. Then B × C = { ( x , x ) } ..
Step 2
Now the complement X = ( A × A ) ( B × C ) is not the Cartesian product D × E for any D, E.
Because if X = D × E then ( x , y ) X x D and also ( y , x ) X x E .. Hence ( x D x E ) ,, so ( x , x ) D × E = X ,, which is absurd.
Callum Dudley

Callum Dudley

Beginner2022-07-12Added 4 answers

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 A b 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.
Step 1
1. Assume a 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 A ( b B b B ), this is just ϕ , which is equivalent to ϕ
4. Distribute to get ( a A b B ) ( a A b B )
5. Finally, disjoin the last disjunct and convert into the desired form
Step 2
- Assume b 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 A b B is false then a A b 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

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Discrete math

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?