Tarski's theory of definability: Common themes in descriptive set theory, recursive function theory, classical pure logic, and finite-universe logic

DOI10.1016/j.apal.2003.10.009zbMath1056.03019OpenAlexW2038489218MaRDI QIDQ598270

J. W. Addison

Publication date: 6 August 2004

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2003.10.009

zbMATH Keywords

TarskidefinabilityBipartite graphsEhrenfeucht-Fraïssé gamesFinite model theoryClassical pure logicDescriptive set theoryFinite-universe logicInterpolation principlesPrefix hierarchiesRecursive function theorySeparation principles

Mathematics Subject Classification ID

Applications of graph theory (05C90) Descriptive set theory (03E15) History of mathematics in the 20th century (01A60) Logic in computer science (03B70) Classical first-order logic (03B10) History of mathematical logic and foundations (03-03) Model theory of finite structures (03C13) Recursive functions and relations, subrecursive hierarchies (03D20) Interpolation, preservation, definability (03C40)

Related Items

On the ‘definability of definable’ problem of Alfred Tarski, Part II ⋮ A field guide to equational logic ⋮ The Craig interpolation theorem in abstract model theory ⋮ THE PREHISTORY OF THE SUBSYSTEMS OF SECOND-ORDER ARITHMETIC

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A general method to construct oracles realizing given relationships between complexity classes
• Separation principles in the hierarchies of classical and effective descriptive set theory
• Determinateness and the separation property
• Separation principles and the axiom of determinateness
• Les opérations logiques et les ensembles projectifs
• Address at the Princeton University Bicentennial Conference on Problems of Mathematics (December 17–19, 1946), By Alfred Tarski
• Separation principles in the hierarchy theory of pure first-order logic
• Sur les théorèmes de séparation dans la Théorie des ensembles
• A problem concerning the notion of definability
• On definable sets of positive integers
• Recursive Predicates and Quantifiers