🤔Mathematical Logic Unit 6 – Set Theory – Axioms and Operations

What's Set Theory All About?

• Set theory provides a rigorous foundation for mathematics by defining basic objects called sets and their properties
• Sets are collections of distinct objects, and set theory studies the relationships between these collections
• Fundamental concepts in set theory include membership, subset, union, intersection, and complement
• Set theory allows for precise definitions and proofs of mathematical statements using logical operations and quantifiers
• Axiomatic set theory, such as Zermelo-Fraenkel set theory (ZFC), establishes a consistent framework for building mathematical theories
• Set theory has applications in various branches of mathematics, including analysis, topology, and algebra
• Paradoxes in naive set theory, such as Russell's paradox, led to the development of axiomatic set theory to avoid inconsistencies

Key Concepts and Definitions

• A set is a well-defined collection of distinct objects, called elements or members
• The notation $a \in A$ means that $a$ is an element of the set $A$
• A set can be described by listing its elements between curly braces, such as $A = \{1, 2, 3\}$
• The empty set, denoted by $\emptyset$ or $\{\}$, is the set containing no elements
• Two sets are equal if and only if they have the same elements
• A set $A$ is a subset of a set $B$, denoted by $A \subseteq B$, if every element of $A$ is also an element of $B$
  • A proper subset, denoted by $A \subset B$, is a subset where $A \neq B$
• The power set of a set $A$, denoted by $\mathcal{P}(A)$, is the set of all subsets of $A$
• The cardinality of a set $A$, denoted by $|A|$, is the number of elements in the set
  • Finite sets have a natural number cardinality, while infinite sets have transfinite cardinalities

Axioms of Set Theory

• The axioms of set theory provide a consistent foundation for building mathematical theories
• The Axiom of Extensionality states that two sets are equal if and only if they have the same elements
• The Axiom of Empty Set asserts the existence of the empty set, $\emptyset$
• The Axiom of Pairing states that for any two sets $a$ and $b$, there exists a set $\{a, b\}$ containing exactly these elements
• The Axiom of Union states that for any set $A$, there exists a set $\bigcup A$ containing all elements that belong to at least one set in $A$
• The Axiom of Power Set states that for any set $A$, there exists a set $\mathcal{P}(A)$ containing all subsets of $A$
• The Axiom of Infinity asserts the existence of an infinite set, typically the set of natural numbers
• The Axiom of Separation (or Subset Selection) allows the construction of a subset of a given set satisfying a specific property
• The Axiom of Replacement allows the construction of a new set by replacing elements of an existing set according to a given function

Basic Set Operations

• The union of two sets $A$ and $B$, denoted by $A \cup B$, is the set containing all elements that belong to either $A$ or $B$ (or both)
• The intersection of two sets $A$ and $B$, denoted by $A \cap B$, is the set containing all elements that belong to both $A$ and $B$
• The difference of two sets $A$ and $B$, denoted by $A \setminus B$, is the set containing all elements of $A$ that are not elements of $B$
• The complement of a set $A$ with respect to a universal set $U$, denoted by $A^c$ or $U \setminus A$, is the set containing all elements of $U$ that are not elements of $A$
• The Cartesian product of two sets $A$ and $B$, denoted by $A \times B$, is the set of all ordered pairs $(a, b)$ where $a \in A$ and $b \in B$
  • This concept can be extended to the Cartesian product of $n$ sets, resulting in $n$-tuples
• Set operations can be visualized using Venn diagrams, which represent sets as overlapping or disjoint shapes

Set Relationships and Properties

• Two sets $A$ and $B$ are disjoint if their intersection is the empty set, i.e., $A \cap B = \emptyset$
• A collection of sets is pairwise disjoint if any two sets in the collection are disjoint
• A set $A$ is a subset of a set $B$, denoted by $A \subseteq B$, if every element of $A$ is also an element of $B$
  • If $A \subseteq B$ and $B \subseteq A$, then $A = B$
• The power set of a set $A$, denoted by $\mathcal{P}(A)$, is the set of all subsets of $A$
  • The cardinality of the power set of a finite set $A$ is $2^{|A|}$
• A set is finite if it has a natural number cardinality, and infinite otherwise
  • Countable sets are infinite sets with the same cardinality as the natural numbers, while uncountable sets have a larger cardinality
• The continuum hypothesis states that there is no set with a cardinality between that of the natural numbers and the real numbers

Advanced Set Operations

• The symmetric difference of two sets $A$ and $B$, denoted by $A \triangle B$, is the set of elements that belong to either $A$ or $B$, but not both
  • Formally, $A \triangle B = (A \setminus B) \cup (B \setminus A)$
• The Cartesian product of a set $A$ with itself $n$ times is denoted by $A^n$ and consists of all ordered $n$-tuples of elements from $A$
• The power set operation can be iterated, leading to higher-order power sets such as $\mathcal{P}(\mathcal{P}(A))$
• The axiom of choice states that, given a collection of non-empty sets, it is possible to select an element from each set to form a new set
  • This axiom is independent of the other axioms of ZFC and has important consequences in mathematics
• Transfinite recursion is a method for defining functions on ordinal numbers, which extends the concept of induction to infinite sets
• The continuum hypothesis, stating that there is no set with a cardinality between that of the natural numbers and the real numbers, is independent of the axioms of ZFC

Applications in Mathematical Logic

• Set theory provides a foundation for mathematical logic by allowing the construction of models for logical systems
• Propositional logic can be modeled using sets, with logical connectives corresponding to set operations (e.g., conjunction as intersection, disjunction as union)
• First-order logic can be interpreted in set theory, with variables ranging over sets and predicates corresponding to set membership or relationships
• The completeness and soundness of logical systems can be proven using set-theoretic methods
• Set theory is used to define structures in model theory, such as groups, rings, and fields
• The independence of the continuum hypothesis and the axiom of choice from the other axioms of ZFC was proven using model-theoretic techniques

Common Pitfalls and How to Avoid Them

• Confusing the symbols for element ($\in$) and subset ($\subseteq$)
  • Remember that $a \in A$ means $a$ is an element of the set $A$, while $A \subseteq B$ means every element of $A$ is also an element of $B$
• Forgetting to specify the universal set when taking complements
  • Always make sure to clearly define the universal set $U$ when using the complement operation, as $A^c = U \setminus A$
• Misinterpreting the empty set as a non-existent entity
  • The empty set is a well-defined set that contains no elements, and it is a subset of every set
• Applying set operations to non-sets or mixing sets of different types
  • Ensure that the objects you are working with are well-defined sets and that the operations you apply are valid for the given sets
• Confusing the cardinality of a set with its elements
  • The cardinality $|A|$ is a measure of the size of the set $A$, not an element of the set itself
• Assuming that all infinite sets have the same cardinality
  • There are different levels of infinity, with some infinite sets (like the real numbers) having a larger cardinality than others (like the natural numbers)