ZFC Set Theory
This post introduces set theory. The naive theory encountered some paradoxes during 19 century. As a result, people created axiomatic set theories.
Among them, ZFC is the basic axiom system for modern (2000) set theory.
Set Theory
Source: wiki
Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concerned with those that are relevant to mathematics as a whole.
The modern study of set theory was initiated by the German mathematicians Richard Dedekind and Georg Cantor in the 1870s. In particular, Georg Cantor is commonly considered the founder of set theory. The non-formalized systems investigated during this early stage go under the name of naive set theory. After the discovery of paradoxes within naive set theory (such as Russell's paradox, Cantor's paradox and the Burali-Forti paradox), various axiomatic systems were proposed in the early twentieth century, of which Zermelo–Fraenkel set theory (with or without the axiom of choice) is still the best-known and most studied.
Set theory is commonly employed as a foundational system for the whole of mathematics, particularly in the form of Zermelo–Fraenkel set theory with the axiom of choice.[1] Besides its foundational role, set theory also provides the framework to develop a mathematical theory of infinity, and has various applications in computer science (such as in the theory of relational algebra), philosophy and formal semantics. Its foundational appeal, together with its paradoxes, its implications for the concept of infinity and its multiple applications, have made set theory an area of major interest for logicians and philosophers of mathematics. Contemporary research into set theory covers a vast array of topics, ranging from the structure of the real number line to the study of the consistency of large cardinals.
Definition of Set
Source: wiki
A set is the mathematical model for a collection of different things; a set contains elements or members, which can be mathematical objects of any kind: numbers, symbols, points in space, lines, other geometrical shapes, variables, or even other sets.
- The set with no element is the empty set; a set with a single element is a singleton.
- A set may have a finite number of elements or be an infinite set.
Sets are uniquely characterized by their elements; this means that two sets that have precisely the same elements are equal (they are the same set).This property is called extensionality. In particular, this implies that there is only one empty set.
Sets are ubiquitous in modern mathematics. Indeed, set theory, more specifically Zermelo–Fraenkel set theory, has been the standard way to provide rigorous foundations for all branches of mathematics since the first half of the 20th century.
Naive Set Theory
Source: wiki
Naive set theory is any of several theories of sets used in the discussion of the foundations of mathematics. Unlike axiomatic set theories, which are defined using formal logic, naive set theory is defined informally, in natural language.
朴素集合论是通过自然语言定义的, 而不是通过严谨的公理系统.
朴素集合论认为, 集合就是所有满足性质P(在该性质已经给定的情况下)的所有元素x所组成的集合. 也就是说一个集合S是根据一个性质P来定义的.
罗素悖论: 我有一个集合, 这个集合是由所有不属于它的元素构成的, 那这个集合是否存在？ \[ X = \{x | x \notin X\} \]
理论上来说这个集合是不能存在的, 因为它要是存在, 那X的元素到底属不属于X?
罗素悖论证明了不是所有的集合都可以存在, 因此有必要建立公理化的集合论.
Axiomatic Set Theory
->Source
在數學中，公理化集合论是集合論透過建立一階邏輯的嚴謹重整，以解決樸素集合論中出現的悖論。集合論的基礎主要由德國數學家格奧爾格·康托爾在19世紀末建立。
公理化集合論不直接定義集合和集合成員, 而是先規範可以描述其性質的一些公理.
ZFC
ZFC = Zermelo–Fraenkel set theory with the axiom of choice.
ZFC(Zermelo–Fraenkel set theory with the axiom of choice) is the basic axiom system for modern (2000) set theory and is the most common foundation of mathematics.
It's proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such as Russell's paradox.
ZFC就是向ZF增加选择公理. 选择公理曾饱受争议，因为选择函数的存在性是非构造性的；选择公理确立了选择函数的存在，而不说明如何构造这些函数。所以使用选择公理构造的一些集合，尽管可以证明其存在，但可能无法详细、描述性地构造出。因此，当一个结论依赖于选择公理时，有时会被明确地指出.
ZFC公理系统承认极限的存在, 承认选择公理, 承认排中律.
ZFC一般由一阶逻辑写出, 实际上包含了无穷多个公理, 因为替代公理(axiom of replacement)实际上是公理模式.
Zermelo-Fraenkel Set Theory (ZF)
Source: Stanford Encyclopedia of Philosophy
Axiom of Extensionality
\[ ∀x∀y[∀z(z∈x↔z∈y)→x=y] \]
This axiom asserts that when sets \(x\) and \(y\) have the same members, they are the same set.
Axiom of the empty set
This axiom asserts the existence of the empty set: \[ ∃x¬∃y(y∈x \]
Since it is provable from this axiom and the previous axiom that there is a unique such set, we may introduce the notation \(∅\) to denote it.
Axiom of pairs
This axiom asserts that given any sets \(x\) and \(y\), there exists a pair set of \(x\) and \(y\), i.e., a set which has only \(x\) and \(y\) as members: \[ ∀x∀y∃z∀w(w∈z↔w=x∨w=y) \]
Since it is provable that there is a unique pair set for each given \(x\) and \(y\), we introduce the notation \(\{x,y\}\) to denote it. In the particular case when \(x=y\), the axiom asserts the existence of the singleton \(\{x\}\), namely the set having \(x\) as its unique member.
Axiom of power set
This axiom asserts that for any set \(x\), there is a set \(y\) which contains as members all those sets whose members are also elements of \(x\), i.e., \(y\) contains all of the subsets of \(x\): \[ ∀x∃y∀z[z∈y↔∀w(w∈z→w∈x)] \] Since every set provably has a unique ‘power set’, we introduce the notation \(\mathcal P(x)\) to denote it.
Note also that we may define the notion "\(x\) is a subset of \(y\) (\(x⊆y\))" as: \(∀z(z∈x→z∈y)\). Then we may simplify the statement of the Power Set Axiom as follows: \[ ∀x∃y∀z(z∈y↔z⊆x) \]
Axiom of union
This axiom asserts that for any given set \(x\), there is a set \(y\) which has as members all of the members of all of the members of \(x\) \[ ∀x∃y∀z[z∈y↔∃w(w∈x∧z∈w)] \]
Since it is provable that there is a unique ‘union’ of any set \(x\), we introduce the notation \(⋃x\) to denote it.
Axiom of infinity
This axiom asserts the existence of an infinite set, i.e., a set with an infinite number of members: \[ ∃x[∅∈x∧∀y(y∈x→⋃{y,{y}}∈x)] \]
We may think of this as follows. Let us define "the union of x and y" (\(x∪y\)) as the union of the pair set of \(x\) and \(y\), i.e., as \(⋃{x,y}\). Then the Axiom of Infinity asserts that there is a set \(x\) which contains ∅ as a member and which is such that whenever a set \(y\) is a member of \(x\), then \(y∪\{y\}\) is also a member of \(x\).
Consequently, this axiom guarantees the existence of a set of the following form: \[ \{∅, \{ ∅ \}, \{ ∅, \{ ∅ \} \}, \{ ∅, \{ ∅ \}, \{ ∅, \{ ∅ \} \} \},…\} \]
Notice that the second element, \(\{∅\}\), is in this set because
- the fact that \(∅\) is in the set implies that \(∅∪\{∅\}\) is in the set and
- \(∅∪\{∅\}\) just is \(\{∅\}\).
Similarly, the third element, \(\{∅,\{∅\}\}\), is in this set because
- the fact that {∅} is in the set implies that {∅}∪ is in the set and
- \(\{∅\}∪ \{ \{ ∅ \} \}\) just is \(\{ ∅, \{ ∅ \} \}\).
And so forth.
Axiom (schema) of separation
This is the Separation Schema, which is a formula-pattern that uses a metavariable (in this case \(ψ\)) to describe an infinite list of axioms – one axiom for each formula of the language of set theory with at least a free variable.
Every instance of the Separation Schema asserts the existence of a set that contains the elements of a given set w that satisfy a certain condition, which is given by a formula \(ψ\).
That is, suppose that \(ψ(x,u_1,…,u_k)\) is a formula of the language of set theory that has \(x\) free and may or may not have \(u_1,…,u_k\) free. Then the Separation Schema for the condition \(ψ\) asserts: \[ ∀u1…∀uk[∀w∃v∀r(r∈v↔r∈w∧ψ(r,u1,…,uk))] \]
In other words, given sets \(w\) and \(u_1,…,u_k\), there exists a set \(v\) which has as members precisely the members \(r\) of \(w\) which satisfy the formula \(ψ(r,u_1,…,u_k)\).
Axiom (schema) of replacement
This is the Replacement Schema, which is also a formula-pattern that uses a metavariable (in this case \(ϕ\)) to describe an infinite list of axioms -- one axiom for each formula of the language of set theory with at least two free variables. Suppose that \(ψ(x, y, u_1,…,u_k)\) is a formula with \(x\) and \(y\) free, and in which \(u_1,…u_k\) may or may not be free. Then the instance of the Replacement Schema given by \(ϕ(x,y,u_1,…,u_k)\) is the following axiom: \[ ∀u1…∀uk[∀x∃!yϕ(x,y,u1,…uk)→ \\ ∀w∃v∀r(r∈v↔∃s(s∈w∧ϕ(s,r,u1,…uk)))] \]
In other words, if we know that \(ϕ\) is a functional formula (which relates each set \(x\) to a unique set y), then if we are given a set \(w\), we can form a new set \(v\) as follows: collect all of the sets to which the members of w are uniquely related by \(ϕ\).
Note that the Replacement Schema can take you ‘out of’ the set \(w\) when forming the set \(v\). The elements of \(v\) need not be elements of \(w\). By contrast, the Separation Schema of Zermelo only yields subsets of the given set \(w\).
Axiom of regularity
The final axiom asserts that every set is ‘well-founded’: \[ ∀x[x≠∅→∃y(y∈x∧∀z(z∈x→¬(z∈y)))] \] A member \(y\) of a set \(x\) with this property is called a ‘minimal’ element. This axiom rules out the existence of circular chains of sets (e.g., such as \(x∈y∧y∈z∧z∈x\)) as well as infinitely descending chains of sets (such as \(… x3∈x2∈x1∈x0\)).
Axiom of Choice
Axiom of Choice: Let \(\left(E_\alpha\right)_{\alpha \in A}\) be a family of nonempty sets \(E_\alpha\), indexed by an index set \(A\). Then we can find a family \(\left(x_\alpha\right)_{\alpha \in A}\) of elements \(x_\alpha\) of \(E_\alpha\), indexed by the same set \(A\).
This axiom is trivial when A is a singleton set, and from math- ematical induction one can also prove it without difficulty when A is finite. However, when A is infinite, one cannot deduce this axiom from the other axioms of set theory, but must explicitly add it to the list of axioms.
在对测度论的研究中我们会发现, 如果我们接受“选择公理”，则我们必须接纳不可测集. 这是数学中令人遗憾的事实: 不是所有的集合都是Lebesgue可测的.