Implementation of mathematics in set theory
Encyclopedia
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 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 Infinity and 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
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.
It is not the primary aim of this article to say anything about the relative merits of these theories as foundations for mathematics. The reason for the use of two different set theories is to illustrate that multiple approaches to the implementation of mathematics are feasible. Precisely because of this approach, this article is not a source of "official" definitions for any mathematical concept.
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
exists", where 
is a formula of our language: the theory proves the existence of "the x such that 
" just in case it is a theorem that "there is one and only one x such that 
". (See Bertrand Russell
's theory of descriptions
.) Loosely, the theory "defines" or "constructs" this object in this case. If the statement is not a theorem, the theory cannot show that the object exists; if the statement is provably false in the theory, it proves that the object cannot exist; loosely, the object cannot be constructed.
ZFC and NFU share the language of set theory, so the same formal definitions "the x such that
" can be contemplated in the two theories. A specific form of definition in the language of set theory is set-builder notation: 
means "the set A such that for all x, 
" (A cannot be free in 
). This notation admits certain conventional extensions: 
is synonymous with 
; 
is defined as 
, where 
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
fails to refer to anything in any set theory with classical logic; in class theories like 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
in ZFC is not suitable for NFU because the object (defined in purely set theoretical language as the set of all finite von Neumann ordinals) cannot be shown to exist in NFU. The usual definition of 
in NFU is (in purely set theoretical language) as the set of all infinite well-orderings all of whose proper initial segments are finite, an object which can be shown not to exist in ZFC. In the case of such imported objects, there may be different definitions, one for use in ZFC and related theories, and one for use in NFU and related theories. For such "implementations" of imported mathematical concepts to make sense, it is necessary to be able to show that the two parallel interpretations have the expected properties: for example, the implementations of the natural numbers in ZFC and NFU are different, but both are implementations of the same mathematical structure, because both include definitions for all the primitives of Peano arithmetic and satisfy (the translations of) the Peano axioms. It is then possible to compare what happens in the two theories as when only set theoretical language is in use, as long as the definitions appropriate to ZFC are understood to be used in the ZFC context and the definitions appropriate to NFU are understood to be used in the NFU context.
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 ZFC for much of what is done in this article, for example).
The empty set is the unique set with no members. In NFU, there are also urelements with no members.
For each object x, there is a set
with x as its only element.
For objects x and y, there is a set
containing x and y as its only elements.
The union of two sets is defined in the usual way.
This is a recursive definition of unordered n-tuples for any concrete n (finite sets given as lists of their elements).
In NFU
, all the set definitions given work by stratified comprehension; in ZFC, the existence of the unordered pair is given by the axiom of Pairing, the existence of the empty set follows by Separation from the existence of any set, and the boolean union of two sets exists by the axioms of Pairing and Union (
).
and functions
which are needed to implementat other concepts which may seem to be prior.
The first definition of the ordered pair was the definition
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
from the system of that work.
It is more usual now to use the definition
, due to Kuratowski.
Either of these definitions works in either ZFC or NFU
. In NFU, the Kuratowski pair has a technical disadvantage: it is two types higher than its projections. It is common to postulate the existence of a type-level ordered pair (a pair
which is the same type as its projections) in NFU. It is convenient to use the Kuratowski pair in both systems until the use of type-level pairs can be formally justified.
The internal details of these definitions have nothing to do with their actual mathematical function. For any notion
of ordered pair, the things that matter are that it satisfy the defining condition
and that it be reasonably easy to collect ordered pairs into sets.
are sets whose members are all ordered pair
s. Where possible, a relation R (understood as a binary predicate) is implemented as
(which may be written as 
). Where R is a set of ordered pairs, read xRy as (x,y)∈R.
In ZFC, some relations (such as the general equality relation or subset relation on sets) are "too large"
to be sets (but may be harmlessly reified as proper classes). In NFU
, some relations (such as the membership relation) are not sets because their definitions are not stratified: in
x and y would
need to have the same type (because they appear as projections of the same pair), but also
successive types (because x is considered as an element of y).
s. Then the following concepts are useful:
The converse
of R is the relation
.
The domain of R is the set
.
The range of R is the domain of the converse of R.
The field of R is the union
of the domain and range of R.
The preimage of a member x of the field of R is the set
(used in the definition of "well-founded" below).
The downward closure of a member x of the field of R is the smallest set D containing x, and containing each zRy for each y∈D (i.e., including the preimage of each of its elements with respect to R as a subset).
The relative product of R and S, R|S, is the relation
.
In ZFC, proving that these notions are all sets follows from Union
, Separation, and Power Set
. In NFU
, it is easy to check that these definitions give rise to stratified formulas.
Notice that the range and codomain of a relation are not distinguished: this could be done by representing a relation R with codomain B as (R,B), but our development will not require this.
In ZFC, any relation whose domain is a subset of a set A and whose range is a subset of a set B will be a set, since the cartesian product
is a set (being a subclass of 
), and Separation provides for the existence of 
. In NFU
, some relations with global scope (such as equality and subset) can be implemented as sets. In NFU, bear in mind that x and y are three types lower than R in
(one type lower if a type-level ordered pair is used).
. R is:
Relations having certain combinations of the above properties have standard names. R is:
. Such a relation
(predicate) is implemented as a relation (set) exactly as described in the previous section. So the predicate F is implemented by the set
. A set of ordered pairs F is a function if and only if 
. Define F(x) as the unique object y such that xFy (if there is one) or as the unique object y such that (x,y) ∈ F. The presence in both theories of functional predicates which are not sets makes it useful to allow the notation F(x) both for sets F 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 NFU
, x has the same type as F(x), and F is three types higher than F(x) (one type higher, if a type-level ordered pair is used). For any set A, define
as 
, more conveniently written as 
. If A is a set and F is any functional relation, Replacement assures that 
is a set in ZFC. In NFU, 
and A have the same type, and F is two types higher than 
(the same type, if a type-level ordered pair is used).
The function I(x) = x is not a set in ZFC because it is "too large". I(x) is however, a set in NFU. The function (predicate)
is not a function (set) in either theory; in ZFC because it is too large; in NFU because its definition is unstratified. Moreover, S(x) can be proved not to exist in NFU: see the resolution of Cantor's paradox in New Foundations
.
of f and g,
, is defined as the relative product 
, if this results in a function: 
is a function, with 
, if the range of f is a subset of the domain of g. The inverse
of f, f-1, is defined as the converse
of f (if this is a function). Given any set A, the identity function
is the set 
: this is a set in both ZFC and NF
, but for different reasons.
and one-to-one if it has an inverse.
If f is a function from set A to set B, f is a:
This terminology adjusts for the fact that a function, as defined above, does not determine its codomain.
, two sets A and B are the same size (or are equinumerous) if and only if there is a bijection f from A to B. This can be written as
, but note that (for the moment) this expresses a relation between A and B rather than a relation between yet-undefined objects 
and 
. Denote this relation by 
in contexts such as the actual definition of the cardinals where even the appearance of presupposing abstract cardinals should be avoided.
Similarly, define
as holding if and only if there is an 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
; if f witnesses 
, then 
witnesses 
; if f witnesses 
and g witnesses 
, then 
witnesses 
.
It can be shown that
is a linear order on abstract cardinals, but not on sets. Reflexivity is obvious and transitivity is proven just as for equinumerousness. The Schroder-Bernstein theorem, provable in ZFC and NFU
in an entirely standard way, establishes that
(this establishes antisymmetry on cardinals), and
follows in a standard way in either theory from the axiom of choice.
becomes evident.
The Axiom of Infinity of ZFC tells us that there is a set A which contains
and contains 
for each 
. This set A is not uniquely determined (it can be made larger while preserving this closure property): the set N of natural numbers is
which is the intersection of all sets which contain the empty set and are closed under the "successor" operation
.
In ZFC, a set
is finite if and only if there is 
such that 
: further, define 
as this n for finite A. (It can be proved that no two distinct natural numbers are the same size).
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
for each natural number 
and contains 
whenever it contains 
.
In NFU, it is not obvious that this approach can be used, since the successor operation
is unstratified and so the set N as defined above cannot be shown to exist in NFU (it is interesting to note that it is consistent for the set of finite von Neumann ordinals to exist in NFU, but this strengthens the theory, as the existence of this set implies the Axiom of Counting (for which see below or the New Foundations
article)).
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 NFU
(this is not the usual definition, but the results are the same): define Fin, the set of finite sets, as
For any set
, define 
as 
. Define N as the set 
.
The Axiom of Infinity of NFU can be expressed as
: this is enough to establish that each natural number has a nonempty successor (the successor of 
being 
for any 
) which is the hard part of showing that the Peano axioms of arithmetic are satisfied.
The operations of arithmetic can be defined in a style similar to the style given above (using the definition of successor just given). They can also be defined in a natural set theoretical way: if A and B are disjoint finite sets, define |A|+|B| as
. More formally, define m+n for m and n in N as
(But note that this style of definition is feasible for the ZFC numerals as well, but more circuitous: the form of the 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 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.
as representing an abstraction from the set x respecting just those features (identify elements of A up to
R).
For any set A, a set
is a partition of A if all elements of P are nonempty, any two distinct elements of P are disjoint, and 
.
For every equivalence relation R with field A,
is a partition of A. Moreover, each partition P of A determines an equivalence relation 
.
This technique has limitations in both ZFC and NFU
. In ZFC, since the universe is not a set, it seems possible to abstract features only from elements of small domains. This can be circumvented using a trick due to Dana Scott
: if R is an equivalence relation on the universe, define
as the set of all y such that 
and the rank of y is less than or equal to the rank of any 
. This works because the ranks are sets. Of course, there still may be a proper class of 
's. In NFU, the main difficulty is that 
is one type higher than x, so for example the "map" 
is not in general a (set) function (though 
is a set). This can be circumvented by the use of the Axiom of Choice to select a representative from each equivalence class to replace 
, which will be at the same type as x, or by choosing a canonical representative if there is a way to do this without invoking Choice (the use of representatives is hardly unknown in ZFC, either). In NFU, the use of equivalence class constructions to abstract properties of general sets is more common, as for example in the definitions of cardinal and ordinal number below.
and 
are similar and write 
just in case there is a bijection f from the field of 
to the field of 
such that 
for all x and y.
Similarity is shown to be an equivalence relation in much the same way that equinumerousness was shown to be an equivalence relation above.
In 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 von Neumann is more commonly used.
For any partial order
, the corresponding strict partial order < is defined as 
. Strict linear orders and strict well-orderings are defined similarly.
A set A is said to be transitive if
: each element of an element of A is also an element of A. A (von Neumann) ordinal is a transitive set on which membership is a strict well-ordering.
In ZFC, the order type of a well-ordering W is then defined as the unique von Neumann ordinal which is equinumerous with the field of W and membership on which is isomorphic to the strict well-ordering associated with W. (the equinumerousness condition distinguishes between well-orderings with fields of size 0 and 1, whose associated strict well-orderings are indistinguishable).
In ZFC there cannot be a set of all ordinals. In fact, the von Neumann ordinals are an inconsistent totality in any set theory: it can be shown with modest set theoretical assumptions that every element of a von Neumann ordinal is a von Neumann ordinal and the von Neumann ordinals are strictly well-ordered by membership. It follows that the class of von Neumann ordinals would be a von Neumann ordinal if it were a set: but it would then be an element of itself, which contradicts that fact that membership is a strict well-ordering of the von Neumann ordinals.
It is worth noting that the existence of order types for all well-orderings is not a theorem of Zermelo set theory
: it requires the Axiom of replacement. Even Scott's trick cannot be used in Zermelo set theory
without an additional assumption (such as the assumption that every set belongs to a rank which is a set, which does not essentially
strengthen Zermelo set theory
but is not a theorem of that theory).
In NFU
, the collection of all ordinals is a set by stratified comprehension. The Burali-Forti paradox is evaded in an unexpected way. There is a natural order on the ordinals defined by
if and only if some (and so any) 
is similar to an initial segment of some (and so any) 
. Further, it can be shown that this natural order is a well-ordering of the ordinals and so must have an order type 
. It would seem that the order type of the ordinals less than
with the natural order would be 
, contradicting the fact that 
is the order type of the entire natural order on the ordinals (and so not of any of its proper initial segments). But this relies on our intuition (correct in ZFC) that the order type of the natural order on the ordinals less than 
is 
for any ordinal 
. This assertion is unstratified, because the type of the second 
is four higher than the type of the first (two higher if a type level pair is used). The assertion which is true and provable in NFU
is that the order type of the natural order on the ordinals less than
is 
for any ordinal 
, where 
is the order type of 
for any 
(it is easy to show that this does not depend on the choice of W; note that T raises type by one). Thus the order type of the ordinals less than 
with the natural order is 
, and 
. All uses of 
here can be replaced with 
if a type-level pair is used.
This shows that the T operation is nontrivial, which has a number of interesting consequences. It follows immediately that the singleton map
is not a set, as otherwise restrictions of this map would establish the similarity of W and 
for any
well-ordering W. T is (externally) bijective and order-preserving. Because of this, the fact
establishes that 
is a "descending sequence" in the ordinals which cannot be a set.
Ordinals fixed by T are called cantorian ordinals, and ordinals which dominate only cantorian ordinals (which are easily shown to be cantorian themselves) are said to be strongly cantorian. There can be no set of cantorian ordinals or set of strongly cantorian ordinals.
. Recall that a von Neumann ordinal is a transitive set A such that the restriction of membership to A is a strict well-ordering. This is quite a strong condition in the NFU context, since the membership relation involves a difference of type. A von Neumann ordinal A is not an ordinal in the sense of NFU, but
belongs to an ordinal 
which may be termed the order type of (membership on) A. It is easy to show that the order type of a von Neumann
ordinal A is cantorian: for any well-ordering W of order type
, the induced well-ordering of initial segments of W by inclusion has order type 
(it is one type higher, thus the application of T): but the order types of the well-ordering of a von Neumann ordinal A by membership and the well-ordering of its initial segments by inclusion are clearly the same because the two well-orderings are actually the same relation, so the order type of A is fixed under T. Moreover, the same argument applies to any smaller ordinal (which will be the order type of an initial segment of A, also a von Neumann ordinal) so the order type of any von Neumann ordinal is strongly cantorian!
The only von Neumann ordinals which can be shown to exist in NFU without additional assumptions are the concrete finite ones. However, the application of a permutation method can convert any model of NFU to a model in which every strongly cantorian ordinal is the order type of a von Neumann ordinal. This suggests that the concept "strongly cantorian ordinal of NFU" might be a better
analogue to "ordinal of ZFC" than is the apparent analogue "ordinal of NFU".
in a way which generalizes the definition of natural
number: for any set A,
.
In ZFC, these equivalence classes are too large as usual. Scott's trick could be used (and indeed is used in ZF
),
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
the Axiom of Choice in the usual way in both theories).
The natural order on cardinal numbers is seen to be a well-ordering: that it is reflexive, antisymmetric (on abstract cardinals, which are now available) and transitive has been shown above. That it is a linear order follows from the Axiom of Choice: well-order two sets and an
initial segment of one well-ordering will be isomorphic to the other, so one set will have cardinality smaller than that of the other. That it is a well-ordering follows from the Axiom of Choice in a similar way.
With each infinite cardinal, many order types are associated for the usual reasons (in either set theory).
Cantor's theorem shows (in both theories) that there are nontrivial distinctions between infinite cardinal numbers. In ZFC, one proves
In 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 NFU
is
, where 
is the set of one-element subsets of A. 
shows that there are "fewer" singletons than sets (the obvious bijection 
from 
to V has already been seen not to be a set). It is actually provable in NFU + Choice that 
(where << 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: 
; 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 cantorian just in case
; the cardinal 
is also said to be a cantorian cardinal. A set A is said to be strongly cantorian (and its cardinal to be strongly cantorian as well) just in case the restriction of the singleton map to A (
) is a set. Well-orderings of strongly cantorian sets are always strongly cantorian ordinals; this is not always true of well-orderings of cantorian sets (though the shortest well-ordering of a cantorian set will be cantorian). A cantorian set is a set which satisfies the usual form of Cantor's theorem.
The operations of cardinal arithmetic are defined in a set-theoretically motivated way in both theories.
. One would like to define 
as 
, and one does this in ZFC, but there is an obstruction in NFU
when using the Kuratowski pair: one defines
as 
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).
Defining the exponential operation on cardinals requires T in an essential way: if
was defined as the collection of functions from A to B, this is three types higher than A or B, so it is reasonable to define 
as 
so that it is the same type as A or B (
replaces 
with type-level pairs). An effect of this is that the exponential operation is partial: for example, 
is undefined. In ZFC one defines 
as 
without difficulty.
The exponential operation is total and behaves exactly as expected on cantorian cardinals, since T fixes such cardinals and it is easy to show that a function space between cantorian sets is cantorian (as are power sets, cartesian products, and other usual type constructors). This offers further encouragement to the view that the "standard" cardinalities in NFU
are the cantorian (indeed, the strongly cantorian) cardinalities, just as the "standard" ordinals seem to be the strongly cantorian ordinals.
Now the usual theorems of cardinal arithmetic with the axiom of choice can be proved, including
. From the case 
the existence of a type level ordered pair can be derived: 
is equal to 
just in case 
, which would be witnessed by a one-to-one correspondence between Kuratowski pairs 
and double singletons 
: redefine 
as the c such that 
is associated with the Kuratowski 
: this is a type-level notion of ordered pair.
(though they are the same in ZFC): finite ordinals and finite cardinals. Each of these supports a T operation in NFU
(basically the same operation). It is easy to prove that
is a natural number if n is a natural number in NFU
+ Infinity + Choice (and so
and the first
infinite ordinal
are cantorian) but it is not possible to prove in this theory that 
. However, common sense indicates that this should be true, and so it can be adopted as an axiom:
One natural consequence of this axiom (and indeed its original formulation) is
All that can be proved in NFU
without Counting is
.
A consequence of Counting is that N is a strongly cantorian set (again, this is an equivalent assertion).
with references to 
(type of a raised; this presupposes that it is known that a is a set; otherwise one must say "the element of 
" to get this effect) or 
(type of a lowered) where 
for all 
, so it is not necessary to assign types to such variables for purposes of stratification.
Any subset of a strongly cantorian set is strongly cantorian. The power set of a strongly cantorian set is strongly cantorian. The cartesian product of two strongly cantorian sets is strongly cantorian.
Introducing the Axiom of Counting means that types need not be assigned to variables restricted to N or to P(N), R (the set of reals) or indeed any set ever considered in classical mathematics outside of set theory.
There are no analogous phenomena in ZFC. See the main New Foundations
article for stronger axioms that can be adjoined to NFU to enforce "standard" behavior of familiar mathematical objects.
is represented by the pair 
. To make 
, introduce the relation 
defined by 
. It is provable that this is an equivalence relation: define positive rational numbers as equivalence classes of pairs of positive natural numbers under this relation. Arithmetic operations on positive rational numbers and the order relation on positive rationals are defined just as in elementary school and proved (with some effort) to have the expected properties.
Represent magnitudes (positive reals) as nonempty proper initial segments of the positive rationals with no largest element. The operations of addition and multiplication on magnitudes are implemented by elementwise addition of the positive rational elements of the magnitudes. Order is implemented as set inclusion.
Represent real numbers as differences
of magnitudes: formally speaking, a real number is an equivalence class of pairs 
of magnitudes under the equivalence relation 
defined by 
. The operations of addition and multiplication on real numbers are defined just as one would expect from the algebraic rules for adding and multiplying differences. The treatment of order is also as in elementary algebra.
This is the briefest sketch of the constructions. Note that the constructions are exactly the same in ZFC and in NFU
, except for the difference in the constructions of the natural numbers: since all variables are restricted to strongly cantorian sets, there is no need to worry about stratification restrictions. Without the Axiom of Counting, it might be necessary to introduce some applications of T in a full discussion of these constructions.
: though the constructions are clearly feasible in 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
as 
. The definition of the general n-tuple using the Kuratowski pair is trickier, as one needs to keep the types of all the projections the same, and the type displacement between the n-tuple and its projections increases as n increases. Here, the n-tuple has the same type as each of its projections.
General cartesian products are defined similarly:
The definitions are the same in ZFC but without any worries about stratification (the grouping given here is opposite to that more usually used, but this is easily corrected for).
Now consider the infinite cartesian product
. In ZFC, this is defined as the set of all functions f with domain I such that 
(where A is implicitly understood as a function taking each i to 
).
In NFU, this is requires attention to type. Given a set I and set valued function A whose value at
in 
is written 
, Define 
as the set of all functions f with domain I such that 
: notice that 
is stratified because of our convention that A is a function with values at singletons of the indices. Note that the very largest families of sets (which cannot be indexed by sets of singletons) will not have cartesian products under this definition. Note further that the sets 
are at the same type as the index set I (since one type higher than its elements); the product, as a set of functions with domain I (so at the same type as I) is one type higher (assuming a type-level ordered pair).
Now consider the product
of the cardinals of these sets. The cardinality |
| is one type higher than the cardinals 
, so the correct definition of the infinite product of cardinals is 
(because the inverse of T is not total, it is possible that this may not exist).
Repeat this for disjoint unions of families of sets and sums of families of cardinals. Again, let A be a set-valued function with domain
: write 
for 
. The disjoint union 
is the set 
. This set is at the same type as the sets 
.
The correct definition of the sum
is thus 
, since there is no type displacement.
It is possible to extend these definitions to handle index sets which are not sets of singletons, but this introduces an additional type level and is not needed for most purposes.
In ZFC, define the disjoint union
as 
, where 
abbreviates 
.
Permutation methods can be used to show relative consistency with NFU of the assertion that for every strongly cantorian set A there is a set I of the same size whose elements are self-singletons:
for each i in I.
; 
; 
for limit ordinals 
. This is an example of a construction by transfinite recursion. The rank of a set A is said to be 
if and only if 
. The existence of the ranks as sets depends on the axiom of replacement at each limit step (the hierarchy cannot be constructed in Zermelo set theory
); by the axiom of foundation, every set belongs to some rank.
The cardinal
is called 
.
This construction cannot be carried out in NFU
because the power set operation is not a set function in NFU
(
is one type higher than A for purposes of stratification).
The sequence of cardinals
can be implemented in NFU. Recall that 
is defined as 
, where 
is a convenient set of size 2, and 
. Let 
be the smallest set of cardinals which contains 
(the cardinality of the set of natural numbers), contains the cardinal 
whenever it contains 
, and which is closed under suprema of sets of cardinals.
A convention for ordinal indexing of any well-ordering
is defined as the element x of the field of 
such that
the order type of the restriction of
to 
is 
; then define 
as the element with index 
in the natural order on the elements of 
. The cardinal 
is the element with index 
in the natural order on all infinite cardinals (which is a well-ordering, see above). Note that 
follows immediately from this definition. In all these constructions, notice that the type of the index 
is two higher (with type-level ordered pair) than the type of 
.
Each set A of ZFC has a transitive closure
(the intersection of all transitive sets which contains A). By the axiom of foundation, the restriction of the membership relation to the transitive closure of A is a well-founded relation
. The relation
is either empty or has A as its top element, so this relation is a set picture. It can be proved in ZFC that every set picture is isomorphic to some 
.
This suggests that (an initial segment of) the cumulative hierarchy can be studied by considering the isomorphism classes of set pictures. These isomorphism classes are sets and make up a set in NFU
. There is a natural set relation analogous to membership on isomorphism classes of set pictures: if
is a set picture, write 
for its isomorphism class and define 
as holding if 
is the isomorphism class of the restriction of y to the downward closure of one of the elements of the preimage under y of the top element of y. The relation E is a set relation, and it is straightforward to prove that it is well-founded and extensional. If the definition of E is confusing, it can be deduced from the observation that it is induced by precisely the relationship which holds between the set picture associated with A and the set picture associated with B when 
in the usual set theory.
There is a T operation on isomorphism classes of set pictures analogous to the T operation on ordinals: if x is a set picture, so is
. Define 
as 
. It is easy to see that 
.
An axiom of extensionality for this simulated set theory follows from E's extensionality. From its well-foundedness follows an axiom of foundation. There remains the question of what comprehension axiom E may have. Consider any collection of set pictures
(collection of set pictures whose fields are made up entirely of singletons). Since each 
is one type higher than x (using a type-level ordered pair), replacing each element 
of the field of each 
in the collection with 
results in a collection of set pictures isomorphic to the original collection but with their fields disjoint. The union of these set
pictures with a new top element yields a set picture whose isomorphism type will have as its preimages under E exactly the elements of the original collection. That is, for any collection of isomorphism types
, there is an isomorphism type 
whose preimage under E is exactly this collection.
In particular, there will be an isomorphism type [v] whose preimage under E is the collection of all T[x]s (including T[v]). Since T[v] E v and E is well-founded,
. This resembles the resolution of the Burali-Forti paradox discussed above and in the New Foundations
article, and is in fact the local resolution of Mirimanoff's paradox of the set of all well-founded sets.
There are ranks of isomorphism classes of set pictures just as there are ranks of sets in the usual set theory. For any collection of set pictures A, define S(A) as the set of all isomorphism classes of set pictures whose preimage under E is a subset of A; call A a "complete" set if every subset of A is a preimage under E. The collection of "ranks" is the smallest collection containing the empty set and closed under the S operation (which is a kind of power set construction) and under unions of its subcollections. It is straightforward to prove (much as in the usual set theory) that the ranks are well-ordered by inclusion, and so the ranks have an index in this well-order: refer to the rank with index
as 
. It is provable that 
for complete ranks 
. The union of the complete ranks (which will be the first incomplete rank) with the relation E looks like an initial segment of the universe of Zermelo-style set theory (not necessarily like the full universe of ZFC because it may not be large enough). It is provable that if 
is the first incomplete rank, then 
is a complete rank and thus 
. So there is a "rank of the cumulative hierarchy" with an "external automorphism" T moving the rank downward, exactly the condition on a nonstandard model of a rank in the cumulative hierarchy under which a model of NFU is constructed in the New Foundations
article. There are technical details to verify, but there is an interpretation not only of a fragment of ZFC but of NFU
itself in this structure, with
defined as 
: this "relation" 
is not a set relation but has the same type displacement between its arguments as the usual membership relation 
.
So there is a natural construction inside NFU of the cumulative hierarchy of sets which internalizes the natural construction of a model of NFU in Zermelo-style set theory.
Under the Axiom of Cantorian Sets described in the New Foundations
article, the strongly cantorian part of the set of isomorphism classes of set pictures with the E relation as membership becomes a (proper class) model of ZFC (in which there are n-Mahlo cardinals for each n; this extension of NFU is strictly stronger than ZFC). This is a proper class model because the strongly cantorian isomorphism classes do not make up a set.
Permutation methods can be used to create from any model of NFU a model in which every strongly cantorian isomorphism type of set pictures is actually realized as the restriction of the true membership relation to the transitive closure of a set.
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
. The implementation of a number of basic mathematical concepts is carried out in parallel in ZFC (the dominant set theory) and in NFU
New Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
, the version of Quine's New Foundations
New Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
shown to be consistent by R. B. Jensen in 1969 (here understood to include at least axioms of Infinity and 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
Zermelo set theory
Zermelo set theory, as set out in an important paper in 1908 by Ernst Zermelo, is the ancestor of modern set theory. It bears certain differences from its descendants, which are not always understood, and are frequently misquoted...
near the lower end of the scale and going up to ZFC extended with large cardinal
Large cardinal property
In the mathematical field of set theory, a large cardinal property is a certain kind of property of transfinite cardinal numbers. Cardinals with such properties are, as the name suggests, generally very "large"...
hypotheses such as "there is a measurable cardinal
Measurable cardinal
- Measurable :Formally, a measurable cardinal is an uncountable cardinal number κ such that there exists a κ-additive, non-trivial, 0-1-valued measure on the power set of κ...
"; and on the other hand a hierarchy of extensions of NFU which is surveyed in the New Foundations
New Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
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.
It is not the primary aim of this article to say anything about the relative merits of these theories as foundations for mathematics. The reason for the use of two different set theories is to illustrate that multiple approaches to the implementation of mathematics are feasible. Precisely because of this approach, this article is not a source of "official" definitions for any mathematical concept.
Preliminaries
The following sections carry out certain constructions in the two theories ZFC and NFUNew Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
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
exists", where is a formula of our language: the theory proves the existence of "the x such that " just in case it is a theorem that "there is one and only one x such that ". (See Bertrand RussellBertrand Russell
Bertrand Arthur William Russell, 3rd Earl Russell, OM, FRS was a British philosopher, logician, mathematician, historian, and social critic. At various points in his life he considered himself a liberal, a socialist, and a pacifist, but he also admitted that he had never been any of these things...
's theory of descriptions
Theory of descriptions
The theory of descriptions is the philosopher Bertrand Russell's most significant contribution to the philosophy of language. It is also known as Russell's Theory of Descriptions...
.) Loosely, the theory "defines" or "constructs" this object in this case. If the statement is not a theorem, the theory cannot show that the object exists; if the statement is provably false in the theory, it proves that the object cannot exist; loosely, the object cannot be constructed.
ZFC and NFU share the language of set theory, so the same formal definitions "the x such that
" can be contemplated in the two theories. A specific form of definition in the language of set theory is set-builder notation: means "the set A such that for all x, " (A cannot be free in ). This notation admits certain conventional extensions: is synonymous with ; is defined as , where 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
fails to refer to anything in any set theory with classical logic; in class theories like NBGVon Neumann–Bernays–Gödel set theory
In the foundations of mathematics, von Neumann–Bernays–Gödel set theory is an axiomatic set theory that is a conservative extension of the canonical axiomatic set theory ZFC. A statement in the language of ZFC is provable in NBG if and only if it is provable in ZFC. The ontology of NBG includes...
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
in ZFC is not suitable for NFU because the object (defined in purely set theoretical language as the set of all finite von Neumann ordinals) cannot be shown to exist in NFU. The usual definition of in NFU is (in purely set theoretical language) as the set of all infinite well-orderings all of whose proper initial segments are finite, an object which can be shown not to exist in ZFC. In the case of such imported objects, there may be different definitions, one for use in ZFC and related theories, and one for use in NFU and related theories. For such "implementations" of imported mathematical concepts to make sense, it is necessary to be able to show that the two parallel interpretations have the expected properties: for example, the implementations of the natural numbers in ZFC and NFU are different, but both are implementations of the same mathematical structure, because both include definitions for all the primitives of Peano arithmetic and satisfy (the translations of) the Peano axioms. It is then possible to compare what happens in the two theories as when only set theoretical language is in use, as long as the definitions appropriate to ZFC are understood to be used in the ZFC context and the definitions appropriate to NFU are understood to be used in the NFU context.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
Zermelo set theory
Zermelo set theory, as set out in an important paper in 1908 by Ernst Zermelo, is the ancestor of modern set theory. It bears certain differences from its descendants, which are not always understood, and are frequently misquoted...
instead of ZFC for much of what is done in this article, for example).
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!)
The empty set is the unique set with no members. In NFU, there are also urelements with no members.
For each object x, there is a set
with x as its only element.
For objects x and y, there is a set
containing x and y as its only elements.
The union of two sets is defined in the usual way.
This is a recursive definition of unordered n-tuples for any concrete n (finite sets given as lists of their elements).
In NFU
New Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
, all the set definitions given work by stratified comprehension; in ZFC, the existence of the unordered pair is given by the axiom of Pairing, the existence of the empty set follows by Separation from the existence of any set, and the boolean union of two sets exists by the axioms of Pairing and Union (
).Ordered pair
First, consider the ordered pair. The reason that this comes first is technical: ordered pairs are needed to implement relationsRelation (mathematics)
In set theory and logic, a relation is a property that assigns truth values to k-tuples of individuals. Typically, the property describes a possible connection between the components of a k-tuple...
and functions
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
which are needed to implementat other concepts which may seem to be prior.
The first definition of the ordered pair was the definition
proposed by Norbert WienerNorbert Wiener
Norbert Wiener was an American mathematician.A famous child prodigy, Wiener later became an early researcher in stochastic and noise processes, contributing work relevant to electronic engineering, electronic communication, and control systems.Wiener is regarded as the originator of cybernetics, a...
in 1914 in the context of the type theory of Principia Mathematica
Principia Mathematica
The Principia Mathematica is a three-volume work on the foundations of mathematics, written by Alfred North Whitehead and Bertrand Russell and published in 1910, 1912, and 1913...
. Wiener observed that this allowed the elimination of types of n-ary relations for
from the system of that work.It is more usual now to use the definition
, due to Kuratowski.Either of these definitions works in either ZFC or NFU
New Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
. In NFU, the Kuratowski pair has a technical disadvantage: it is two types higher than its projections. It is common to postulate the existence of a type-level ordered pair (a pair
which is the same type as its projections) in NFU. It is convenient to use the Kuratowski pair in both systems until the use of type-level pairs can be formally justified.The internal details of these definitions have nothing to do with their actual mathematical function. For any notion
of ordered pair, the things that matter are that it satisfy the defining condition
and that it be reasonably easy to collect ordered pairs into sets.
Relations
RelationsRelation (mathematics)
In set theory and logic, a relation is a property that assigns truth values to k-tuples of individuals. Typically, the property describes a possible connection between the components of a k-tuple...
are sets whose members are all ordered pair
Ordered pair
In mathematics, an ordered pair is a pair of mathematical objects. In the ordered pair , the object a is called the first entry, and the object b the second entry of the pair...
s. Where possible, a relation R (understood as a binary predicate) is implemented as
(which may be written as ). Where R is a set of ordered pairs, read xRy as (x,y)∈R.In ZFC, some relations (such as the general equality relation or subset relation on sets) are "too large"
to be sets (but may be harmlessly reified as proper classes). In NFU
New Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
, some relations (such as the membership relation) are not sets because their definitions are not stratified: in
x and y wouldneed to have the same type (because they appear as projections of the same pair), but also
successive types (because x is considered as an element of y).
Related definitions
Let R and S be given binary relationBinary relation
In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...
s. Then the following concepts are useful:
The converse
Inverse relation
In mathematics, the inverse relation of a binary relation is the relation that occurs when you switch the order of the elements in the relation. For example, the inverse of the relation 'child of' is the relation 'parent of'...
of R is the relation
.The domain of R is the set
.The range of R is the domain of the converse of R.
The field of R is the union
Union (set theory)
In set theory, the union of a collection of sets is the set of all distinct elements in the collection. The union of a collection of sets S_1, S_2, S_3, \dots , S_n\,\! gives a set S_1 \cup S_2 \cup S_3 \cup \dots \cup S_n.- Definition :...
of the domain and range of R.
The preimage of a member x of the field of R is the set
(used in the definition of "well-founded" below).The downward closure of a member x of the field of R is the smallest set D containing x, and containing each zRy for each y∈D (i.e., including the preimage of each of its elements with respect to R as a subset).
The relative product of R and S, R|S, is the relation
.In ZFC, proving that these notions are all sets follows from Union
Axiom of union
In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom of union is one of the axioms of Zermelo-Fraenkel set theory, stating that, for any set x there is a set y whose elements are precisely the elements of the elements of x...
, Separation, and Power Set
Axiom of power set
In mathematics, the axiom of power set is one of the Zermelo–Fraenkel axioms of axiomatic set theory.In the formal language of the Zermelo–Fraenkel axioms, the axiom reads:...
. In NFU
New Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
, it is easy to check that these definitions give rise to stratified formulas.
Notice that the range and codomain of a relation are not distinguished: this could be done by representing a relation R with codomain B as (R,B), but our development will not require this.
In ZFC, any relation whose domain is a subset of a set A and whose range is a subset of a set B will be a set, since the cartesian product
Cartesian product
In mathematics, a Cartesian product is a construction to build a new set out of a number of given sets. Each member of the Cartesian product corresponds to the selection of one element each in every one of those sets...
is a set (being a subclass of ), and Separation provides for the existence of . In NFUNew Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
, some relations with global scope (such as equality and subset) can be implemented as sets. In NFU, bear in mind that x and y are three types lower than R in
(one type lower if a type-level ordered pair is used).Properties and kinds of relations
Let R be some binary relationBinary relation
In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...
. R is:
- ReflexiveReflexive relationIn mathematics, a reflexive relation is a binary relation on a set for which every element is related to itself, i.e., a relation ~ on S where x~x holds true for every x in S. For example, ~ could be "is equal to".-Related terms:...
if
.
- SymmetricSymmetric relationIn mathematics, a binary relation R over a set X is symmetric if it holds for all a and b in X that if a is related to b then b is related to a.In mathematical notation, this is:...
if
.
- TransitiveTransitive relationIn mathematics, a binary relation R over a set X is transitive if whenever an element a is related to an element b, and b is in turn related to an element c, then a is also related to c....
if
.
- AntisymmetricAntisymmetric relationIn mathematics, a binary relation R on a set X is antisymmetric if, for all a and b in Xor, equivalently,In mathematical notation, this is:\forall a, b \in X,\ R \and R \; \Rightarrow \; a = bor, equivalently,...
if
.
- Well-foundedWell-founded relationIn mathematics, a binary relation, R, is well-founded on a class X if and only if every non-empty subset of X has a minimal element with respect to R; that is, for every non-empty subset S of X, there is an element m of S such that for every element s of S, the pair is not in R:\forall S...
if for every set S which meets the field of R,
whose preimage under R does not meet S.
- 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.
Relations having certain combinations of the above properties have standard names. R is:
- An equivalence relationEquivalence relationIn mathematics, an equivalence relation is a relation that, loosely speaking, partitions a set so that every element of the set is a member of one and only one cell of the partition. Two elements of the set are considered equivalent if and only if they are elements of the same cell...
if and only ifIf and only ifIn logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
R is reflexive, symmetric, and transitive.
- A partial order if and only if R is reflexive, antisymmetric, and transitive.
- A linear order if and only if R is a partial order and for every x,y in the field of R, either xRy or yRx.
- A well-ordering if and only if R is a linear order and well-founded.
- A set picture if and only 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 functional relation is a binary predicate F such that. Such a relationRelation (mathematics)
In set theory and logic, a relation is a property that assigns truth values to k-tuples of individuals. Typically, the property describes a possible connection between the components of a k-tuple...
(predicate) is implemented as a relation (set) exactly as described in the previous section. So the predicate F is implemented by the set
. A set of ordered pairs F is a function if and only if . Define F(x) as the unique object y such that xFy (if there is one) or as the unique object y such that (x,y) ∈ F. The presence in both theories of functional predicates which are not sets makes it useful to allow the notation F(x) both for sets F 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 NFU
New Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
, x has the same type as F(x), and F is three types higher than F(x) (one type higher, if a type-level ordered pair is used). For any set A, define
as , more conveniently written as . If A is a set and F is any functional relation, Replacement assures that is a set in ZFC. In NFU, and A have the same type, and F is two types higher than (the same type, if a type-level ordered pair is used).The function I(x) = x is not a set in ZFC because it is "too large". I(x) is however, a set in NFU. The function (predicate)
is not a function (set) in either theory; in ZFC because it is too large; in NFU because its definition is unstratified. Moreover, S(x) can be proved not to exist in NFU: see the resolution of Cantor's paradox in New FoundationsNew Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
.
Operations on functions
Let f and g be arbitrary functions. The compositionFunction composition
In mathematics, function composition is the application of one function to the results of another. For instance, the functions and can be composed by computing the output of g when it has an argument of f instead of x...
of f and g,
, is defined as the relative product , if this results in a function: is a function, with , if the range of f is a subset of the domain of g. The inverseInverse function
In mathematics, an inverse function is a function that undoes another function: If an input x into the function ƒ produces an output y, then putting y into the inverse function g produces the output x, and vice versa. i.e., ƒ=y, and g=x...
of f, f-1, is defined as the converse
Inverse relation
In mathematics, the inverse relation of a binary relation is the relation that occurs when you switch the order of the elements in the relation. For example, the inverse of the relation 'child of' is the relation 'parent of'...
of f (if this is a function). Given any set A, the identity function
is the set : this is a set in both ZFC and NFNew Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
, but for different reasons.
Special kinds of function
A function is an injectionInjective function
In mathematics, an injective function is a function that preserves distinctness: it never maps distinct elements of its domain to the same element of its codomain. In other words, every element of the function's codomain is mapped to by at most one element of its domain...
and one-to-one if it has an inverse.
If f is a function from set A to set B, f is a:
- InjectionInjective functionIn mathematics, an injective function is a function that preserves distinctness: it never maps distinct elements of its domain to the same element of its codomain. In other words, every element of the function's codomain is mapped to by at most one element of its domain...
if the domain of f is A and the range of f is a subset of B. In other words, the imageImageAn image is an artifact, for example a two-dimensional picture, that has a similar appearance to some subject—usually a physical object or a person.-Characteristics:...
s under f of distinct members of A are distinct members of B. - Surjection if f has domain A and range B.
- BijectionBijectionA bijection is a function giving an exact pairing of the elements of two sets. A bijection from the set X to the set Y has an inverse function from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements...
if f is both an injection and a surjection.
This terminology adjusts for the fact that a function, as defined above, does not determine its codomain.
Size of sets
In both ZFC and NFUNew Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
, two sets A and B are the same size (or are equinumerous) if and only if there is a bijection f from A to B. This can be written as
, but note that (for the moment) this expresses a relation between A and B rather than a relation between yet-undefined objects and . Denote this relation by in contexts such as the actual definition of the cardinals where even the appearance of presupposing abstract cardinals should be avoided.Similarly, define
as holding if and only if there is an injectionInjective function
In mathematics, an injective function is a function that preserves distinctness: it never maps distinct elements of its domain to the same element of its codomain. In other words, every element of the function's codomain is mapped to by at most one element of its domain...
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
; if f witnesses , then witnesses ; if f witnesses and g witnesses , then witnesses .It can be shown that
is a linear order on abstract cardinals, but not on sets. Reflexivity is obvious and transitivity is proven just as for equinumerousness. The Schroder-Bernstein theorem, provable in ZFC and NFUNew Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
in an entirely standard way, establishes that
(this establishes antisymmetry on cardinals), and
follows in a standard way in either theory from the axiom of choice.
Finite sets and natural numbers
Natural numbers can be considered either as finite ordinals or finite cardinals. Here consider them as finite cardinal numbers. This is the first place where a major difference between the implementations in ZFC and NFUNew Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
becomes evident.
The Axiom of Infinity of ZFC tells us that there is a set A which contains
and contains for each . This set A is not uniquely determined (it can be made larger while preserving this closure property): the set N of natural numbers is
which is the intersection of all sets which contain the empty set and are closed under the "successor" operation
.In ZFC, a set
is finite if and only if there is such that : further, define as this n for finite A. (It can be proved that no two distinct natural numbers are the same size).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
for each natural number and contains whenever it contains .In NFU, it is not obvious that this approach can be used, since the successor operation
is unstratified and so the set N as defined above cannot be shown to exist in NFU (it is interesting to note that it is consistent for the set of finite von Neumann ordinals to exist in NFU, but this strengthens the theory, as the existence of this set implies the Axiom of Counting (for which see below or the New FoundationsNew Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
article)).
The standard definition of the natural numbers, which is actually the oldest set-theoretic definition of natural numbers
Set-theoretic definition of natural numbers
Several ways have been proposed to define the natural numbers using set theory.- The contemporary standard :In standard, Zermelo-Fraenkel set theory the natural numbers...
, is as equivalence classes of finite sets under equinumerousness. Essentially the same definition is appropriate to NFU
New Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
(this is not the usual definition, but the results are the same): define Fin, the set of finite sets, as
For any set
, define as . Define N as the set .The Axiom of Infinity of NFU can be expressed as
: this is enough to establish that each natural number has a nonempty successor (the successor of being for any ) which is the hard part of showing that the Peano axioms of arithmetic are satisfied.The operations of arithmetic can be defined in a style similar to the style given above (using the definition of successor just given). They can also be defined in a natural set theoretical way: if A and B are disjoint finite sets, define |A|+|B| as
. More formally, define m+n for m and n in N as(But note that this style of definition is feasible for the ZFC numerals as well, but more circuitous: the form of the NFU
New Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
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 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
A general technique for implementing abstractions in set theory is the use of equivalence classes. If an equivalence relation R tells us that elements of its field A are alike in some particular respect, then for any set x, regard the set as representing an abstraction from the set x respecting just those features (identify elements of A up toUp to
In mathematics, the phrase "up to x" means "disregarding a possible difference in x".For instance, when calculating an indefinite integral, one could say that the solution is f "up to addition by a constant," meaning it differs from f, if at all, only by some constant.It indicates that...
R).
For any set A, a set
is a partition of A if all elements of P are nonempty, any two distinct elements of P are disjoint, and .For every equivalence relation R with field A,
is a partition of A. Moreover, each partition P of A determines an equivalence relation .This technique has limitations in both ZFC and NFU
New Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
. In ZFC, since the universe is not a set, it seems possible to abstract features only from elements of small domains. This can be circumvented using a trick due to Dana Scott
Dana Scott
Dana Stewart Scott is the emeritus Hillman University Professor of Computer Science, Philosophy, and Mathematical Logic at Carnegie Mellon University; he is now retired and lives in Berkeley, California...
: if R is an equivalence relation on the universe, define
as the set of all y such that and the rank of y is less than or equal to the rank of any . This works because the ranks are sets. Of course, there still may be a proper class of 's. In NFU, the main difficulty is that is one type higher than x, so for example the "map" is not in general a (set) function (though is a set). This can be circumvented by the use of the Axiom of Choice to select a representative from each equivalence class to replace , which will be at the same type as x, or by choosing a canonical representative if there is a way to do this without invoking Choice (the use of representatives is hardly unknown in ZFC, either). In NFU, the use of equivalence class constructions to abstract properties of general sets is more common, as for example in the definitions of cardinal and ordinal number below.Ordinal numbers
Two well-orderings and are similar and write just in case there is a bijection f from the field of to the field of such that for all x and y.Similarity is shown to be an equivalence relation in much the same way that equinumerousness was shown to be an equivalence relation above.
In NFU
New Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
, 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
Scott's trick
In set theory, Scott's trick is a method for choosing sets of representatives for equivalence classes without using the axiom of choice, if the axiom of regularity is available . It can be used to define representatives for ordinal numbers in Zermelo–Fraenkel set theory...
to define the ordinals in essentially the same way, but a device of von Neumann is more commonly used.
For any partial order
, the corresponding strict partial order < is defined as . Strict linear orders and strict well-orderings are defined similarly.A set A is said to be transitive if
: each element of an element of A is also an element of A. A (von Neumann) ordinal is a transitive set on which membership is a strict well-ordering.In ZFC, the order type of a well-ordering W is then defined as the unique von Neumann ordinal which is equinumerous with the field of W and membership on which is isomorphic to the strict well-ordering associated with W. (the equinumerousness condition distinguishes between well-orderings with fields of size 0 and 1, whose associated strict well-orderings are indistinguishable).
In ZFC there cannot be a set of all ordinals. In fact, the von Neumann ordinals are an inconsistent totality in any set theory: it can be shown with modest set theoretical assumptions that every element of a von Neumann ordinal is a von Neumann ordinal and the von Neumann ordinals are strictly well-ordered by membership. It follows that the class of von Neumann ordinals would be a von Neumann ordinal if it were a set: but it would then be an element of itself, which contradicts that fact that membership is a strict well-ordering of the von Neumann ordinals.
It is worth noting that the existence of order types for all well-orderings is not a theorem of Zermelo set theory
Zermelo set theory
Zermelo set theory, as set out in an important paper in 1908 by Ernst Zermelo, is the ancestor of modern set theory. It bears certain differences from its descendants, which are not always understood, and are frequently misquoted...
: it requires the Axiom of replacement. Even Scott's trick cannot be used in Zermelo set theory
Zermelo set theory
Zermelo set theory, as set out in an important paper in 1908 by Ernst Zermelo, is the ancestor of modern set theory. It bears certain differences from its descendants, which are not always understood, and are frequently misquoted...
without an additional assumption (such as the assumption that every set belongs to a rank which is a set, which does not essentially
strengthen Zermelo set theory
Zermelo set theory
Zermelo set theory, as set out in an important paper in 1908 by Ernst Zermelo, is the ancestor of modern set theory. It bears certain differences from its descendants, which are not always understood, and are frequently misquoted...
but is not a theorem of that theory).
In NFU
New Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
, the collection of all ordinals is a set by stratified comprehension. The Burali-Forti paradox is evaded in an unexpected way. There is a natural order on the ordinals defined by
if and only if some (and so any) is similar to an initial segment of some (and so any) . Further, it can be shown that this natural order is a well-ordering of the ordinals and so must have an order type . It would seem that the order type of the ordinals less than with the natural order would be , contradicting the fact that is the order type of the entire natural order on the ordinals (and so not of any of its proper initial segments). But this relies on our intuition (correct in ZFC) that the order type of the natural order on the ordinals less than is for any ordinal . This assertion is unstratified, because the type of the second is four higher than the type of the first (two higher if a type level pair is used). The assertion which is true and provable in NFUNew Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
is that the order type of the natural order on the ordinals less than
is for any ordinal , where is the order type of for any (it is easy to show that this does not depend on the choice of W; note that T raises type by one). Thus the order type of the ordinals less than with the natural order is , and . All uses of here can be replaced with if a type-level pair is used.This shows that the T operation is nontrivial, which has a number of interesting consequences. It follows immediately that the singleton map
is not a set, as otherwise restrictions of this map would establish the similarity of W and for anywell-ordering W. T is (externally) bijective and order-preserving. Because of this, the fact
establishes that is a "descending sequence" in the ordinals which cannot be a set.Ordinals fixed by T are called cantorian ordinals, and ordinals which dominate only cantorian ordinals (which are easily shown to be cantorian themselves) are said to be strongly cantorian. There can be no set of cantorian ordinals or set of strongly cantorian ordinals.
Digression: von Neumann ordinals in NFU
It is possible to reason about von Neumann ordinals in NFUNew Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
. Recall that a von Neumann ordinal is a transitive set A such that the restriction of membership to A is a strict well-ordering. This is quite a strong condition in the NFU context, since the membership relation involves a difference of type. A von Neumann ordinal A is not an ordinal in the sense of NFU, but
belongs to an ordinal which may be termed the order type of (membership on) A. It is easy to show that the order type of a von Neumannordinal A is cantorian: for any well-ordering W of order type
, the induced well-ordering of initial segments of W by inclusion has order type (it is one type higher, thus the application of T): but the order types of the well-ordering of a von Neumann ordinal A by membership and the well-ordering of its initial segments by inclusion are clearly the same because the two well-orderings are actually the same relation, so the order type of A is fixed under T. Moreover, the same argument applies to any smaller ordinal (which will be the order type of an initial segment of A, also a von Neumann ordinal) so the order type of any von Neumann ordinal is strongly cantorian!The only von Neumann ordinals which can be shown to exist in NFU without additional assumptions are the concrete finite ones. However, the application of a permutation method can convert any model of NFU to a model in which every strongly cantorian ordinal is the order type of a von Neumann ordinal. This suggests that the concept "strongly cantorian ordinal of NFU" might be a better
analogue to "ordinal of ZFC" than is the apparent analogue "ordinal of NFU".
Cardinal numbers
Cardinal numbers are defined in NFUNew Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
in a way which generalizes the definition of natural
number: for any set A,
.In ZFC, these equivalence classes are too large as usual. Scott's trick could be used (and indeed is used in ZF
Zermelo–Fraenkel set theory
In mathematics, Zermelo–Fraenkel set theory with the axiom of choice, named after mathematicians Ernst Zermelo and Abraham Fraenkel and commonly abbreviated ZFC, is one of several axiomatic systems that were proposed in the early twentieth century to formulate a theory of sets without the paradoxes...
),
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 fromthe Axiom of Choice in the usual way in both theories).
The natural order on cardinal numbers is seen to be a well-ordering: that it is reflexive, antisymmetric (on abstract cardinals, which are now available) and transitive has been shown above. That it is a linear order follows from the Axiom of Choice: well-order two sets and an
initial segment of one well-ordering will be isomorphic to the other, so one set will have cardinality smaller than that of the other. That it is a well-ordering follows from the Axiom of Choice in a similar way.
With each infinite cardinal, many order types are associated for the usual reasons (in either set theory).
Cantor's theorem shows (in both theories) that there are nontrivial distinctions between infinite cardinal numbers. In ZFC, one proves
In NFUNew Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
, 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 NFU
New Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
is
, where is the set of one-element subsets of A. shows that there are "fewer" singletons than sets (the obvious bijection from to V has already been seen not to be a set). It is actually provable in NFU + Choice that (where << 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: ; 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 cantorian just in case
; the cardinal is also said to be a cantorian cardinal. A set A is said to be strongly cantorian (and its cardinal to be strongly cantorian as well) just in case the restriction of the singleton map to A () is a set. Well-orderings of strongly cantorian sets are always strongly cantorian ordinals; this is not always true of well-orderings of cantorian sets (though the shortest well-ordering of a cantorian set will be cantorian). A cantorian set is a set which satisfies the usual form of Cantor's theorem.The operations of cardinal arithmetic are defined in a set-theoretically motivated way in both theories.
. One would like to define as , and one does this in ZFC, but there is an obstruction in NFUNew Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
when using the Kuratowski pair: one defines
as 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).Defining the exponential operation on cardinals requires T in an essential way: if
was defined as the collection of functions from A to B, this is three types higher than A or B, so it is reasonable to define as so that it is the same type as A or B ( replaces with type-level pairs). An effect of this is that the exponential operation is partial: for example, is undefined. In ZFC one defines as without difficulty.The exponential operation is total and behaves exactly as expected on cantorian cardinals, since T fixes such cardinals and it is easy to show that a function space between cantorian sets is cantorian (as are power sets, cartesian products, and other usual type constructors). This offers further encouragement to the view that the "standard" cardinalities in NFU
New Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
are the cantorian (indeed, the strongly cantorian) cardinalities, just as the "standard" ordinals seem to be the strongly cantorian ordinals.
Now the usual theorems of cardinal arithmetic with the axiom of choice can be proved, including
. From the case the existence of a type level ordered pair can be derived: is equal to just in case , which would be witnessed by a one-to-one correspondence between Kuratowski pairs and double singletons : redefine as the c such that is associated with the Kuratowski : this is a type-level notion of ordered pair.The Axiom of Counting and subversion of stratification
So there are two different implementations of the natural numbers in NFUNew Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
(though they are the same in ZFC): finite ordinals and finite cardinals. Each of these supports a T operation in NFU
New Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
(basically the same operation). It is easy to prove that
is a natural number if n is a natural number in NFUNew Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
+ Infinity + Choice (and so
and the firstinfinite ordinal
are cantorian) but it is not possible to prove in this theory that . However, common sense indicates that this should be true, and so it can be adopted as an axiom:
- Rosser's Axiom of Counting: For each natural number n,
.
One natural consequence of this axiom (and indeed its original formulation) is
for each natural number n.
All that can be proved in NFU
New Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
without Counting is
.A consequence of Counting is that N is a strongly cantorian set (again, this is an equivalent assertion).
Properties of strongly cantorian sets
The type of any variable restricted to a strongly cantorian set A can be raised or lowered as desired by replacing references to with references to (type of a raised; this presupposes that it is known that a is a set; otherwise one must say "the element of " to get this effect) or (type of a lowered) where for all , so it is not necessary to assign types to such variables for purposes of stratification.Any subset of a strongly cantorian set is strongly cantorian. The power set of a strongly cantorian set is strongly cantorian. The cartesian product of two strongly cantorian sets is strongly cantorian.
Introducing the Axiom of Counting means that types need not be assigned to variables restricted to N or to P(N), R (the set of reals) or indeed any set ever considered in classical mathematics outside of set theory.
There are no analogous phenomena in ZFC. See the main New Foundations
New Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
article for stronger axioms that can be adjoined to NFU to enforce "standard" behavior of familiar mathematical objects.
Familiar number systems: positive rationals, magnitudes, and reals
Represent positive fractions as pairs of positive natural numbers (0 is excluded): is represented by the pair . To make , introduce the relation defined by . It is provable that this is an equivalence relation: define positive rational numbers as equivalence classes of pairs of positive natural numbers under this relation. Arithmetic operations on positive rational numbers and the order relation on positive rationals are defined just as in elementary school and proved (with some effort) to have the expected properties.Represent magnitudes (positive reals) as nonempty proper initial segments of the positive rationals with no largest element. The operations of addition and multiplication on magnitudes are implemented by elementwise addition of the positive rational elements of the magnitudes. Order is implemented as set inclusion.
Represent real numbers as differences
of magnitudes: formally speaking, a real number is an equivalence class of pairs of magnitudes under the equivalence relation defined by . The operations of addition and multiplication on real numbers are defined just as one would expect from the algebraic rules for adding and multiplying differences. The treatment of order is also as in elementary algebra.This is the briefest sketch of the constructions. Note that the constructions are exactly the same in ZFC and in NFU
New Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
, except for the difference in the constructions of the natural numbers: since all variables are restricted to strongly cantorian sets, there is no need to worry about stratification restrictions. Without the Axiom of Counting, it might be necessary to introduce some applications of T in a full discussion of these constructions.
Operations on indexed families of sets
In this class of constructions it appears that ZFC has an advantage over NFUNew Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
: though the constructions are clearly feasible in NFU
New Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
, they are more complicated than in ZFC for reasons having to do with stratification.
Throughout this section assume a type-level ordered pair. Define
as . The definition of the general n-tuple using the Kuratowski pair is trickier, as one needs to keep the types of all the projections the same, and the type displacement between the n-tuple and its projections increases as n increases. Here, the n-tuple has the same type as each of its projections.General cartesian products are defined similarly:
The definitions are the same in ZFC but without any worries about stratification (the grouping given here is opposite to that more usually used, but this is easily corrected for).
Now consider the infinite cartesian product
. In ZFC, this is defined as the set of all functions f with domain I such that (where A is implicitly understood as a function taking each i to ).In NFU, this is requires attention to type. Given a set I and set valued function A whose value at
in is written , Define as the set of all functions f with domain I such that : notice that is stratified because of our convention that A is a function with values at singletons of the indices. Note that the very largest families of sets (which cannot be indexed by sets of singletons) will not have cartesian products under this definition. Note further that the sets are at the same type as the index set I (since one type higher than its elements); the product, as a set of functions with domain I (so at the same type as I) is one type higher (assuming a type-level ordered pair).Now consider the product
of the cardinals of these sets. The cardinality || is one type higher than the cardinals , so the correct definition of the infinite product of cardinals is (because the inverse of T is not total, it is possible that this may not exist).Repeat this for disjoint unions of families of sets and sums of families of cardinals. Again, let A be a set-valued function with domain
: write for . The disjoint union is the set . This set is at the same type as the sets .The correct definition of the sum
is thus , since there is no type displacement.It is possible to extend these definitions to handle index sets which are not sets of singletons, but this introduces an additional type level and is not needed for most purposes.
In ZFC, define the disjoint union
as , where abbreviates .Permutation methods can be used to show relative consistency with NFU of the assertion that for every strongly cantorian set A there is a set I of the same size whose elements are self-singletons:
for each i in I.The cumulative hierarchy
In ZFC, define the cumulative hierarchy as the ordinal-indexed sequence of sets satisfying the following conditions:; ; for limit ordinals . This is an example of a construction by transfinite recursion. The rank of a set A is said to be if and only if . The existence of the ranks as sets depends on the axiom of replacement at each limit step (the hierarchy cannot be constructed in Zermelo set theoryZermelo set theory
Zermelo set theory, as set out in an important paper in 1908 by Ernst Zermelo, is the ancestor of modern set theory. It bears certain differences from its descendants, which are not always understood, and are frequently misquoted...
); by the axiom of foundation, every set belongs to some rank.
The cardinal
is called .This construction cannot be carried out in NFU
New Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
because the power set operation is not a set function in NFU
New Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
(
is one type higher than A for purposes of stratification).The sequence of cardinals
can be implemented in NFU. Recall that is defined as , where is a convenient set of size 2, and . Let be the smallest set of cardinals which contains (the cardinality of the set of natural numbers), contains the cardinal whenever it contains , and which is closed under suprema of sets of cardinals.A convention for ordinal indexing of any well-ordering
is defined as the element x of the field of such thatthe order type of the restriction of
to is ; then define as the element with index in the natural order on the elements of . The cardinal is the element with index in the natural order on all infinite cardinals (which is a well-ordering, see above). Note that follows immediately from this definition. In all these constructions, notice that the type of the index is two higher (with type-level ordered pair) than the type of .Each set A of ZFC has a transitive closure
(the intersection of all transitive sets which contains A). By the axiom of foundation, the restriction of the membership relation to the transitive closure of A is a well-founded relationWell-founded relation
In mathematics, a binary relation, R, is well-founded on a class X if and only if every non-empty subset of X has a minimal element with respect to R; that is, for every non-empty subset S of X, there is an element m of S such that for every element s of S, the pair is not in R:\forall S...
. The relation
is either empty or has A as its top element, so this relation is a set picture. It can be proved in ZFC that every set picture is isomorphic to some .This suggests that (an initial segment of) the cumulative hierarchy can be studied by considering the isomorphism classes of set pictures. These isomorphism classes are sets and make up a set in NFU
New Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
. There is a natural set relation analogous to membership on isomorphism classes of set pictures: if
is a set picture, write for its isomorphism class and define as holding if is the isomorphism class of the restriction of y to the downward closure of one of the elements of the preimage under y of the top element of y. The relation E is a set relation, and it is straightforward to prove that it is well-founded and extensional. If the definition of E is confusing, it can be deduced from the observation that it is induced by precisely the relationship which holds between the set picture associated with A and the set picture associated with B when in the usual set theory.There is a T operation on isomorphism classes of set pictures analogous to the T operation on ordinals: if x is a set picture, so is
. Define as . It is easy to see that .An axiom of extensionality for this simulated set theory follows from E's extensionality. From its well-foundedness follows an axiom of foundation. There remains the question of what comprehension axiom E may have. Consider any collection of set pictures
(collection of set pictures whose fields are made up entirely of singletons). Since each is one type higher than x (using a type-level ordered pair), replacing each element of the field of each in the collection with results in a collection of set pictures isomorphic to the original collection but with their fields disjoint. The union of these setpictures with a new top element yields a set picture whose isomorphism type will have as its preimages under E exactly the elements of the original collection. That is, for any collection of isomorphism types
, there is an isomorphism type whose preimage under E is exactly this collection.In particular, there will be an isomorphism type [v] whose preimage under E is the collection of all T[x]s (including T[v]). Since T[v] E v and E is well-founded,
. This resembles the resolution of the Burali-Forti paradox discussed above and in the New FoundationsNew Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
article, and is in fact the local resolution of Mirimanoff's paradox of the set of all well-founded sets.
There are ranks of isomorphism classes of set pictures just as there are ranks of sets in the usual set theory. For any collection of set pictures A, define S(A) as the set of all isomorphism classes of set pictures whose preimage under E is a subset of A; call A a "complete" set if every subset of A is a preimage under E. The collection of "ranks" is the smallest collection containing the empty set and closed under the S operation (which is a kind of power set construction) and under unions of its subcollections. It is straightforward to prove (much as in the usual set theory) that the ranks are well-ordered by inclusion, and so the ranks have an index in this well-order: refer to the rank with index
as . It is provable that for complete ranks . The union of the complete ranks (which will be the first incomplete rank) with the relation E looks like an initial segment of the universe of Zermelo-style set theory (not necessarily like the full universe of ZFC because it may not be large enough). It is provable that if is the first incomplete rank, then is a complete rank and thus . So there is a "rank of the cumulative hierarchy" with an "external automorphism" T moving the rank downward, exactly the condition on a nonstandard model of a rank in the cumulative hierarchy under which a model of NFU is constructed in the New FoundationsNew Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
article. There are technical details to verify, but there is an interpretation not only of a fragment of ZFC but of NFU
New Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
itself in this structure, with
defined as : this "relation" is not a set relation but has the same type displacement between its arguments as the usual membership relation .So there is a natural construction inside NFU of the cumulative hierarchy of sets which internalizes the natural construction of a model of NFU in Zermelo-style set theory.
Under the Axiom of Cantorian Sets described in the New Foundations
New Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
article, the strongly cantorian part of the set of isomorphism classes of set pictures with the E relation as membership becomes a (proper class) model of ZFC (in which there are n-Mahlo cardinals for each n; this extension of NFU is strictly stronger than ZFC). This is a proper class model because the strongly cantorian isomorphism classes do not make up a set.
Permutation methods can be used to create from any model of NFU a model in which every strongly cantorian isomorphism type of set pictures is actually realized as the restriction of the true membership relation to the transitive closure of a set.
External links
- Metamath: A web site devoted to an ongoing derivation of mathematics from the axioms of ZFC and first-order logicFirst-order logicFirst-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...
. - Stanford Encyclopedia of PhilosophyStanford Encyclopedia of PhilosophyThe Stanford Encyclopedia of Philosophy is a freely-accessible online encyclopedia of philosophy maintained by Stanford University. Each entry is written and maintained by an expert in the field, including professors from over 65 academic institutions worldwide...
:- Quine's New Foundations -- by Thomas Forster.
- Alternative axiomatic set theories -- by Randall Holmes.
- Randall Holmes: New Foundations Home Page