1 What is Set Theory?
Set theory is the branch of mathematics that studies collections of objects called sets and forms the foundational language for nearly all mathematical structures. It explores the existence, relationships, and properties of sets and operations on them, and it lays the groundwork for logic, number systems, topology, analysis, and more. In this note we specifically consider naïve set theory.
2 Topics
- [[set-theory-fundamentals]]
- De Morgan's Laws
2.1 Inclusion Exclusion Principle
The cardinality operator is a function \(\lvert \cdot \rvert\) giving the number of elements (known as the cardinality) of a finite set.
In combinatorics, the inclusion-exclusion principle is a counting technique generalizing the familiar method of obtaining he number of elements in the union of two finite sets. For two sets \(A\) and \(B\) the principle states \[ \lvert A \cup B \rvert =\lvert A \rvert + \lvert B \rvert -\lvert A \cap B \rvert . \] Generalizing to \(n\) indexed sets \(A_{1}, \dots, A_{n}\) the principle states \[ \left\lvert \bigcup_{i=1}^n A_{i} \right\rvert =\sum_{k=1}^{n}(-1)^{k+1}\left( \sum_{1\leq i_{1}<\dots<i_{k } \leq n}^{}\left| A_{i_{1}} \cap \dots \cap A_{i_{k}} \right| \right) . \]
2.2 Limit Supremum and Limit Infimum
Consider infinite sequences, i.e. a collection, of sets indexed by some ordered set, for example \(\{ A_{n} \}_{n \in \mathbb{N}}\). On these sequences we can define notion of the limit infimum and limit supremum of ordered indexed sets of sets \[ \begin{align} \liminf_{n to \infty}X_{n} & := \bigcup_{k=1}^\infty\bigcap_{m=k}^\infty X_{m}=\{ x: x \in X_{n}~\text{for all but finite }n \}, \\ \limsup_{n to \infty}X_{n} & := \bigcap_{k=1}^\infty\bigcup_{m=k}^\infty X_{m}=\{ x: x \in X_{n}~\text{for infinitely many }n \}. \end{align} \]
3 Functions, Relations, and Orders
3.1 Relations
Functions as sets of ordered pairs
Injections, surjections, bijections
Relations: reflexivity, symmetry, transitivity
Equivalence relations and partitions
Partial and total orders
4 Cardinality and Infinite Sets
Finite vs. infinite
Countable sets: N,QN,Q
Uncountable sets: RR
4.0.1 Theorems:
Cantor’s Diagonal Argument: RR is uncountable
Countable Union of Countables is Countable
Schröder–Bernstein Theorem: If A≤BA≤B and B≤AB≤A, then A≅BA≅B