Selection and Uniformization Problems in the Monadic Theory of Ordinals: A Survey
A formula ψ(Y) is a selector for a formula ϕ(Y) in a structure \(\mathcal{M}\) if there exists a unique Y that satisfies ψ in \(\mathcal{M}\) and this Y also satisfies ϕ. A formula ψ(X,Y) uniformizes a formula ϕ(X,Y) in a structure \(\mathcal{M}\) if for
- PDF / 529,252 Bytes
- 18 Pages / 430 x 660 pts Page_size
- 62 Downloads / 164 Views
Abstract. A formula ψ(Y ) is a selector for a formula ϕ(Y ) in a structure M if there exists a unique Y that satisfies ψ in M and this Y also satisfies ϕ. A formula ψ(X, Y ) uniformizes a formula ϕ(X, Y ) in a structure M if for every X there exists a unique Y such that ψ(X, Y ) holds in M and for this Y , ϕ(X, Y ) also holds in M. In this paper we survey some fundamental algorithmic questions and recent results regarding selection and uniformization, when the formulas ψ and ϕ are formulas of the monadic logic of order and the structure M = (α,
Data Loading...
