Sets Proofs and Disproofs PDF

## 6.3 Sets: Proofs and Disproofs All of our proof techniques can be used with statements involving sets. ### Example **Prove ∀A, B ⊆ U, A ∪ B ⊆ A ∩ B ⇒ A = B** **Proof:** Let A, B ⊆ U s.t. A ∪ B ⊆ A ∩ B. Let x ∈ A. x ∈ A ∪ B (generalization) x ∈ A ∩ B (by assumption) x ∈ B (specification) So B...

## 6.3 Sets: Proofs and Disproofs All of our proof techniques can be used with statements involving sets. ### Example **Prove ∀A, B ⊆ U, A ∪ B ⊆ A ∩ B ⇒ A = B** **Proof:** Let A, B ⊆ U s.t. A ∪ B ⊆ A ∩ B. Let x ∈ A. x ∈ A ∪ B (generalization) x ∈ A ∩ B (by assumption) x ∈ B (specification) So B ⊆ A x ∈ A (specification) So A ⊆ B ∴ A = B **We can use truth tables on conditional statements** **Proof:** Let A, B ⊆ U s.t. A ∪ B ⊆ A ∩ B: | A | B | A ∪ B | A ∩ B | A ∪ B ⊆ A ∩ B | |---|---|---|---|---| | T | T | T | T | T | | T | F | T | F | F | | F | T | T | F | F | | F | F | F | F | T | I know A ∪ B ⊆ A ∩ B must be true, ignore rows when it's false ∴ ∀A, B ⊆ U, A ∪ B ⊆ A ∩ B ⇒ A = B. **We can still disprove statements.** The major difference is a counterexample involving sets can be a picture. ### Example **Disprove ∀A, B, C ⊆ U, A ∩ C ⊆ B ∩ C ∧ A ∪ C ⊆ B ∪ C ⇒ A = B.** ![Image description: A Venn diagram showing three circles labeled A, B, and C. Circle A and Circle B intersect, but circle A does not intersect circle C. Circle C is entirely contained within Circle B. The intersection of Circle A and Circle C is empty. The intersection of Circle B and Circle C is the entirety of Circle C.] When considering counterexamples, consider the extremes like U or Ø. **Group work:** Disprove ∀A, B, C ⊆ U, B ∩ C ⊆ A ∧ (A - B) ∩ (A - C) = Ø ![Image description: A Venn diagram showing three circles labeled A, B, and C. Circle A is the largest, and contains the entirety of Circle B and Circle C. There is no intersection between the three circles. The intersection of Circle A and Circle B is the entirety of Circle B. The intersection of Circle A and Circle C is the entirety of Circle C. The intersection of Circle B and Circle C is empty.] ## Need to build intuition on sets so we know if it's worth our time proving or looking for counterexamples. ### Definition Given A, B ⊆ U, the **symmetric difference** of A and B is: A Δ B = (A - B) ∪ (B - A) ### Example Let A = {1, 2, 3}, B = {2, 3, 4}. Find A Δ B. A Δ B = (A - B) ∪ (B - A) = {1, 2, 3} - {2, 3, 4} ∪ {2, 3, 4} - {1, 2, 3} = {1} ∪ {4} = {1, 4} Notice A Δ B ≡ A ⊕ B, the exclusive or. ### Group work Prove or disprove A Δ B ⊆ A ∪ B. **Proof:** Let A, B ⊆ U. A Δ B should be a subset of the inclusive or, so prove it. Statements who conditions can be proven via truth tables: | A | B | A Δ B | A ∪ B | A Δ B ⊆ A ∪ B | |---|---|---|---|---| | T | T | F | T | T | | T | F | T | T | T | | F | T | T | T | T | | F | F | F | F | T | ∴ A Δ B ⊆ A ∪ B. ### Example Prove or disprove that ∀A, B ⊆ U, P(A) ∩ P(B) = P(A ∪ B) **Proof:** Let x ∈ P(A) ∩ P(B). You can't assume the result, so start with the assumption P(A) ∩ P(B) So x ∈ P(A) (specification) x ⊆ A ∪ B So x ∈ P(A ∪ B) ∴ P(A) ∩ P(B) = P(A ∪ B)