Urelement

Last updated

In set theory, a branch of mathematics, an urelement or ur-element (from the German prefix ur-, 'primordial') is an object that is not a set (has no elements), but that may be an element of a set. It is also referred to as an atom or individual. Ur-elements are also not identical with the empty set.

Contents

Theory

There are several different but essentially equivalent ways to treat urelements in a first-order theory.

One way is to work in a first-order theory with two sorts, sets and urelements, with a ∈ b only defined when b is a set. In this case, if U is an urelement, it makes no sense to say , although is perfectly legitimate.

Another way is to work in a one-sorted theory with a unary relation used to distinguish sets and urelements. As non-empty sets contain members while urelements do not, the unary relation is only needed to distinguish the empty set from urelements. Note that in this case, the axiom of extensionality must be formulated to apply only to objects that are not urelements.

This situation is analogous to the treatments of theories of sets and classes. Indeed, urelements are in some sense dual to proper classes: urelements cannot have members whereas proper classes cannot be members. Put differently, urelements are minimal objects while proper classes are maximal objects by the membership relation (which, of course, is not an order relation, so this analogy is not to be taken literally).

Urelements in set theory

The Zermelo set theory of 1908 included urelements, and hence is a version now called ZFA or ZFCA (i.e. ZFA with axiom of choice). [1] It was soon realized that in the context of this and closely related axiomatic set theories, the urelements were not needed because they can easily be modeled in a set theory without urelements. [2] Thus, standard expositions of the canonical axiomatic set theories ZF and ZFC do not mention urelements (for an exception, see Suppes [3] ). Axiomatizations of set theory that do invoke urelements include Kripke–Platek set theory with urelements and the variant of Von Neumann–Bernays–Gödel set theory described by Mendelson. [4] In type theory, an object of type 0 can be called an urelement; hence the name "atom".

Adding urelements to the system New Foundations (NF) to produce NFU has surprising consequences. In particular, Jensen proved [5] the consistency of NFU relative to Peano arithmetic; meanwhile, the consistency of NF relative to anything remains an open problem, pending verification of Holmes's proof of its consistency relative to ZF. Moreover, NFU remains relatively consistent when augmented with an axiom of infinity and the axiom of choice. Meanwhile, the negation of the axiom of choice is, curiously, an NF theorem. Holmes (1998) takes these facts as evidence that NFU is a more successful foundation for mathematics than NF. Holmes further argues that set theory is more natural with than without urelements, since we may take as urelements the objects of any theory or of the physical universe. [6] In finitist set theory, urelements are mapped to the lowest-level components of the target phenomenon, such as atomic constituents of a physical object or members of an organisation.

Quine atoms

An alternative approach to urelements is to consider them, instead of as a type of object other than sets, as a particular type of set. Quine atoms (named after Willard Van Orman Quine) are sets that only contain themselves, that is, sets that satisfy the formula x = {x}. [7]

Quine atoms cannot exist in systems of set theory that include the axiom of regularity, but they can exist in non-well-founded set theory. ZF set theory with the axiom of regularity removed cannot prove that any non-well-founded sets exist (unless it is inconsistent, in which case it will prove any arbitrary statement), but it is compatible with the existence of Quine atoms. Aczel's anti-foundation axiom implies that there is a unique Quine atom. Other non-well-founded theories may admit many distinct Quine atoms; at the opposite end of the spectrum lies Boffa's axiom of superuniversality, which implies that the distinct Quine atoms form a proper class. [8]

Quine atoms also appear in Quine's New Foundations, which allows more than one such set to exist. [9]

Quine atoms are the only sets called reflexive sets by Peter Aczel, [8] although other authors, e.g. Jon Barwise and Lawrence Moss, use the latter term to denote the larger class of sets with the property x ∈ x. [10]

Related Research Articles

<span class="mw-page-title-main">Axiom of choice</span> Axiom of set theory

In mathematics, the axiom of choice, abbreviated AC or AoC, is an axiom of set theory equivalent to the statement that a Cartesian product of a collection of non-empty sets is non-empty. Informally put, the axiom of choice says that given any collection of sets, each containing at least one element, it is possible to construct a new set by choosing one element from each set, even if the collection is infinite. Formally, it states that for every indexed family of nonempty sets, there exists an indexed set such that for every . The axiom of choice was formulated in 1904 by Ernst Zermelo in order to formalize his proof of the well-ordering theorem.

In mathematics, the axiom of regularity is an axiom of Zermelo–Fraenkel set theory that states that every non-empty set A contains an element that is disjoint from A. In first-order logic, the axiom reads:

Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal systems of logic such as their expressive or deductive power. However, it can also include uses of logic to characterize correct mathematical reasoning or to establish foundations of mathematics.

In set theory and its applications throughout mathematics, a class is a collection of sets that can be unambiguously defined by a property that all its members share. Classes act as a way to have set-like collections while differing from sets so as to avoid paradoxes, especially Russell's paradox. The precise definition of "class" depends on foundational context. In work on Zermelo–Fraenkel set theory, the notion of class is informal, whereas other set theories, such as von Neumann–Bernays–Gödel set theory, axiomatize the notion of "proper class", e.g., as entities that are not members of another entity.

<span class="mw-page-title-main">Set theory</span> Branch of mathematics that studies sets

Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory — as a branch of mathematics — is mostly concerned with those that are relevant to mathematics as a whole.

In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom of extensionality, axiom of extension, or axiom of extent, is one of the axioms of Zermelo–Fraenkel set theory. Informally, it says that the two sets A and B are equal if and only if A and B have the same members.

In set theory, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such as Russell's paradox. Today, Zermelo–Fraenkel set theory, with the historically controversial axiom of choice (AC) included, is the standard form of axiomatic set theory and as such is the most common foundation of mathematics. Zermelo–Fraenkel set theory with the axiom of choice included is abbreviated ZFC, where C stands for "choice", and ZF refers to the axioms of Zermelo–Fraenkel set theory with the axiom of choice excluded.

In set theory, an uncountable cardinal is inaccessible if it cannot be obtained from smaller cardinals by the usual operations of cardinal arithmetic. More precisely, a cardinal κ is strongly inaccessible if it satisfies the following three conditions: it is uncountable, it is not a sum of fewer than κ cardinals smaller than κ, and implies .

Zermelo set theory, as set out in a seminal paper in 1908 by Ernst Zermelo, is the ancestor of modern Zermelo–Fraenkel set theory (ZF) and its extensions, such as von Neumann–Bernays–Gödel set theory (NBG). It bears certain differences from its descendants, which are not always understood, and are frequently misquoted. This article sets out the original axioms, with the original text and original numbering.

In set theory, several ways have been proposed to construct the natural numbers. These include the representation via von Neumann ordinals, commonly employed in axiomatic set theory, and a system based on equinumerosity that was proposed by Gottlob Frege and by Bertrand Russell.

In set theory and related branches of mathematics, the von Neumann universe, or von Neumann hierarchy of sets, denoted by V, is the class of hereditary well-founded sets. This collection, which is formalized by Zermelo–Fraenkel set theory (ZFC), is often used to provide an interpretation or motivation of the axioms of ZFC. The concept is named after John von Neumann, although it was first published by Ernst Zermelo in 1930.

Internal set theory (IST) is a mathematical theory of sets developed by Edward Nelson that provides an axiomatic basis for a portion of the nonstandard analysis introduced by Abraham Robinson. Instead of adding new elements to the real numbers, Nelson's approach modifies the axiomatic foundations through syntactic enrichment. Thus, the axioms introduce a new term, "standard", which can be used to make discriminations not possible under the conventional ZFC axioms for sets. Thus, IST is an enrichment of ZFC: all axioms of ZFC are satisfied for all classical predicates, while the new unary predicate "standard" satisfies three additional axioms I, S, and T. In particular, suitable nonstandard elements within the set of real numbers can be shown to have properties that correspond to the properties of infinitesimal and unlimited elements.

In mathematical logic, New Foundations (NF) is a non-well-founded, finitely axiomatizable set theory conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica.

Non-well-founded set theories are variants of axiomatic set theory that allow sets to be elements of themselves and otherwise violate the rule of well-foundedness. In non-well-founded set theories, the foundation axiom of ZFC is replaced by axioms implying its negation.

The Kripke–Platek set theory with urelements (KPU) is an axiom system for set theory with urelements, based on the traditional (urelement-free) Kripke–Platek set theory. It is considerably weaker than the (relatively) familiar system ZFU. The purpose of allowing urelements is to allow large or high-complexity objects to be included in the theory's transitive models without disrupting the usual well-ordering and recursion-theoretic properties of the constructible universe; KP is so weak that this is hard to do by traditional means.

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 and in NFU, the version of Quine's New Foundations shown to be consistent by R. B. Jensen in 1969.

An approach to the foundations of mathematics that is of relatively recent origin, Scott–Potter set theory is a collection of nested axiomatic set theories set out by the philosopher Michael Potter, building on earlier work by the mathematician Dana Scott and the philosopher George Boolos.

In mathematics and logic, Ackermann set theory is an axiomatic set theory proposed by Wilhelm Ackermann in 1956.

In the foundations of mathematics, Aczel's anti-foundation axiom is an axiom set forth by Peter Aczel, as an alternative to the axiom of foundation in Zermelo–Fraenkel set theory. It states that every accessible pointed directed graph corresponds to exactly one set. In particular, according to this axiom, the graph consisting of a single vertex with a loop corresponds to a set that contains only itself as element, i.e. a Quine atom. A set theory obeying this axiom is necessarily a non-well-founded set theory.

References

  1. ↑ Dexter Chua et al.: ZFA: Zermelo–Fraenkel set theory with atoms, on: ncatlab.org: nLab, revised on July 16, 2016.
  2. ↑ Jech, Thomas J. (1973). The Axiom of Choice . Mineola, New York: Dover Publ. p.  45. ISBN   0486466248.
  3. ↑ Suppes, Patrick (1972). Axiomatic Set Theory ([Éd. corr. et augm. du texte paru en 1960] ed.). New York: Dover Publ. ISBN   0486616304 . Retrieved 17 September 2012.
  4. ↑ Mendelson, Elliott (1997). Introduction to Mathematical Logic (4th ed.). London: Chapman & Hall. pp. 297–304. ISBN   978-0412808302 . Retrieved 17 September 2012.
  5. ↑ Jensen, Ronald Björn (December 1968). "On the Consistency of a Slight (?) Modification of Quine's 'New Foundations'". Synthese. 19 (1/2). Springer: 250–264. doi:10.1007/bf00568059. ISSN   0039-7857. JSTOR   20114640. S2CID   46960777.
  6. ↑ Holmes, Randall, 1998. Elementary Set Theory with a Universal Set . Academia-Bruylant.
  7. ↑ Thomas Forster (2003). Logic, Induction and Sets. Cambridge University Press. p. 199. ISBN   978-0-521-53361-4.
  8. 1 2 Aczel, Peter (1988), Non-well-founded sets, CSLI Lecture Notes, vol. 14, Stanford University, Center for the Study of Language and Information, p.  57, ISBN   0-937073-22-9, MR   0940014 , retrieved 2016-10-17.
  9. ↑ Barwise, Jon; Moss, Lawrence S. (1996), Vicious circles. On the mathematics of non-wellfounded phenomena, CSLI Lecture Notes, vol. 60, CSLI Publications, p. 306, ISBN   1575860090 .
  10. ↑ Barwise, Jon; Moss, Lawrence S. (1996), Vicious circles. On the mathematics of non-wellfounded phenomena, CSLI Lecture Notes, vol. 60, CSLI Publications, p. 57, ISBN   1575860090 .
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.