STEP-BY-STEP LESSON · §6.4
Boolean Algebras, Russell’s Paradox, and the Halting Problem
See the shared structure of logic and sets and the role of contradiction in limitations.
Before you begin
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ᶜ
Indirect Argument: Contradiction and Contraposition
To prove S, temporarily assume ¬S and derive incompatible statements. The assumption ¬S is then rejected.
¬S ⇒ contradiction
To prove P→Q, prove equivalent ¬Q→¬P. Start from the negated conclusion and reach the negated hypothesis.
P→Q ≡ ¬Q→¬P
Symbols
- 0,1
- bottom and top of a Boolean algebra
- H(P,x)
- hypothetical total halting decider for program P on input x
- D(P)
- program that reverses H’s prediction about P running on its own description
Definitions and notation for this topic
Zero and one in a Boolean algebra
x∧0=0; x∨1=1; x∧xᶜ=0; x∨xᶜ=1
In a declared Boolean algebra, 0 and 1 name its least and greatest elements, and ∧,∨,complement satisfy the Boolean laws. Their concrete meanings depend on the model.
These are algebraic roles, not a claim that every set is a number. In propositional logic the analogous roles are false, true, AND, OR and NOT.
Separate glossary example
For subsets of a fixed U, the elements are sets: 0=∅, 1=U, meet is ∩, join is ∪, and complement is taken in U.
Step by step
Step 1 / 9
Identify the Boolean operations
A Boolean algebra has two binary operations, a complement operation, and distinguished elements 0 and 1. For subsets of a fixed universe U these are ∩, ∪, complement, ∅ and U. For truth values they are AND, OR, NOT, false and true.
(∩,∪,ᶜ,∅,U) ↔ (∧,∨,¬,F,T)
The same laws can describe different kinds of objects; these operations are not ordinary numerical addition and multiplication.
Worked example
Explain A∪(A∩B)=A using membership.
- If x∈A∪(A∩B), then x∈A or x is in both A and B. Either way x∈A.
- If x∈A, it belongs to the union of A with any other set.
- Both inclusions hold. This is absorption, matching p∨(p∧q) iff p.
Optional self-check
What corresponds to ∅ in a truth table: true or false?
Show answer
False: no element satisfies membership in the empty set.