Tarski's theory of definability: Common themes in descriptive set theory, recursive function theory, classical pure logic, and finite-universe logic
Publication:598270
DOI10.1016/j.apal.2003.10.009zbMath1056.03019OpenAlexW2038489218MaRDI QIDQ598270
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
TarskidefinabilityBipartite graphsEhrenfeucht-Fraïssé gamesFinite model theoryClassical pure logicDescriptive set theoryFinite-universe logicInterpolation principlesPrefix hierarchiesRecursive function theorySeparation principles
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
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