A transformation scheme for infinitary first-order combinatorics presenting computational level of expressiveness in predicate logic

DOI10.1134/S1995080215040137MaRDI QIDQ266237zbMATH OpenOpenAlexFDO

Authors Mikhaĭl G. Peretyat'kin

Publication date 13 April 2016

Published in Lobachevskii Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/s1995080215040137

zbMATH Keywords

c.e. Boolean algebrafinitely axiomatizable theoryfirst-order logicincomplete theorymodel-theoretic propertyTarski-Lindenbaum algebraTuring computability

Mathematics Subject Classification ID

Basic properties of first-order languages and structures (03C07) Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45)

Recommendations

• scientific article; zbMATH DE number 4037817
• Combinatorics of first order structures and propositional proof systems
• On the definitional embeddability of the combinatory logic theory into the first-order predicate calculus
• Transformations of logic programs on infinite lists
• Translation of first order formulas into ground formulas via a completion theory
• Systems of illative combinatory logic complete for first-order propositional and predicate calculus
• A formal system of first-order predicate calculus with infinitely long expressions
• Formalized proofs of the infinity and normal form predicates in the first-order theory of rewriting
• An algorithm for dual transformation in first-order logic
• Completeness of two systems of illative combinatory logic for first-order propositional and predicate calculus

Cites work

• scientific article; zbMATH DE number 3784831 (Why is no real title available?)
• scientific article; zbMATH DE number 1007358 (Why is no real title available?)
• scientific article; zbMATH DE number 934778 (Why is no real title available?)
• scientific article; zbMATH DE number 1450824 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• Arithmetic hierarchy and ideals of enumerated Boolean algebras
• The Tarski-Lindenbaum algebra of the class of all strongly constructivizable countable saturated models

Cited in

(4)

• Composition under distributive natural transformations: or, when predicate abstraction is impossible
• scientific article; zbMATH DE number 1396671 (Why is no real title available?)
• Combinatorial expressions and lower bounds
• Fundamental significance of the finitary and infinitary semantic layers and characterization of the expressive power of first-order logic

This page was built for publication: A transformation scheme for infinitary first-order combinatorics presenting computational level of expressiveness in predicate logic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q266237)