Scott–Potter set theory

From Wikipedia, the free encyclopedia

You have new messages (last change).

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.

Potter (1990, 2004) clarified and simplified the approach of Scott (1974), and showed how the resulting axiomatic set theory can do what is expected of such theory, namely grounding the cardinal and ordinal numbers, Peano arithmetic and the other usual number systems, and the theory of relations.

Contents

[edit] ZU etc.

[edit] Preliminaries

This section and the next follow Part I of Potter (2004) closely. The background logic is first order logic with identity. The ontology includes urelements as well as sets, simply to allow the set theories described in this entry to have models that are not purely mathematical in nature. The urelements serve no essential mathematical purpose.

Some terminology peculiar to Potter's set theory:

  • a is a collection if a={x : x∈a}. All sets are collections, but not all collections are sets.
  • The accumulation of a, acc(a), is the set {x : x is a urelement or ∃b∈a (x∈b or x⊂b)}.
  • If ∀V∈V(V = acc(V∩V)) then V is a history.
  • A level is the accumulation of a history.
  • An initial level has no other levels as members.
  • A limit level is a level that is neither the initial level nor the level above any other level.
  • The birthday of set a, denoted V(a), is the lowest level V such that a⊂V.

[edit] Axioms

Creation: ∀V∃V' (V∈V' ).

Remark: There is no highest level, hence there are infinitely many levels. This axiom establishes the ontology of levels.

Separation: An axiom schema. For any first order formula Φ(x) with (bound) variables ranging over the level V, the collection {x∈V : Φ(x)} is also a set.

Remark: Given the levels established by Creation, this schema establishes the existence of sets and how to form them. It tells us that a level is a set, and all subsets, definable via first order logic, of levels are also sets. This schema can be seen as an extension of the background logic.

Infinity: There exists at least one limit level.

Remark: Among the sets Separation allows, at least one is infinite. This axiom is primarily mathematical, as there is no need for the actual infinite in other human contexts, the human sensory order being necessarily finite. For mathematical purposes, the axiom "There exists an inductive set" would suffice.

[edit] Further existence premises

The following statements, while in the nature of axioms, are not axioms of ZU. Instead, they assert the existence of sets satisfying a stated condition. As such, they are "existence premises," meaning the following. Let X denote any statement below. Any theorem whose proof requires X is then formulated conditionally as "If X holds, then..." Potter defines several systems using existence premises, including the following two:

  • ZfU =df ZU + Ordinals;
  • ZFU =df Separation + Reflection.

Ordinals: For each (infinite) ordinal α, there exists a corresponding level Vα.

Remark: In words, "There exists a level corresponding to each infinite ordinal." Ordinals makes possible the conventional Von Neumann definition of ordinal numbers.

Let τ(x) be a first order term.

Replacement: An axiom scheme. For any collection a, ∀x∈a(τ(x) is a set) → {τ(x) : x∈a} is a set.

Remark: If the term τ(x) is a function (call it f(x)), and if the domain of f is a set, then the range of f is also a set.

Let Φ denote a first order formula in which any number of free variables are present. Let Φ(V) denote Φ with these free variables all quantified, with the quantified variables restricted to the level V.

Reflection: An axiom schema. If the free variables in any instance of ∃V(Φ→Φ(V)) are universally quantified, the result is an axiom.

Remark: This schema asserts the existence of a "partial" universe, namely the level V, in which all properties Φ holding when the quantified variables range over all levels, also hold when these variables range over V only. Reflection turns Creation, Infinity, Ordinals, and Replacement into theorems. (Potter 2004: §13.3).

Let A and a denote sequences of nonempty sets, each indexed by n.

Countable Choice: Given any sequence A, there exists a sequence a such that:

∀n∈ω(an∈An).

Remark. Countable Choice enables proving that any set must be one of finite or infinite.

Let B and C denote sets, and let n index the members of B, each denoted Bn.

Choice: Let the members of B be disjoint nonempty sets. Then:

∃C∀n(C∩Bn is a singleton).

[edit] Discussion

Boolos's (1971) proposed the "iterative conception of set" as a way of keeping at bay the eponymous (Russell's, Burali-Forti's, and Cantor's) paradoxes resulting from the unrestricted use of the principle of comprehension that naive set theory allows. The iterative conception of set stratifies the universe of sets into a sequence of "levels," with sets at lower levels being logically prior to sets at higher levels. Moreover, the sets at a given level are the members of the sets making up the next higher level. Hence the levels form a nested and well-ordered sequence, and would form a hierarchy if set membership were transitive.

The resulting hierarchy of levels and sets steers clear of the paradoxes of naive set theory in a well-motivated way. Collections such as "the class of all sets" or "the class of all ordinals" include sets from all levels of the hierarchy. Given the iterative conception, such collections cannot form sets at any given level of the hierarchy and thus cannot be sets at all. The iterative conception has come to be more and more accepted in recent decades, despite an imperfect understanding of its historical origins.

[edit] Scott's theory

Scott (1974) did not mention the "iterative conception of set," instead proposing his theory as a natural outgrowth of the simple theory of types. Nevertheless, Scott's theory can be seen as an unwitting axiomatization of the iterative conception and the associated iterative hierarchy.

Scott began with an axiom he declined to name: the atomic formula x∈y implies that y is a set. In symbols:

∀x,y∃a[x∈y→y=a].

His axiom of Extensionality and axiom schema of Comprehension (Separation) are strictly analogous to their ZF counterparts and so do not mention levels. He then invoked two axioms that do mention levels:

  • Accumulation. A given level "accumulates" all members and subsets of all earlier levels. See the above definition of accumulation.
  • Restriction. All collections belong to some level.

Restriction also implies the existence of at least one level and assures that all sets are well-founded.

Scott's final axiom, the Reflection schema, is identical to the above existence premise bearing the same name, and likewise does duty for ZF's Infinity and Replacement. Scott's system has the same strength as ZF.

[edit] Potter's theory

Potter (1990, 2004) introduced the idiosyncratic terminology described earlier in this entry, and discarded or replaced all of Scott's axioms except Reflection; the result is ZU. Russell's paradox is Potter's (2004) first theorem; Russell's paradox reproduces his very easy proof thereof, one requiring no set theory axioms. Thus Potter establishes from the very outset the need for a more restricted kind of collection, namely sets, that steers clear of Russell's paradox.

ZU, like ZF, cannot be finitely axiomatized. ZU differs from ZFC in that it:

  • Includes no axiom of extensionality because the usual extensionality principle follows from the definition of collection and an easy lemma;
  • Admits nonwellfounded sets. However Potter (2004) never invokes such sets, and no theorem in Potter would be overturned were Foundation or its equivalent added to ZU;
  • Includes no equivalents of Choice or the axiom schema of Replacement.

Hence ZU is equivalent to the Zermelo set theory of 1908, namely ZFC minus Choice, Replacement, and Foundation. The remaining differences between ZU and ZFC are mainly expositional.

What is the strength of ZfU, and ZFU relative to Z, ZF, and ZFC?

The natural numbers are not defined as a particular set within the iterative hierarchy, but as models of a "pure" Dedekind algebra. "Dedekind algebra" is Potter's name for a set closed under an unary injective operation, successor, whose domain contains a unique element, zero, absent from its range. Because all Dedekind algebras with the lowest possible birthdays are categorical (all models are isomorphic), any such algebra can proxy for the natural numbers.

The Frege–Russell definitions of the cardinal and ordinal numbers work in Scott-Potter set theory, because the equivalence classes these definitions require are indeed sets. Thus in ZU, an equivalence class of:

In ZFC, these definitions give rise to the Cantor and Burali-Forti paradox.

Although Potter (2004) devotes an entire appendix to proper classes, the strength and merits of Scott-Potter set theory relative to the well-known rivals to ZFC that admit proper classes, namely NBG and Morse–Kelley set theory, have yet to be explored.

Scott-Potter set theory resembles NFU in that the latter is a recently devised axiomatic set theory admitting both urelements and sets that are not well-founded. But the urelements of NFU, unlike those of ZU, play an essential role; they and the resulting restrictions on Extensionality make possible a proof of NFU's consistency relative to Peano arithmetic. But nothing is known about the strength of NFU relative to Creation+Separation, NFU+Infinity relative to ZU, and of NFU+Infinity+Countable Choice relative to ZU+Countable Choice.

Unlike nearly all writing on set theory in recent decades, Potter (2004) mentions mereological fusions. His collections are also synonymous with the "virtual sets" of Willard Quine and Richard Milton Martin: entities arising from the free use of the principle of comprehension, and that can never be admitted to the universe of discourse.

[edit] See also

[edit] References

  • George Boolos, 1971, "The iterative conception of set," Journal of Philosophy 68: 215–31. Reprinted in Richard Jeffrey and Burgess, J.,, eds., 1999. Logic, Logic, and Logic. Harvard Univ. Press.
  • Potter, Michael, 1990. Sets: An Introduction. Oxford Univ. Press.
  • ------, 2004. Set Theory and its Philosophy. Oxford Univ. Press.
  • Dana Scott, 1974, "Axiomatizing set theory" in Jech, Thomas, J., ed., Axiomatic Set Theory II, Proceedings of Symposia in Pure Mathematics 13. American Mathematical Society: 207–14.

[edit] External links

Retrieved from "http://en.wikipedia.org../../../s/c/o/Scott%E2%80%93Potter_set_theory_609e.html"