Content deleted Content added
m →Related definitions: Attempted to fix some LaTeX math |
m →Related definitions: semicolon is traditional symbol for composition of relations |
||
| (42 intermediate revisions by 26 users not shown) | |||
Line 1:
{{Short description|none}}
This article examines the implementation of mathematical concepts in [[set theory]]. The implementation of a number of basic mathematical concepts is carried out in parallel in [[ZFC]] (the dominant set theory) and in [[New Foundations|NFU]], the version of Quine's [[New Foundations]] shown to be consistent by [[R. B. Jensen]] in 1969 (here understood to include at least axioms of [[Axiom of infinity|Infinity]] and [[Axiom of choice|Choice]]).
What is said here applies also to two families of set theories: on the one hand, a range of theories including [[Zermelo set theory]] near the lower end of the scale and going up to ZFC extended with [[large cardinal property|large cardinal]] hypotheses such as "there is a [[measurable cardinal]]"; and on the other hand a hierarchy of extensions of NFU which is surveyed in the [[New Foundations]] article. These correspond to different general views of what the set-theoretical universe is like, and it is the approaches to implementation of mathematical concepts under these two general views that are being compared and contrasted.
Line 7 ⟶ 8:
==Preliminaries==
The following sections carry out certain constructions in the two theories [[ZFC]] and [[New Foundations|NFU]] and compare the resulting implementations of certain mathematical structures (such as the [[natural numbers]]).
Mathematical theories prove theorems (and nothing else). So saying that a theory allows the construction of a certain object means that it is a theorem of that theory that that object exists. This is a statement about a definition of the form "the x such that <math>\phi</math> exists", where <math>\phi</math> is a [[Well-formed formula|formula]] of our [[Formal language|language]]: the theory proves the existence of "the x such that <math>\phi</math>" just in case it is a theorem that "there is one and only one x such that <math>\phi</math>". (See [[Bertrand Russell
ZFC and NFU share the language of set theory, so the same formal definitions "the x such that <math>\phi</math>" can be contemplated in the two theories. A specific form of definition in the language of set theory is [[set-builder notation]]: <math>\{x \mid \phi\}</math> means "the set A such that for all x, <math>x \in A \leftrightarrow \phi</math>" (A cannot be [[Free variables and bound variables|free]] in <math>\phi</math>). This notation admits certain conventional extensions: <math>\{x \in B \mid \phi\}</math> is synonymous with <math>\{x \mid x \in B \wedge \phi\}</math>; <math>\{f(x_1,\ldots,x_n) \mid \phi\}</math> is defined as <math>\{z \mid \exists x_1,\ldots,x_n\,(z=f(x_1,\dots,x_n) \wedge \phi)\}</math>, where <math>f(x_1,\ldots,x_n)</math> is an expression already defined.
Expressions definable in set-builder notation make sense in both ZFC and NFU: it may be that both theories prove that a given definition succeeds, or that neither do (the expression <math>\{x \mid x\not\in x\}</math> fails to refer to anything in ''any'' set theory with classical logic; in [[Class (set theory)|class]] theories like [[Von Neumann–Bernays–Gödel set theory|NBG]] this notation does refer to a class, but it is defined differently), or that one does and the other doesn't. Further, an object defined in the same way in ZFC and NFU may turn out to have different properties in the two theories (or there may be a difference in what can be proved where there is no provable difference between their properties).
Further, set theory imports concepts from other branches of mathematics (in intention, ''all'' branches of mathematics). In some cases, there are different ways to import the concepts into ZFC and NFU. For example, the usual definition of the first infinite [[Ordinal number|ordinal]] <math>\omega</math> in ZFC is not suitable for NFU because the object (defined in purely set theoretical language as the set of all finite [[von Neumann
Whatever is proven to exist in a theory clearly provably exists in any extension of that theory; moreover, analysis of the proof that an object exists in a given theory may show that it exists in weaker versions of that theory (one may consider [[Zermelo set theory]] instead of
== Empty set, singleton, unordered pairs and tuples ==
These constructions appear first because they are the simplest constructions in set theory, not because they are the first constructions that come to mind in mathematics (though the notion of finite set is certainly fundamental
:<math>\left.\varnothing\right. \, \overset{\mathrm{def.}}{=} \left\{x : x \neq x\right\}</math>▼
▲:<math>\left.\varnothing\right. \overset{\mathrm{def.}}{=} \left\{x : x \neq x\right\}</math>
For each object <math>x</math>, there is a set <math>\{x\}</math> with <math>x</math> as its only element:
:<math>\left\{x\right\} \overset{\mathrm{def.}}{=} \left\{y : y = x\right\}</math>
For objects <math>x</math> and <math>y</math>, there is a set <math>\{x,y\}</math> containing <math>x</math> and <math>y</math> as its only elements:
:<math>\left\{x,y\right\} \overset{\mathrm{def.}}{=} \left\{z : z=x \vee z = y\right\}</math>
The [[Union (set theory)|union]] of two sets is defined in the usual way:
:<math>\left.x \cup y\right. \, \overset{\mathrm{def.}}{=} \left\{z : z \in x \vee z \in y\right\}</math>
This is a recursive definition of unordered <math>n</math>-tuples for any concrete <math>n</math> (finite sets given as lists of their elements:)
:<math>\left\{x_1, \ldots, x_n, x_{n+1}\right\} \overset{\mathrm{def.}}{=} \left\{x_1, \ldots, x_n\right\} \cup \left\{x_{n+1}\right\}</math>
In
== Ordered pair ==
{{main article|Ordered pair}}
First, consider the '''ordered pair'''. The reason that this comes first is technical: ordered pairs are needed to implement [[Relation (mathematics)|relations]] and [[Function (mathematics)|functions]], which are needed to
The first definition of the ordered pair was the definition <math>(x,y) \overset{\mathrm{def}}{=} \{\{\{x\},\emptyset\},\{\{y\}\}\}</math> proposed by [[Norbert Wiener]] in 1914 in the context of the type theory of [[Principia Mathematica]]. Wiener observed that this allowed the elimination of types of ''n''-ary relations for
It is more usual now to use the definition <math>(x,y) \overset{\mathrm{def.}}{=} \{\{x\},\{x,y\}\}</math>, due to [[Kazimierz Kuratowski|Kuratowski]].
Either of these definitions works in either
The internal details of these definitions have nothing to do with their actual mathematical function. For any notion <math>(x,y)</math> of ordered pair, the
…and that it be reasonably easy to collect ordered pairs into sets.
== Relations ==
[[Relation (mathematics)|Relations]] are sets whose members are all [[ordered pair]]s. Where possible, a relation
In
to be sets (but may be harmlessly reified as [[proper class]]es). In
need to have the same type (because they appear as projections of the same pair), but also
successive types (because
=== Related definitions ===
Let <math>R</math> and <math>S</math> be given [[binary relation]]s. Then the following concepts are useful:
The '''[[
The '''___domain''' of <math>R</math> is the set <math>\left\{x : \exists y
The '''range''' of <math>R</math> is the ___domain of the converse of <math>R</math>. That is, the set <math>\left\{y : \exists x \left(xRy\right)\right\}</math>.
The '''field''' of <math>R</math> is the [[union (set theory)|union]] of the ___domain and range of <math>R</math>.
The '''[[preimage]]''' of a member <math>x</math> of the field of <math>R</math> is the set <math>\left\{y : yRx\right\}</math> (used in the definition of 'well-founded' below
The '''downward closure''' of a member <math>x</math> of the field of <math>R</math> is the smallest set <math>D</math> containing <math>x</math>, and containing each <math>zRy</math> for each <math>y \in D</math> (i.e., including the preimage of each of its elements with respect to <math>R</math> as a subset
The '''[[relation composition|relative product]]''' <math>R
Notice that with our formal definition of a binary relation, the range and codomain of a relation are not distinguished
In
▲Notice that the range and codomain of a relation are not distinguished: this could be done by representing a relation <math>R</math> with codomain <math>B</math> as <math>\left(R, B\right)</math>, but our development will not require this.
▲In [[ZFC]], any relation whose ___domain is a subset of a set <math>A</math> and whose range is a subset of a set <math>B</math> will be a set, since the [[cartesian product]] <math>A \times B = \left\{\left(a, b\right) : a \in A \wedge b \in B\right\}</math> is a set (being a subclass of <math>\mathcal{P}\!\left(A \cup B\right)</math>), and ''Separation'' provides for the existence of <math>\left\{\left(x, y\right) \in A \times B : xRy\right\}</math>. In [[New Foundations|NFU]], some relations with global scope (such as equality and subset) can be implemented as sets. In NFU, bear in mind that <math>x</math> and <math>y</math> are three types lower than <math>R</math> in <math>xRy</math> (one type lower if a type-level ordered pair is used).
=== Properties and kinds of relations ===
*'''[[Reflexive relation|Reflexive]]''' if
* '''[[Symmetric relation|Symmetric]]''' if <math>\forall x, y \,(xRy \to yRx)</math>.▼
* '''[[
* '''[[Antisymmetric relation|Antisymmetric]]''' if <math>\forall x, y \,(xRy \wedge yRx \rightarrow x=y)</math>.
* '''[[Well-founded relation|Well-founded]]''' if for every set
* '''Extensional''' if for every
Relations having certain combinations of the above properties have standard names.
▲* '''[[Symmetric relation|Symmetric]]''' if <math>\forall x,y \,(xRy \to yRx)</math>.
* An '''[[
* A '''[[linear order]]''' if
* A '''set picture''' if
== Functions ==▼
▲* '''[[Antisymmetric relation|Antisymmetric]]''' if <math>\forall x,y \,(xRy \wedge yRx \rightarrow x=y)</math>.
A
Outside of formal set theory, we usually specify a function in terms of its ___domain and codomain, as in the phrase "Let <math>f: A \to B</math> be a function". The ___domain of a function is just its ___domain as a relation, but we have not yet defined the codomain of a function. To do this we introduce the terminology that a function is '''from <math>A</math> to <math>B</math>''' if its ___domain equals <math>A</math> and its range ''is contained in'' <math>B</math>. In this way, every function is a function from its ___domain to its range, and a function <math>f</math> from <math>A</math> to <math>B</math> is also a function from <math>A</math> to <math>C</math> for any set <math>C</math> containing <math>B</math>.
▲* '''[[Well-founded relation|Well-founded]]''' if for every set ''S'' which meets the field of ''R'', <math>\ \exists x \in S</math> whose preimage under ''R'' does not meet ''S''.
Indeed, no matter which set we consider to be the codomain of a function, the function does not change as a set since by definition it is just a set of ordered pairs. That is, a function does not determine its codomain by our definition. If one finds this unappealing then one can instead define a function as the ordered pair <math>(f, B)</math>, where <math>f</math> is a functional relation and <math>B</math> is its codomain, but we do not take this approach in this article (more elegantly, if one first defines ordered triples - for example as <math>(x, y, z) = (x, (y, z))</math>- then one could define a function as the ordered triple <math>(f, A, B)</math> so as to also include the ___domain). Note that the same issue exists for relations: outside of formal set theory we usually say "Let <math>R \subseteq A \times B</math> be a binary relation", but formally <math>R</math> is a set of ordered pairs such that <math>\text{dom}\,R \subseteq A</math> and <math>\text{ran}\,R \subseteq B</math>.
▲* '''Extensional''' if for every ''x,y'' in the field of ''R'', ''x=y'' if and only if ''x'' and ''y'' have the same preimage under ''R''.
In
▲Relations having certain combinations of the above properties have standard names. ''R'' is:
The function <math>I</math> such that <math>I\!\left(x\right) = x</math> is not a set in
▲* A '''[[partial order]]''' if ''R'' is reflexive, antisymmetric, and transitive.
▲* A '''[[linear order]]''' if ''R'' is a partial order and for every ''x,y'' in the field of ''R'', either ''xRy'' or ''yRx''.
▲* A '''[[well-ordering]]''' if ''R'' is a linear order and well-founded.
▲* A '''set picture''' if ''R'' is well-founded and extensional, and the field of ''R'' either equals the downward closure of one of its members (called its ''top element''), or is empty.
▲== Functions ==
▲A [[function (set theory)|functional relation]] is a [[binary predicate]] <math>F</math> such that <math>\forall x, y, z\,\left(xFy \wedge xFz \to y = z\right)</math>. Such a [[Relation (mathematics)|relation]] ([[Predicate (logic)|predicate]]) is implemented as a relation (set) exactly as described in the previous section. So the predicate <math>F</math> is implemented by the set <math>\left\{\left(x, y\right) : xFy\right\}</math>. A set of ordered pairs <math>F</math> is a function if and only if <math>\forall x, y, z\,\left(\left(x, y\right) \in F \wedge \left(x, z\right) \in F \to y = z\right)</math>. It is therefore possible to define this function <math>F\!\left(x\right)</math> as the unique object <math>y</math> such that <math>xFy</math> – i.e.: <math>x</math> is <math>F</math>-related to <math>y</math> such that the relation <math>f</math> holds between <math>x</math> and <math>y</math> – or as the unique object <math>y</math> such that <math>\left(x, y\right) \in F</math>. The presence in both theories of functional predicates which are not sets makes it useful to allow the notation <math>F\!\left(x\right)</math> both for sets <math>F</math> and for important functional predicates. As long as one does not quantify over functions in the latter sense, all such uses are in principle eliminable.
▲In [[New Foundations|NFU]], <math>x</math> has the same type as <math>F\!\left(x\right)</math>, and <math>F</math> is three types higher than <math>F\!\left(x\right)</math> (one type higher, if a type-level ordered pair is used). To solve this problem, one could define <math>F\left[A\right]</math> as <math>\left\{y : \exists x\,\left(x \in A \wedge y = F\!\left(x\right)\right)\right\}</math> for any set <math>A</math>, but this is more conveniently written as <math>\left\{F\!\left(x\right) : x \in A\right\}</math>. Then, if <math>A</math> is a set and <math>F</math> is any functional relation, the '[[axiom of replacement]]' assures that <math>F\left[A\right]</math> is a set in [[ZFC]]. In NFU, <math>F\left[A\right]</math> and <math>A</math> now have the same type, and <math>F</math> is two types higher than <math>F\left[A\right]</math> (the same type, if a type-level ordered pair is used).
▲The function <math>I\!\left(x\right) = x</math> is not a set in [[ZFC]] because it is 'too large.' <math>I\!\left(x\right)</math> is, however, a set in NFU. The function (predicate) <math>S\!\left(x\right) = \left\{x\right\}</math> is neither a function nor a set in either theory; in ZFC, this is true because such a set would be too large, and, in NFU, this is true because its definition would not be [[Stratified formula#In set theory|stratified]]. Moreover, <math>S\!\left(x\right)</math> can be proved not to exist in NFU (see the resolution of Cantor's paradox in [[New Foundations]].)
=== Operations on functions ===
Let <math>f</math> and <math>g</math> be arbitrary functions. The '''[[function composition|composition]]''' of <math>f</math> and <math>g</math>, <math>g \circ f</math>, is defined as the relative product <math>f
=== Special kinds of function ===
▲If <math>f</math> is a function from <math>A</math> to <math>B</math>, <math>f</math> is a:
* '''[[Injective function|Injection]]''' from <math>A</math> to <math>B</math> if the [[image (mathematics)|image]]s under <math>f</math> of distinct members of <math>A</math> are distinct members of <math>B</math>.
* '''[[Surjection]]''' from <math>A</math> to <math>B</math> if the range of <math>f</math> is <math>B</math>.
* '''[[Bijection]]''' from <math>A</math> to <math>B</math> if <math>f</math> is both an injection and a surjection.
Defining functions as ordered pairs <math>(f, B)</math> or ordered triples <math>(f, A, B)</math> has the advantages that we do not have to introduce the terminology of being a function "from <math>A</math> to <math>B</math>", and that we can speak of "being surjective" outright as opposed to only being able to speak of "being surjective onto <math>B</math>".
== Size of sets ==
In both [[ZFC]] and [[New Foundations|NFU]], two sets ''A'' and ''B'' are the same size (or are '''[[equinumerous]]''') if and only if there is a [[
Similarly, define <math>|A| \leq |B|</math> as holding if and only if there is an [[Injective function|injection]] from ''A'' to ''B''.
It is straightforward to show that the relation of equinumerousness is an [[equivalence relation]]: equinumerousness of ''A'' with ''A'' is witnessed by <math>i_A</math>; if ''f'' witnesses <math>|A|=|B|</math>, then <math>f^{-1}</math> witnesses <math>|B|=|A|</math>; and if ''f'' witnesses <math>|A|=|B|</math> and ''g'' witnesses <math>|B|=|C|</math>, then <math>g\circ f</math> witnesses <math>|A|=|C|</math>.
It can be shown that <math>|A| \leq |B|</math> is a [[linear order]] on abstract cardinals, but not on sets. Reflexivity is obvious and transitivity is proven just as for equinumerousness. The [[
*<math>|A| \leq |B| \wedge |B| \leq |A| \rightarrow |A| = |B|</math>
(this establishes antisymmetry on cardinals), and
Line 148 ⟶ 137:
The usual operations of arithmetic can be defined recursively and in a style very similar to that in which the set of natural numbers itself is defined. For example, + (the addition operation on natural numbers) can be defined as the smallest set which contains <math>((x,\emptyset),x)</math> for each natural number <math>x</math> and contains <math>((x,y \cup \{y\}),z \cup \{z\})</math> whenever it contains <math>((x,y),z)</math>.
In NFU, it is not obvious that this approach can be used, since the successor operation <math>y \cup \{y\}</math> is unstratified and so the set ''N'' as defined above cannot be shown to exist in NFU (
The standard definition of the natural numbers, which is actually the oldest [[set-theoretic definition of natural numbers]], is as equivalence classes of finite sets under equinumerousness. Essentially the same definition is appropriate to [[New Foundations|NFU]] (this is not the usual definition, but the results are the same): define ''Fin'', the set of finite sets, as
Line 160 ⟶ 149:
(But note that this style of definition is feasible for the ZFC numerals as well, but more circuitous: the form of the [[New Foundations|NFU]] definition facilitates set manipulations while the form of the ZFC definition facilitates recursive definitions, but either theory supports either style of definition).
The two implementations are quite different. In ZFC, choose a [[representative (mathematics)|representative]] of each finite cardinality (the equivalence classes themselves are too large to be sets); in NFU the equivalence classes themselves are sets, and are thus an obvious choice for objects to stand in for the cardinalities. However, the arithmetic of the two theories is identical: the same abstraction is implemented by these two superficially different approaches.
== Equivalence relations and partitions ==
Line 180 ⟶ 169:
In [[New Foundations]] (NFU), the '''order type''' of a well-ordering ''W'' is the set of all well-orderings which are similar to ''W''. The set of '''ordinal numbers''' is the set of all order types of well-orderings.
This does not work in [[ZFC]], because the equivalence classes are too large. It would be formally possible to use [[Scott's trick]] to define the ordinals in essentially the same way, but a device of [[John von Neumann|von Neumann]] is more commonly used.
For any partial order <math>\leq</math>, the corresponding '''strict partial order''' < is defined as <math>\{(x,y) \mid x \leq y \wedge x \neq y\}</math>. Strict linear orders and strict well-orderings are defined similarly.
Line 209 ⟶ 198:
Cardinal numbers are defined in [[New Foundations|NFU]] in a way which generalizes the definition of natural
number: for any set ''A'', <math>|A|
In [[ZFC]], these equivalence classes are too large as usual. Scott's trick could be used (and indeed is used in [[Zermelo–Fraenkel set theory|ZF]]), <math>|A|</math> is usually defined as the smallest order type (here a von Neumann ordinal) of a well-ordering of ''A'' (that every set can be well-ordered follows from
Line 221 ⟶ 210:
Cantor's theorem shows (in both theories) that there are nontrivial distinctions between infinite cardinal numbers. In [[ZFC]], one proves <math>|A|<|P(A)|.</math> In [[New Foundations|NFU]], the usual form of Cantor's theorem is false (consider the case A=V), but Cantor's theorem is an ill-typed statement. The correct form of the theorem in [[New Foundations|NFU]] is <math>|P_1(A)|<|P(A)|</math>, where <math>P_1(A)</math> is the set of one-element subsets of A. <math>|P_1(V)|<|P(V)|</math> shows that there are "fewer" singletons than sets (the obvious bijection <math>x \mapsto \{x\}</math> from <math>P_1(V)</math> to ''V'' has already been seen not to be a set). It is actually provable in NFU + Choice that <math>|P_1(V)|<|P(V)|\ll|V|</math> (where <math>\ll</math> signals the existence of many intervening cardinals; there are many, many urelements!). Define a type-raising T operation on cardinals analogous to the T operation on ordinals: <math>T(|A|) = |P_1(A)|</math>; this is an external endomorphism of the cardinals just as the T operation on ordinals is an external endomorphism of the ordinals.
A set ''A'' is said to be
The operations of cardinal arithmetic are defined in a set-theoretically motivated way in both theories. <math>|A| + |B| = \{C \cup D \mid C \sim A \wedge D \sim B \wedge C \cap D = \emptyset\}</math>. One would like to define <math>|A|\cdot|B|</math> as <math>|A \times B|</math>, and one does this in [[ZFC]], but there is an obstruction in [[New Foundations|NFU]] when using the Kuratowski pair: one defines <math>|A|\cdot|B|</math> as <math>T^{-2}(|A \times B|)</math> because of the type displacement of 2 between the pair and its projections, which implies a type displacement of two between a cartesian product and its factors. It is straightforward to prove that the product always exists (but requires attention because the inverse of T is not total).
Line 265 ⟶ 254:
In this class of constructions it appears that [[ZFC]] has an advantage over [[New Foundations|NFU]]: though the constructions are clearly feasible in [[New Foundations|NFU]], they are more complicated than in ZFC for reasons having to do with stratification.
Throughout this section assume a type-level ordered pair. Define <math>(x_1,x_2,\ldots,x_n
General cartesian products are defined similarly: <math>A_1 \times A_2 \times \ldots \times A_n = A_1 \times (A_2 \times \ldots \times A_n)</math>
Line 324 ⟶ 313:
==References==
*[[Keith Devlin]], 1994. ''The Joy of Sets'', 2nd ed. Springer-Verlag.
*Holmes, Randall, 1998. ''[
*Potter, Michael, 2004. ''Set Theory and its Philosophy'', 2nd ed. Oxford Univ. Press.
*Suppes, Patrick, 1972. ''Axiomatic Set Theory''. Dover.
*Tourlakis, George, 2003. ''Lectures in Logic and Set Theory, Vol. 2''. Cambridge Univ. Press.
==
* [http://us.metamath.org/ Metamath:] A web site devoted to an ongoing derivation of mathematics from the axioms of ZFC and [[first-order logic]].
* [[Stanford Encyclopedia of Philosophy]]:
** [http://plato.stanford.edu/entries/quine-nf Quine's New Foundations]
** [http://setis.library.usyd.edu.au/stanford/entries/settheory-alternative/ Alternative axiomatic set theories]
* Randall Holmes: [
{{Mathematical logic}}
[[Category:Large-scale mathematical formalization projects]]▼
[[Category:Formalism (deductive)]]▼
[[Category:Mathematical logic]]
[[Category:Set theory]]
▲[[Category:Formalism (deductive)]]
▲[[Category:Large-scale mathematical formalization projects]]
| |||