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.03019MaRDI 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
Tarski; definability; Bipartite graphs; Ehrenfeucht-Fraïssé games; Finite model theory; Classical pure logic; Descriptive set theory; Finite-universe logic; Interpolation principles; Prefix hierarchies; Recursive function theory; Separation principles
05C90: Applications of graph theory
03E15: Descriptive set theory
01A60: History of mathematics in the 20th century
03B70: Logic in computer science
03B10: Classical first-order logic
03-03: History of mathematical logic and foundations
03C13: Model theory of finite structures
03D20: Recursive functions and relations, subrecursive hierarchies
03C40: Interpolation, preservation, definability
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
