Scott's trick
Encyclopedia
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 (Forster 2003:182). It can be used to define representatives for ordinal numbers in Zermelo–Fraenkel set theory
. The method is named after Dana Scott
, who was the first to apply it.
Beyond the problem of defining set representatives for ordinal numbers, Scott's trick can be used to obtain representatives for cardinal numbers and when taking ultrapowers of proper classes in model theory.
is an equivalence class of sets, where two sets are equivalent if there is a bijection
between them. The difficulty is that every equivalence class of this relation is a proper class, and so the equivalence classes themselves cannot be directly manipulated in set theories, such as Zermelo–Fraenkel set theory, that only deal with sets. It is often desirable in the context of set theory to have sets that are representatives for the equivalence classes. These sets are then taken to "be" cardinal numbers, by definition.
In Zermelo–Fraenkel set theory with the axiom of choice, one way of assigning representatives to cardinal numbers is to associate each cardinal number with the least ordinal number of the same cardinality. But if the axiom of choice is not assumed, it is possible that some sets do not have the same cardinality as any ordinal number, and thus the cardinal numbers of those sets have no ordinal number as representative.
Scott's trick assigns representatives differently, using the fact that for every set A there is a least rank γA in the cumulative hierarchy when some set of the same cardinality as A appears. Thus one may define the representative of the cardinal number of A to be the set of all sets of rank γA that have the same cardinality as A. This definition assigns a representative to every cardinal number even when not every set can be well-ordered (an assumption equivalent to the axiom of choice). It can be carried out in Zermelo–Fraenkel set theory, without using the axiom of choice, but making essential use of the axiom of regularity
.
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...
, 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
Axiom of regularity
In mathematics, the axiom of regularity is one of the axioms of Zermelo-Fraenkel set theory and was introduced by...
is available (Forster 2003:182). It can be used to define representatives for ordinal numbers in Zermelo–Fraenkel set theory
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...
. The method is named after 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...
, who was the first to apply it.
Beyond the problem of defining set representatives for ordinal numbers, Scott's trick can be used to obtain representatives for cardinal numbers and when taking ultrapowers of proper classes in model theory.
Application to cardinalities
The use of Scott's trick for cardinal numbers shows how the method is typically employed. The initial definition of a cardinal numberCardinal number
In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality of sets. The cardinality of a finite set is a natural number – the number of elements in the set. The transfinite cardinal numbers describe the sizes of infinite...
is an equivalence class of sets, where two sets are equivalent if there is a bijection
Bijection
A 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...
between them. The difficulty is that every equivalence class of this relation is a proper class, and so the equivalence classes themselves cannot be directly manipulated in set theories, such as Zermelo–Fraenkel set theory, that only deal with sets. It is often desirable in the context of set theory to have sets that are representatives for the equivalence classes. These sets are then taken to "be" cardinal numbers, by definition.
In Zermelo–Fraenkel set theory with the axiom of choice, one way of assigning representatives to cardinal numbers is to associate each cardinal number with the least ordinal number of the same cardinality. But if the axiom of choice is not assumed, it is possible that some sets do not have the same cardinality as any ordinal number, and thus the cardinal numbers of those sets have no ordinal number as representative.
Scott's trick assigns representatives differently, using the fact that for every set A there is a least rank γA in the cumulative hierarchy when some set of the same cardinality as A appears. Thus one may define the representative of the cardinal number of A to be the set of all sets of rank γA that have the same cardinality as A. This definition assigns a representative to every cardinal number even when not every set can be well-ordered (an assumption equivalent to the axiom of choice). It can be carried out in Zermelo–Fraenkel set theory, without using the axiom of choice, but making essential use of the axiom of regularity
Axiom of regularity
In mathematics, the axiom of regularity is one of the axioms of Zermelo-Fraenkel set theory and was introduced by...
.