Study guide: Set Theory and Mathematical Logic

📋 Course Outline

1. Propositions and Logical Connectives
2. Implication and Logical Equivalence
3. Proof Methods and Induction
4. Sets and Quantified Statements
5. Subsets, Equality, and Power Sets
6. Union and Intersection
7. Complements and De Morgan Laws
8. Cartesian Products and Tuples
9. Families of Sets and Choice

📖 1. Propositions and Logical Connectives

🔑 Key Concepts & Definitions

• Statement: A sentence that has a truth value, true or false.
• Negation: True when A is false and false when A is true.
• Conjunction: True exactly when both A and B are true.
• Disjunction: True when at least one of A and B is true, and false when both are false.
• Tautology: A statement that is always true.

📝 Essential Points

• A ∧ ¬A is always false by the principle of non-contradiction, while A ∨ ¬A is always true by the principle of excluded middle.

📖 2. Implication and Logical Equivalence

🔑 Key Concepts & Definitions

• Implication: If whenever A is true, B is true; A is the hypothesis and B is the conclusion.
• Equivalence: When A ⇒ B and B ⇒ A both hold.

★ Must-know

📌 The converse of A ⇒ B is B ⇒ A, and an implication does not by itself establish its converse.

Further detail

📌 For A ⇔ B, A ⇒ B states that A is a sufficient condition for B, while B ⇒ A states that A is a necessary condition for B.

• The implication A ⇒ B is equivalent to ¬B ⇒ ¬A, called its contrapositive.

• The negation of A ⇒ B is A ∧ ¬B.

💡 Memory Hook

Implication goes one way; equivalence requires both directions.

📖 3. Proof Methods and Induction

★ Must-know

• A direct proof of A ⇒ B assumes A is true and deduces that B is true.

• For induction from k, prove P(k), then prove that P(t) implies P(t+1) for every t ≥ k.

Further detail

• A proof by contradiction assumes A is false and derives a statement that is both true and false, thereby concluding that A is true.

• A proof by contraposition proves A ⇒ B by proving the equivalent statement ¬B ⇒ ¬A.

• The second form of induction from k proves P(k), then proves that if P(s) holds for every k ≤ s ≤ t, P(t+1) holds.

• For every natural number n ≥ 1, the sum of the first n positive integers is $1+2+\cdots+n=\frac{n(n+1)}{2}$.

📖 4. Sets and Quantified Statements

🔑 Key Concepts & Definitions

• Set: A collection of objects for which membership can be determined, and which is not an element of itself.
• Empty set: Contains no elements, so x ∉ ∅ is always true and x ∈ ∅ is always false.
• Quantifiers: The existential quantifier ∃ means that at least one element satisfies a property, and the universal quantifier ∀ means that every element satisfies it.

📝 Essential Points

📌 A set is written in extension when its elements are listed, and in comprehension when its elements are specified by a property.

📌 The set {∅} is not empty because its sole element is the empty set ∅.

💡 Memory Hook

Existential claims need one witness; universal claims cover every element.

📖 5. Subsets, Equality, and Power Sets

🔑 Key Concepts & Definitions

• Subset: F is a subset of E, written F ⊆ E, if every element of F is an element of E.
• Set equality: Every element of E belongs to F and every element of F belongs to E.
• Power set: The set of all subsets of E, including ∅ and E itself.
• Proper subset: A subset that is not equal to E and is not empty.

★ Must-know

• Every set E contains the empty set as a subset, and every set is a subset of itself.

Further detail

• If A ⊆ B and B ⊆ C, then A ⊆ C.

📖 6. Union and Intersection

🔑 Key Concepts & Definitions

• Union: Contains exactly the elements that belong to E or to F.
• Intersection: Contains exactly the elements that belong to both E and F.
• Disjoint sets: Two sets are disjoint if their intersection is empty.

📝 Essential Points

• Union and intersection are commutative and associative: A ∪ B = B ∪ A, A ∩ B = B ∩ A, A ∪ (B ∪ C) = (A ∪ B) ∪ C, and A ∩ (B ∩ C) = (A ∩ B) ∩ C.

• Intersection distributes over union and union distributes over intersection: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) and A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).

💡 Memory Hook

Union accepts either set; intersection requires both.

📖 7. Complements and De Morgan Laws

🔑 Key Concepts & Definitions

• Set difference: The set of elements that belong to E and do not belong to F.
• Complement: The elements of E that do not belong to F.

★ Must-know

• For A ⊆ E, A and its complement in E are disjoint and their union is E.

• For subsets A and B of E, the complement of A ∪ B is the intersection of their complements, and the complement of A ∩ B is the union of their complements.

Further detail

• Taking the complement twice within E returns the original set: the complement of the complement of A is A.

💡 Memory Hook

A complement swaps membership and non-membership within the universe.

📖 8. Cartesian Products and Tuples

🔑 Key Concepts & Definitions

• Ordered tuple: An ordered n-tuple (a₁,…,aₙ) equals (b₁,…,bₙ) exactly when aᵢ = bᵢ for every component i.
• Cartesian product: The Cartesian product E₁ × ⋯ × Eₙ consists of all ordered n-tuples whose i-th component belongs to Eᵢ; it is empty if any factor is empty.
• Diagonal: The ordered n-tuples whose components are all equal.

📝 Essential Points

• For sets A and B, (x,y) ∈ A × B exactly when x ∈ A and y ∈ B.

💡 Memory Hook

Picture an ordered pair as a coordinate: switching its entries changes its position.

📖 9. Families of Sets and Choice

🔑 Key Concepts & Definitions

• Family of sets: A family of sets indexed by I associates a set Aᵢ with each element i of the nonempty index set I.
• Union of a family: Contains x exactly when x belongs to Aᵢ for at least one index i ∈ I.
• Intersection of a family: Contains x exactly when x belongs to Aᵢ for every index i ∈ I.
• Pairwise disjoint: A family (Aᵢ)ᵢ∈I is pairwise disjoint if Aₛ ∩ Aₜ = ∅ whenever s and t are distinct indices.

📝 Essential Points

• The axiom of choice states that for a nonempty family of nonempty pairwise disjoint sets, there exists a set E whose intersection with each family member is a singleton.