Answer to Question #117938 in Discrete Mathematics for inv

Question

Formulate corresponding proof principles to prove the following properties about defined sets

1. A=B⇔A⊆B and B ⊆ A
2. De Morgan’s Law by mathematical induction
3. Laws for three non-empty finite sets A, B, and C

Answer 1

1. Suppose we want to show A = B. If we show A ⊆ B, then every element of A is also in B, but there is still a possibility that B could have some elements that are not in A, so we can’t conclude A = B. But if in addition we also show B ⊆ A, then B can’t contain anything that is not in A, so A = B

2. Prove DeMorgan’s Law #1 Complement of the Union Equals the Intersection of the Complements

Let P = (A U B)' and Q = A' ∩ B' Let x be an arbitrary element of P then x ∈ P ⇒ x ∈ (A U B)' ⇒ x ∉ (A U B) ⇒ x ∉ A and x ∉ B ⇒ x ∈ A' and x ∈ B' ⇒ x ∈ A' ∩ B' ⇒ x ∈ Q

Prove DeMorgan’s Law #2 Complement of the Intersection Equals the Union of the Complements Let P = (A ∩ B)' and Q = A' U B' Let x be an arbitrary element of P then x ∈ P ⇒ x ∈ (A ∩ B)' ⇒ x ∉ (A ∩ B) ⇒ x ∉ A or x ∉ B ⇒ x ∈ A' or x ∈ B' ⇒ x ∈ A' U B' ⇒ x ∈ Q 

3. Using the Indirect Method

$Let A , B , C be sets. If A ⊆ B and B ∩ C = ∅ , then A ∩ C = ∅$

If we assume the conclusion is false and we obtain a contradiction --- then the theorem must be true.

$Assume A ⊆ B and B ∩ C = ∅ , and A ∩ C ≠ ∅ .$ To prove that this cannot occur, let x∈A∩C.

$x ∈ A ∩ C ⇒ x ∈ A and x ∈ C ⇒ x ∈ B and x ∈ C ⇒ x ∈ B ∩ C$

But this contradicts the second premise. Hence, the theorem is proven.