Scale (descriptive set theory)

Last updated November 28, 2020

In the mathematical discipline of descriptive set theory, a scale is a certain kind of object defined on a set of points in some Polish space (for example, a scale might be defined on a set of real numbers). Scales were originally isolated as a concept in the theory of uniformization,^[1] but have found wide applicability in descriptive set theory, with applications such as establishing bounds on the possible lengths of wellorderings of a given complexity, and showing (under certain assumptions) that there are largest countable sets of certain complexities.

Formal definition

Given a pointset A contained in some product space

A\subseteq X=X_{0}\times X_{1}\times \ldots X_{m-1}

where each X_k is either the Baire space or a countably infinite discrete set, we say that a norm on A is a map from A into the ordinal numbers. Each norm has an associated prewellordering, where one element of A precedes another element if the norm of the first is less than the norm of the second.

A scale on A is a countably infinite collection of norms

(\phi _{n})_{n<\omega }

with the following properties:

If the sequence x_i is such that

x_i is an element of A for each natural number i, and

x_i converges to an element x in the product space X, and

for each natural number n there is an ordinal λ_n such that φ_n(x_i)=λ_n for all sufficiently large i, then

x is an element of A, and

for each n, φ_n(x)≤λ_n.^[2]

By itself, at least granted the axiom of choice, the existence of a scale on a pointset is trivial, as A can be wellordered and each φ_n can simply enumerate A. To make the concept useful, a definability criterion must be imposed on the norms (individually and together). Here "definability" is understood in the usual sense of descriptive set theory; it need not be definability in an absolute sense, but rather indicates membership in some pointclass of sets of reals. The norms φ_n themselves are not sets of reals, but the corresponding prewellorderings are (at least in essence).

The idea is that, for a given pointclass Γ, we want the prewellorderings below a given point in A to be uniformly represented both as a set in Γ and as one in the dual pointclass of Γ, relative to the "larger" point being an element of A. Formally, we say that the φ_n form a Γ-scale on A if they form a scale on A and there are ternary relations S and T such that, if y is an element of A, then

\forall n\forall x(\varphi _{n}(x)\leq \varphi _{n}(y)\iff S(n,x,y)\iff T(n,x,y))

where S is in Γ and T is in the dual pointclass of Γ (that is, the complement of T is in Γ).^[3] Note here that we think of φ_n(x) as being ∞ whenever x∉A; thus the condition φ_n(x)≤φ_n(y), for y∈A, also implies x∈A.

The definition does not imply that the collection of norms is in the intersection of Γ with the dual pointclass of Γ. This is because the three-way equivalence is conditional on y being an element of A. For y not in A, it might be the case that one or both of S(n,x,y) or T(n,x,y) fail to hold, even if x is in A (and therefore automatically φ_n(x)≤φ_n(y)=∞).

Applications

This section is yet to be written

Scale property

The scale property is a strengthening of the prewellordering property. For pointclasses of a certain form, it implies that relations in the given pointclass have a uniformization that is also in the pointclass.

Periodicity

This section is yet to be written

Notes

↑ Kechris and Moschovakis 2008:28
↑ Kechris and Moschovakis 2008:37
↑ Kechris and Moschovakis 2008:37, with harmless reworking

Related Research Articles

In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly unchanged in a number of metamathematical investigations, including research into fundamental questions of whether number theory is consistent and complete.

In mathematics, an $n$ -sphere is a topological space that is homeomorphic to a standard $n$ -sphere, which is the set of points in $(n + 1)$ -dimensional Euclidean space that are situated at a constant distance $r$ from a fixed point, called the center. It is the generalization of an ordinary sphere in the ordinary three-dimensional space. The "radius" of a sphere is the constant distance of its points to the center. When the sphere has unit radius, it is usual to call it the unit $n$ -sphere or simply the $n$ -sphere for brevity. In terms of the standard norm, the $n$ -sphere is defined as

In the mathematical discipline of set theory, forcing is a technique for proving consistency and independence results. It was first used by Paul Cohen in 1963, to prove the independence of the axiom of choice and the continuum hypothesis from Zermelo–Fraenkel set theory.

In axiomatic set theory and the branches of mathematics and philosophy that use it, the axiom of infinity is one of the axioms of Zermelo–Fraenkel set theory. It guarantees the existence of at least one infinite set, namely a set containing the natural numbers. It was first published by Ernst Zermelo as part of his set theory in 1908.

In mathematical logic, descriptive set theory (DST) is the study of certain classes of "well-behaved" subsets of the real line and other Polish spaces. As well as being one of the primary areas of research in set theory, it has applications to other areas of mathematics such as functional analysis, ergodic theory, the study of operator algebras and group actions, and mathematical logic.

Finite model theory (FMT) is a subarea of model theory (MT). MT is the branch of mathematical logic which deals with the relation between a formal language (syntax) and its interpretations (semantics). FMT is a restriction of MT to interpretations on finite structures, which have a finite universe.

Independence-friendly logic is an extension of classical first-order logic (FOL) by means of slashed quantifiers of the form $and . The intended reading of is "there is a which is functionally independent from the variables in ". IF logic allows one to express more general patterns of dependence between variables than those which are implicit in first-order logic. This greater level of generality leads to an actual increase in expressive power; the set of IF sentences can characterize the same classes of structures as existential second-order logic. For example, it can express branching quantifier sentences, such as the formula which expresses infinity in the empty signature; this cannot be done in FOL. Therefore, first-order logic cannot, in general, express this pattern of dependency, in which depends only on and, and depends only on and . IF logic is more general than branching quantifiers, for example in that it can express dependencies that are not transitive, such as in the quantifier prefix .$

In set theory, a prewellordering is a binary relation $that is transitive, connex, and wellfounded. In other words, if is a prewellordering on a set, and if we define by$

In set theory, a branch of mathematics, the axiom of uniformization is a weak form of the axiom of choice. It states that if $is a subset of, where and are Polish spaces, then there is a subset of that is a partial function from to, and whose domain equals$

In descriptive set theory, an inductive set of real numbers is one that can be defined as the least fixed point of a monotone operation definable by a positive Σ¹_n formula, for some natural number n, together with a real parameter.

Determinacy is a subfield of set theory, a branch of mathematics, that examines the conditions under which one or the other player of a game has a winning strategy, and the consequences of the existence of such strategies. Alternatively and similarly, "determinacy" is the property of a game whereby such a strategy exists.

Effective descriptive set theory is the branch of descriptive set theory dealing with sets of reals having lightface definitions; that is, definitions that do not require an arbitrary real parameter. Thus effective descriptive set theory combines descriptive set theory with recursion theory.

In model theory and related areas of mathematics, a type is an object that describes how a element or finite collection of elements in a mathematical structure might behave. More precisely, it is a set of first-order formulas in a language L with free variables x₁, x₂,…, x_n that are true of a sequence of elements of an L-structure $. Depending on the context, types can be complete or partial and they may use a fixed set of constants, A, from the structure . The question of which types represent actual elements of leads to the ideas of saturated models and omitting types .$

In the mathematical discipline of set theory, there are many ways of describing specific countable ordinals. The smallest ones can be usefully and non-circularly expressed in terms of their Cantor normal forms. Beyond that, many ordinals of relevance to proof theory still have computable ordinal notations. However, it is not possible to decide effectively whether a given putative ordinal notation is a notation or not ; various more-concrete ways of defining ordinals that definitely have notations are available.

Constructive set theory is an approach to mathematical constructivism following the program of axiomatic set theory. The same first-order language with " $" and " " of classical set theory is usually used, so this is not to be confused with a constructive types approach. On the other hand, some constructive theories are indeed motivated by their interpretability in type theories.$

In the mathematical field of descriptive set theory, a pointclass is a collection of sets of points, where a point is ordinarily understood to be an element of some perfect Polish space. In practice, a pointclass is usually characterized by some sort of definability property; for example, the collection of all open sets in some fixed collection of Polish spaces is a pointclass.

In operator theory, a bounded operator T: X → Y between normed vector spaces X and Y is said to be a contraction if its operator norm ||T|| ≤ 1. Every bounded operator becomes a contraction after suitable scaling. The analysis of contractions provides insight into the structure of operators, or a family of operators. The theory of contractions on Hilbert space is largely due to Béla Szőkefalvi-Nagy and Ciprian Foias.

In recursion theory, hyperarithmetic theory is a generalization of Turing computability. It has close connections with definability in second-order arithmetic and with weak systems of set theory such as Kripke–Platek set theory. It is an important tool in effective descriptive set theory.

Pocket set theory (PST) is an alternative set theory in which there are only two infinite cardinal numbers, ℵ₀ and c. The theory was first suggested by Rudy Rucker in his Infinity and the Mind. The details set out in this entry are due to the American mathematician Randall M. Holmes.

The Moschovakis coding lemma is a lemma from descriptive set theory involving sets of real numbers under the axiom of determinacy. The lemma was developed and named after the mathematician Yiannis N. Moschovakis.

References

Moschovakis, Yiannis N. (1980), Descriptive Set Theory, North Holland, ISBN 0-444-70199-0
Kechris, Alexander S.; Moschovakis, Yiannis N. (2008), "Notes on the theory of scales", in Kechris, Alexander S.; Benedikt Löwe; Steel, John R. (eds.), Games, Scales and Suslin Cardinals: The Cabal Seminar, Volume I, Cambridge University Press, pp. 28–74, ISBN 978-0-521-89951-2

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.

[1] Kechris and Moschovakis 2008:28

[2] Kechris and Moschovakis 2008:37

[3] Kechris and Moschovakis 2008:37, with harmless reworking

[1]

[2]

[3]