STEP-BY-STEP LESSON · §6.3
Disproofs and Algebraic Proofs
Choose counterexamples for false laws and justified transformations for true ones.
Before you begin
Set Theory: Definitions and the Element Method of Proof
The statement x∈A concerns one object. A⊆B says that every element of A belongs to B.
A⊆B ⇔ ∀x(x∈A ⇒ x∈B)
X=Y means X⊆Y and Y⊆X. One inclusion still allows extra elements in the second set.
X=Y ⇔ (X⊆Y ∧ Y⊆X)
Properties of Sets
Fix an arbitrary x in a common universe U. Write p for x∈A, q for x∈B and r for x∈C. Set operations become logical operations on these three statements.
∩ ↔ ∧; ∪ ↔ ∨; complement ↔ ¬
An element is outside A∪B exactly when it is outside A and outside B. Likewise it is outside A∩B exactly when it is outside at least one of A,B.
(A∪B)ᶜ=Aᶜ∩Bᶜ; (A∩B)ᶜ=Aᶜ∪Bᶜ
Direct Proof and Counterexample I: Introduction
Integer n is even iff there is an integer k with n=2k. Evenness gives this representation, and the representation gives evenness.
n even ↔ ∃k∈ℤ: n=2k
For “every odd integer has an odd square”, testing 3,5,7 suggests a pattern but leaves infinitely many cases. Write an arbitrary odd integer as 2k+1 with integer k; no special value is assumed.
n=2k+1; k∈ℤ
Symbols
- A∖B
- elements of A that are not in B
- U
- fixed universe containing all sets’ elements under discussion
- Aᶜ
- complement U∖A within the fixed universe U
Definitions and notation for this topic
Universe and complement laws
Aᶜ=U∖A; (A∪B)ᶜ=Aᶜ∩Bᶜ; (A∩B)ᶜ=Aᶜ∪Bᶜ
Fix a universe U and subsets A,B⊆U. Complement means outside the set but inside U; both De Morgan identities use this same universe.
An element is outside the union exactly when it is outside both sets. Related laws are A∪Aᶜ=U, A∩Aᶜ=∅, and (Aᶜ)ᶜ=A.
Separate glossary example
If U={1,2,3,4}, A={1,2}, B={2,3}, then (A∪B)ᶜ={4}=Aᶜ∩Bᶜ.
Distributive and difference laws
A∩(B∪C)=(A∩B)∪(A∩C); A∖B=A∩Bᶜ
For A,B,C⊆U, set identities permit replacing a set expression by an equal one. The dual distributive law swaps ∩ and ∪ throughout.
Each equals sign needs a valid law. Alternatively, fix an arbitrary x∈U and show that membership in the left and right sides is equivalent.
Separate glossary example
(A∩B)∪(A∩Bᶜ)=A∩(B∪Bᶜ)=A∩U=A.
Simplify
Rewrite an expression in a simpler equivalent form, respecting its domain.
Distribute A∩ over the union and use B∪Bᶜ=U. The rewritten expression has the same value under the stated universe; this is not solving for A.
Separate glossary example
Simplify (A∩B)∪(A∩Bᶜ), with A,B⊆U: it equals A.
2x+3x=5x
Step by step
Step 1 / 6
Check the operation’s direction
Difference keeps elements of the first set and removes those in the second. Swapping the arguments changes the meaning.
A∖B=A∩Bᶜ
The complement uses the common universe U.
Worked example
Is A∖B=B∖A true for all sets?
- Take A={1,2}, B={2}. Removing 2 from A leaves A∖B={1}.
- For B∖A, the only element 2 is removed, yielding ∅.
- Since {1}≠∅, the universal law is false. Equality may still hold for other choices of A,B.
Optional self-check
Why is (A∖B)∩B empty?
Show answer
An element would have to be both outside B and inside B, which is impossible.