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

Ellie Benjamin 2022-07-10 Answered
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
You can still ask an expert for help

Want to know more about Discrete math?

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (2)

talhekh
Answered 2022-07-11 Author has 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.
Did you like this example?
Subscribe for all access
Callum Dudley
Answered 2022-07-12 Author has 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
Did you like this example?
Subscribe for all access

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2021-08-02

Suppose that A is the set of sophomores at your school and B is the set of students taking discrete mathematics at your school. Express each of these sets in terms of A and B. 
a) the set of sophomores taking discrete mathematics in your school 
b) the set of sophomores at your school who are not taking discrete mathematics 
c) the set of students at your school who either are sophomores or are taking discrete mathematics 
Use these symbols: 

asked 2021-08-15
How many elements are in the set { 0, { { 0 } }?
asked 2021-07-28

Let A, B, and C be sets. Show that (AB)C=(AC)(BC)
image

asked 2020-11-09
Use proof by Contradiction to prove that the sum of an irrational number and a rational number is irrational.
asked 2022-07-17
Discrete Math Compositions
I am having trouble with these compositions.
T = { ( a , a ) , ( a , b ) , ( b , c ) , ( b , d ) , ( c , d ) , ( d , a ) , ( d , b ) }
U = { ( a , a ) , ( a , d ) , ( b , c ) , ( b , d ) , ( c , a ) , ( d , d ) }
I need to find T T, U T, and T U.
My problem is when I get down to, for example U T where (d,a) corresponds with both (a,a) and (a,c). This seems to happen for everyone of these problems. Is it even possible to take the composition of these?
asked 2022-07-15
Discrete math predicate problem
In this problem, we will be using binary predicates F(x, y), G(x, y), etc. to represent functions f, g : U U, etc., where U is the universe. Thus, F(x, y) holds iff y = f ( x ), G(x, y) holds iff y = g ( x ), etc.
1. Write predicate statements that expresses the following facts:
- F represents a function.
- F represents a one-to-one function.
- F represents an onto function.
- F and G represent inverse functions of one another.
- H represents the composition function f g.
2. Use binary predicates representing functions to give formal proofs (in the style of Sec 1.6 of the following statements:
- “If f and g are one-to-one functions, then so is f g.”
- “If f and g are onto functions, then so is f g.”
asked 2022-07-16
Proofs in Discrete Math
n N +, n composite p N +, p is prime and p n and p|n.
Am I supposed to prove that p n and p|n when n is composite and p is prime? Could someone fix my translation if I'm wrong?

New questions

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question