Editing Universe (mathematics)

{{short description|All-encompassing set or class}}

[[File:Probability_venn_event.svg|thumb|320x320px|The relationship between universe and complement]]

In [[mathematics]], and particularly in [[set theory]], [[category theory]], [[type theory]], and the [[foundations of mathematics]], a '''universe''' is a collection that contains all the entities one wishes to consider in a given situation.

In set theory, universes are often [[class (set theory)|classes]] that contain (as [[element (set theory)|elements]]) all sets for which one hopes to [[Mathematical proof|prove]] a particular [[theorem]]. These classes can serve as [[Inner model|inner models]] for various axiomatic systems such as [[Zermelo–Fraenkel set theory|ZFC]] or [[Morse–Kelley set theory]]. Universes are of critical importance to formalizing concepts in [[category theory]] inside set-theoretical foundations. For instance, the [[List of mathematical jargon#canonical|canonical]] motivating example of a category is '''[[Category of sets|Set]]''', the category of all sets, which cannot be formalized in a set theory without some notion of a universe.

In type theory, a universe is a type whose elements are types.

==In a specific context==
{{Main|Domain of discourse}}
Perhaps the simplest version is that ''any'' set can be a universe, so long as the object of study is confined to that particular set. If the object of study is formed by the [[real number]]s, then the [[real line]] '''R''', which is the real number set, could be the universe under consideration. Implicitly, this is the universe that [[Georg Cantor]] was using when he first developed modern [[naive set theory]] and [[cardinality]] in the 1870s and 1880s in applications to [[real analysis]]. The only sets that Cantor was originally interested in were [[subset]]s of '''R'''.

This concept of a universe is reflected in the use of [[Venn diagram]]s. In a Venn diagram, the action traditionally takes place inside a large rectangle that represents the universe ''U''. One generally says that sets are represented by circles; but these sets can only be subsets of ''U''. The [[complement (set theory)|complement]] of a set ''A'' is then given by that portion of the rectangle outside of ''A'''s circle. Strictly speaking, this is the [[complement (set theory)|relative complement]] ''U'' \ ''A'' of ''A'' relative to ''U''; but in a context where ''U'' is the universe, it can be regarded as the [[complement (set theory)|absolute complement]] ''A''<sup>C</sup> of ''A''. Similarly, there is a notion of the [[nullary intersection]], that is the [[intersection (set theory)|intersection]] of [[0 (number)|zero]] sets (meaning no sets, not [[null set]]s).

Without a universe, the nullary intersection would be the set of absolutely everything, which is generally regarded as impossible; but with the universe in mind, the nullary intersection can be treated as the set of everything under consideration, which is simply ''U''. These conventions are quite useful in the algebraic approach to basic set theory, based on [[Boolean lattice]]s. Except in some non-standard forms of [[axiomatic set theory]] (such as [[New Foundations]]), the [[class (set theory)|class]] of all sets is not a Boolean lattice (it is only a [[relatively complemented lattice]]).

In contrast, the class of all subsets of ''U'', called the [[power set]] of ''U'', is a Boolean lattice. The absolute complement described above is the complement operation in the Boolean lattice; and ''U'', as the nullary intersection, serves as the [[Greatest element|top element]] (or nullary [[meet (mathematics)|meet]]) in the Boolean lattice. Then [[De Morgan's laws]], which deal with complements of meets and [[join (mathematics)|join]]s (which are [[union (set theory)|union]]s in set theory) apply, and apply even to the nullary meet and the nullary join (which is the [[empty set]]).

==In ordinary mathematics==
However, once subsets of a given set ''X'' (in Cantor's case, ''X'' = '''R''') are considered, the universe may need to be a set of subsets of ''X''. (For example, a [[topological space|topology]] on ''X'' is a set of subsets of ''X''.) The various sets of subsets of ''X'' will not themselves be subsets of ''X'' but will instead be subsets of '''P'''''X'', the [[power set]] of ''X''. This may be continued; the object of study may next consist of such sets of subsets of ''X'', and so on, in which case the universe will be '''P'''('''P'''''X''). In another direction, the [[binary relation]]s on ''X'' (subsets of the [[Cartesian product]] {{Nowrap|''X'' × ''X'')}} may be considered, or [[function (mathematics)|function]]s from ''X'' to itself, requiring universes like {{Nowrap|'''P'''(''X'' × ''X'')}} or ''X''<sup>''X''</sup>.

Thus, even if the primary interest is ''X'', the universe may need to be considerably larger than ''X''. Following the above ideas, one may want the '''superstructure''' over ''X'' as the universe. This can be defined by [[structural recursion]] as follows:
* Let '''S'''<sub>0</sub>''X'' be ''X'' itself.
* Let '''S'''<sub>1</sub>''X'' be the [[union (set theory)|union]] of ''X'' and '''P'''''X''.
* Let '''S'''<sub>2</sub>''X'' be the union of '''S'''<sub>1</sub>''X'' and '''P'''('''S'''<sub>1</sub>''X'').
* In general, let '''S'''<sub>''n''+1</sub>''X'' be the union of '''S'''<sub>n</sub>''X'' and '''P'''('''S'''<sub>''n''</sub>''X'').
Then the superstructure over ''X'', written '''S'''''X'', is the union of '''S'''<sub>0</sub>''X'', '''S'''<sub>1</sub>''X'', '''S'''<sub>2</sub>''X'', and so on; or
: <math> \mathbf{S}X := \bigcup_{i=0}^{\infty} \mathbf{S}_{i}X \mbox{.} \! </math>

No matter what set ''X'' is the starting point, the [[empty set]] {} will belong to '''S'''<sub>1</sub>''X''. The empty set is the [[von Neumann ordinal]] [0].
Then {[0]}, the set whose only element is the empty set, will belong to '''S'''<sub>2</sub>''X''; this is the von Neumann ordinal [1]. Similarly, {[1]} will belong to '''S'''<sub>3</sub>''X'', and thus so will {[0],[1]}, as the union of {[0]} and {[1]}; this is the von Neumann ordinal [2]. Continuing this process, every [[natural number]] is represented in the superstructure by its von Neumann ordinal. Next, if ''x'' and ''y'' belong to the superstructure, then so does {{''x''},{''x'',''y''}}, which represents the [[ordered pair]] (''x'',''y''). Thus the superstructure will contain the various desired Cartesian products. Then the superstructure also contains [[function (mathematics)|function]]s and [[relation (mathematics)|relation]]s, since these may be represented as subsets of Cartesian products. The process also gives ordered ''n''-tuples, represented as functions whose domain is the von Neumann ordinal [''n''], and so on.

So if the starting point is just ''X'' = {}, a great deal of the sets needed for mathematics appear as elements of the superstructure over {}. But each of the elements of '''S'''{} will be a [[finite set]]. Each of the natural numbers belongs to it, but the set '''N''' of ''all'' natural numbers does not (although it is a ''subset'' of '''S'''{}). In fact, the superstructure over {} consists of all of the [[hereditarily finite set]]s. As such, it can be considered the ''universe of [[finitist mathematics]]''. Speaking anachronistically, one could suggest that the 19th-century finitist [[Leopold Kronecker]] was working in this universe; he believed that each natural number existed but that the set '''N''' (a "[[completed infinity]]") did not.

However, '''S'''{} is unsatisfactory for ordinary mathematicians (who are not finitists), because even though '''N''' may be available as a subset of '''S'''{}, still the power set of '''N''' is not. In particular, arbitrary sets of real numbers are not available. So it may be necessary to start the process all over again and form '''S'''('''S'''{}). However, to keep things simple, one can take the set '''N''' of natural numbers as given and form '''SN''', the superstructure over '''N'''. This is often considered the ''universe of [[ordinary mathematics]]''. The idea is that all of the mathematics that is ordinarily studied refers to elements of this universe. For example, any of the usual [[constructions of the real numbers]] (say by [[Dedekind cut]]s) belongs to '''SN'''. Even [[non-standard analysis]] can be done in the superstructure over a [[non-standard model]] of the natural numbers.

There is a slight shift in philosophy from the previous section, where the universe was any set ''U'' of interest. There, the sets being studied were ''subset''s of the universe; now, they are ''members'' of the universe. Thus although '''P'''('''S'''''X'') is a Boolean lattice, what is relevant is that '''S'''''X'' itself is not. Consequently, it is rare to apply the notions of Boolean lattices and Venn diagrams directly to the superstructure universe as they were to the power-set universes of the previous section. Instead, one can work with the individual Boolean lattices '''P'''''A'', where ''A'' is any relevant set belonging to '''S'''''X''; then '''P'''''A'' is a subset of '''S'''''X'' (and in fact belongs to '''S'''''X''). In Cantor's case ''X'' = '''R''' in particular, arbitrary sets of real numbers are not available, so there it may indeed be necessary to start the process all over again.

==In set theory==
It is possible to give a precise meaning to the claim that '''SN''' is the universe of ordinary mathematics; it is a [[model theory|model]] of [[Zermelo set theory]], the [[axiomatic set theory]] originally developed by [[Ernst Zermelo]] in 1908. Zermelo set theory was successful precisely because it was capable of axiomatising "ordinary" mathematics, fulfilling the programme begun by Cantor over 30 years earlier. But Zermelo set theory proved insufficient for the further development of axiomatic set theory and other work in the [[foundations of mathematics]], especially [[model theory]].

For a dramatic example, the description of the superstructure process above cannot itself be carried out in Zermelo set theory. The final step, forming '''S''' as an infinitary union, requires the [[axiom of replacement]], which was added to Zermelo set theory in 1922 to form [[Zermelo–Fraenkel set theory]], the set of axioms most widely accepted today. So while ordinary mathematics may be done ''in'' '''SN''', discussion ''of'' '''SN''' goes beyond the "ordinary", into [[metamathematics]].

But if high-powered set theory is brought in, the superstructure process above reveals itself to be merely the beginning of a [[transfinite recursion]].
Going back to ''X'' = {}, the empty set, and introducing the (standard) notation ''V''<sub>''i''</sub> for '''S'''<sub>''i''</sub>{}, ''V''<sub>0</sub> = {}, ''V''<sub>1</sub> = '''P'''{}, and so on as before. But what used to be called "superstructure" is now just the next item on the list: ''V''<sub>ω</sub>, where ω is the first [[Infinity|infinite]] [[ordinal number]]. This can be extended to arbitrary [[ordinal number]]s:
: <math> V_{i} := \bigcup_{j<i} \mathbf{P}V_j \! </math>
defines ''V''<sub>''i''</sub> for ''any'' ordinal number ''i''.
The union of all of the ''V''<sub>''i''</sub> is the [[von Neumann universe]] ''V'':
: <math> V := \bigcup_{i} V_{i} \! </math>.
Every individual ''V''<sub>''i''</sub> is a set, but their union ''V'' is a [[proper class]]. The [[axiom of foundation]], which was added to [[Zermelo–Fraenkel set theory|ZF]] set theory at around the same time as the axiom of replacement, says that ''every'' set belongs to ''V''.

: ''[[Kurt Gödel]]'s [[constructible universe]] ''L'' and the [[axiom of constructibility]]''
: ''[[Inaccessible cardinal]]s yield models of ZF and sometimes additional axioms, and are equivalent to the existence of the [[Grothendieck universe]] set''

==In predicate calculus==
In an [[interpretation (logic)|interpretation]] of [[first-order logic]], the universe (or domain of discourse) is the set of individuals (individual constants) over which the [[Quantifier (logic)|quantifiers]] range. A proposition such as {{math|[[Universal quantification|∀]]''x'' (''x''<sup>2</sup> ≠ 2)}} is ambiguous, if no domain of discourse has been identified.  In one interpretation, the domain of discourse could be the set of [[real number]]s; in another interpretation, it could be the set of [[natural number]]s. If the domain of discourse is the set of real numbers, the proposition is false, with {{math|1=''x'' = {{radic|2}}}} as counterexample; if the domain is the set of naturals, the proposition is true, since 2 is not the square of any natural number.

==In category theory==
{{Main|Grothendieck universe}}
There is another approach to universes which is historically connected with [[category theory]].  This is the idea of a [[Grothendieck universe]].  Roughly speaking, a Grothendieck universe is a set inside which all the usual operations of set theory can be performed.  This version of a universe is defined to be any set for which the following axioms hold:<ref>Mac Lane 1998, p. 22</ref>
# <math>x\in u\in U</math> implies <math>x\in U</math>
# <math>u\in U</math> and <math>v\in U</math> imply {''u'',''v''}, (''u'',''v''), and <math>u\times v\in U</math>.
# <math>x\in U</math> implies <math>\mathcal{P}x\in U</math> and <math>\cup x\in U</math>
# <math>\omega\in U</math> (here <math>\omega=\{0,1,2,...\}</math> is the set of all [[Ordinal number|finite ordinals]].)
# if <math>f:a\to b</math> is a surjective function with <math> a\in U</math> and <math>b\subset U</math>, then <math>b\in U</math>.

The most common use of a Grothendieck universe ''U'' is to take ''U'' as a replacement for the category of all sets.  One says that a set ''S'' is '''''U'''''-'''small''' if ''S'' ∈''U'', and '''''U'''''-'''large''' otherwise.  The category ''U''-'''Set''' of all ''U''-small sets has as objects all ''U''-small sets and as morphisms all functions between these sets.  Both the object set and the morphism set are sets, so it becomes possible to discuss the category of "all" sets without invoking proper classes.  Then it becomes possible to define other categories in terms of this new category.  For example, the category of all ''U''-small categories is the category of all categories whose object set and whose morphism set are in ''U''.  Then the usual arguments of set theory are applicable to the category of all categories, and one does not have to worry about accidentally talking about proper classes.  Because Grothendieck universes are extremely large, this suffices in almost all applications.

Often when working with Grothendieck universes, mathematicians assume the [[Tarski–Grothendieck set theory|Axiom of Universes]]: "For any set ''x'', there exists a universe ''U'' such that ''x'' ∈''U''."  The point of this axiom is that any set one encounters is then ''U''-small for some ''U'', so any argument done in a general Grothendieck universe can be applied.<ref>{{Cite arXiv |last=Low |first=Zhen Lin |date=2013-04-18 |title=Universes for category theory |class=math.CT |eprint=1304.5227v2 }}</ref>  This axiom is closely related to the existence of [[Inaccessible cardinal|strongly inaccessible cardinal]]s.

==In type theory<!--'Russell-style universe', 'Russell-style universes', 'Tarski-style universe', and 'Tarski-style universes' redirect here-->==
In some type theories, especially in systems with [[Dependent type|dependent types]], types themselves can be regarded as [[Term (logic)|terms]]. There is a type called the universe (often denoted <math>\mathcal{U}</math>) which has types as its elements. To avoid paradoxes such as [[System U#Girard's paradox|Girard's paradox]] (an analogue of [[Russell's paradox]] for type theory), type theories are often equipped with a [[Countable set|countably infinite]] hierarchy of such universes, with each universe being a term of the next one. 

There are at least two kinds of universes that one can consider in type theory: '''Russell-style universes''' (named after [[Bertrand Russell]]) and '''Tarski-style universes''' (named after [[Alfred Tarski]]).<ref name=nLab>[https://ncatlab.org/homotopytypetheory/show/universe "Universe in Homotopy Type Theory"] in [[nLab]]</ref><ref>Zhaohui Luo, [http://www.cs.rhul.ac.uk/home/zhaohui/universes.pdf "Notes on Universes in Type Theory"], 2012.</ref><ref>[[Per Martin-Löf]], ''Intuitionistic Type Theory'', Bibliopolis, 1984, pp. 88 and 91.</ref> A Russell-style universe is a type whose terms are types.<ref name=nLab/> A Tarski-style universe is a type together with an interpretation operation allowing us to regard its terms as types.<ref name=nLab/>

For example:<ref>{{cite journal |last1=Rathjen |first1=Michael |date=October 2005 |title=The Constructive Hilbert Program and the Limits of Martin-Löf Type Theory |url=https://link.springer.com/article/10.1007/s11229-004-6208-4 |journal=Synthese |volume=147 |pages=81–120 |doi=10.1007/s11229-004-6208-4 |s2cid=143295 |access-date=September 21, 2022}}</ref>

{{quote|The openendedness of [[Martin-Löf type theory]] is particularly manifest in the introduction of so-called universes. Type universes encapsulate the informal notion of reflection whose role may be explained as follows. During the course of developing a particular formalization of type theory, the type theorist may look back over the rules for types, say C, which have been introduced hitherto and perform the step of recognizing that they are valid according to [[Martin-Löf]]’s informal semantics of meaning explanation. This act of ‘introspection’ is an attempt to become aware of the conceptions which have governed our constructions in the past. It gives rise to a “[[reflection principle]] which roughly speaking says whatever we are used to doing with types can be done inside a universe” (Martin-Löf 1975, 83). On the formal level, this leads to an extension of the existing formalization of type theory in that the type forming capacities of C become enshrined in a type universe U<sub>C</sub> mirroring C.}}

==See also==
* [[Conglomerate (mathematics)]]
* [[Domain of discourse]]
* [[Grothendieck universe]]
* [[Herbrand universe]]
* [[Free object]]
* [[Open formula]]
* [[Space (mathematics)]]

==Notes==
{{reflist}}

==References==
*Mac Lane, Saunders (1998). ''Categories for the Working Mathematician''. Springer-Verlag New York, Inc.

==External links==
* {{springer|title=Universe|id=p/u095770}}
* {{MathWorld |title=Universal Set|id=UniversalSet}}

{{Mathematical logic}}

[[Category:Mathematical logic]]
[[Category:Families of sets]]
[[Category:Set theory]]