Set Theory and Logic: The Foundations of Mathematics and Theoretical Reasoning

Table of Contents

1. Introduction
2. What Is Set Theory?
3. Basic Set Operations
4. Subsets, Power Sets, and Cartesian Products
5. Relations and Functions
6. Types of Sets: Finite, Infinite, Countable, and Uncountable
7. Russell’s Paradox and the Need for Axioms
8. Zermelo–Fraenkel Axioms and the Axiom of Choice
9. What Is Logic?
10. Propositional Logic
11. Logical Connectives and Truth Tables
12. Predicate Logic and Quantifiers
13. Logical Inference and Deduction
14. Consistency, Completeness, and Soundness
15. Gödel’s Incompleteness Theorems
16. Applications in Mathematics, Physics, and Computing
17. Conclusion

1. Introduction

Set theory and logic provide the rigorous underpinnings of mathematics and scientific reasoning. Together, they formalize how we define collections of objects and how we construct valid arguments. These disciplines are fundamental in the foundations of mathematics, theoretical physics, computer science, and formal language theory.

2. What Is Set Theory?

A set is a well-defined collection of distinct objects, called elements. Sets are denoted by curly braces:

\[
A = \{1, 2, 3\}, \quad B = \{x \in \mathbb{R} \mid x^2 < 4\}
\]

Set theory forms the language through which modern mathematics is expressed.

3. Basic Set Operations

• Union: \( A \cup B = \{x \mid x \in A \text{ or } x \in B\} \)
• Intersection: \( A \cap B = \{x \mid x \in A \text{ and } x \in B\} \)
• Difference: \( A \setminus B = \{x \mid x \in A \text{ and } x \notin B\} \)
• Complement: \( A^c = \{x \mid x \notin A\} \)

4. Subsets, Power Sets, and Cartesian Products

• \( A \subseteq B \): every element of \( A \) is in \( B \)
• Power set: set of all subsets of \( A \), denoted \( \mathcal{P}(A) \)
• Cartesian product: \( A \times B = \{(a, b) \mid a \in A, b \in B\} \)

5. Relations and Functions

• A relation on \( A \) is a subset of \( A \times A \)
• A function \( f: A \to B \) assigns each \( a \in A \) exactly one \( b \in B \)

Functions are special relations satisfying the vertical line test.

6. Types of Sets: Finite, Infinite, Countable, and Uncountable

• Finite: contains a finite number of elements
• Infinite: not finite
• Countable: bijective to \( \mathbb{N} \)
• Uncountable: e.g., \( \mathbb{R} \), larger than countable sets

Cantor’s diagonal argument shows \( \mathbb{R} \) is uncountable.

7. Russell’s Paradox and the Need for Axioms

Consider the set \( R = \{x \mid x \notin x\} \).
Is \( R \in R \)? This paradox showed naive set theory is inconsistent.

Resolution: adopt axiomatic systems like Zermelo–Fraenkel set theory (ZF).

8. Zermelo–Fraenkel Axioms and the Axiom of Choice

ZF includes axioms for:

• Extensionality
• Pairing
• Union
• Power set
• Replacement
• Infinity

ZFC = ZF + Axiom of Choice (AC):
\[
\text{Given any collection of non-empty sets, there exists a function choosing an element from each.}
\]

9. What Is Logic?

Logic is the formal study of reasoning. It distinguishes valid arguments from invalid ones using symbols and formal rules.

10. Propositional Logic

Deals with propositions (statements that are true or false) and logical connectives:

• \( \lnot \): not
• \( \land \): and
• \( \lor \): or
• \( \rightarrow \): implies
• \( \leftrightarrow \): if and only if

11. Logical Connectives and Truth Tables

Truth tables list all possible truth values of compound propositions.

Example:
\[
p \rightarrow q \text{ is false only when } p = \text{true}, q = \text{false}
\]

12. Predicate Logic and Quantifiers

Extends propositional logic to statements with variables:

• \( \forall x \, P(x) \): for all \( x \), \( P(x) \) holds
• \( \exists x \, P(x) \): there exists an \( x \) such that \( P(x) \)

Crucial in formalizing mathematical statements and proofs.

13. Logical Inference and Deduction

Rules of inference:

• Modus ponens: if \( p \rightarrow q \) and \( p \), then \( q \)
• Modus tollens: if \( p \rightarrow q \) and \( \lnot q \), then \( \lnot p \)
• Reductio ad absurdum: assume the opposite and derive a contradiction

14. Consistency, Completeness, and Soundness

• Consistency: no contradictions in a logical system
• Completeness: every true statement is provable
• Soundness: only true statements can be proven

15. Gödel’s Incompleteness Theorems

1. Any sufficiently powerful consistent system cannot prove all true statements (incompleteness)
2. Such a system cannot prove its own consistency

These theorems limit what can be achieved with formal systems.

16. Applications in Mathematics, Physics, and Computing

• Mathematics: axiomatic foundations, logic proofs
• Physics: formal theories, model theory, quantum logic
• Computer science: programming languages, automated theorem proving, type theory

17. Conclusion

Set theory and logic form the core scaffolding of mathematics and theoretical reasoning. They provide the basis for defining, analyzing, and verifying all structures used in science, engineering, and philosophy.

A solid grounding in these topics is essential for deep engagement with advanced mathematical or physical theories.