Undecidability without arithmetization

DOI10.1007/S11225-005-2976-1MaRDI QIDQ1780896zbMATH OpenOpenAlexFDO

Authors Andrzej Grzegorczyk

Publication date 14 June 2005

Published in Studia Logica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11225-005-2976-1

zbMATH Keywords

Alfred TarskiarithmetizationconcatenationdecidabilitydiscernibilityKurt Gödelrepresentability

Mathematics Subject Classification ID

Classical first-order logic (03B10) Decidability of theories and sets of sentences (03B25)

Review text

The author gives a new natural and transparent proof of the undecidability of first-order predicate calculus which does not use natural numbers. Instead of arithmetic, Tarski's theory of concatenation is used.

Recommendations

• Logical undecidabilities made easy
• First-order Frege theory is undecidable
• Decidability without mathematics
• Growing commas. A study of sequentiality and concatenation
• scientific article; zbMATH DE number 4210102

Cited in

(34)

• Growing commas. A study of sequentiality and concatenation
• The logical strength of compositional principles
• On arithmetical first-order theories allowing encoding and decoding of lists
• On decidability of theories of regular languages
• Weak essentially undecidable theories of concatenation
• Bases for structures and theories. I.
• On undecidability of concatenation theory for one-symbol languages
• On theory of regular languages with the Kleene star operation
• First-order concatenation theory with bounded quantifiers
• The scope of Gödel's first incompleteness theorem
• Consistency and the theory of truth
• Some proofs of undecidability of arithmetic
• Ein Direkter Beweis für die Allgemein‐Rekursive Unlösbarkeit des Entscheidungsproblems des Prädikatenkalküls der Ersten Stufe mit Identität
• The Gödel class with identity is unsolvable
• Logical undecidabilities made easy
• Arithmetic on semigroups
• The paradox of the knower revisited
• Weak theories of concatenation and arithmetic
• Mutual interpretability of Robinson arithmetic and adjunctive set theory with extensionality
• Weak theories of concatenation and minimal essentially undecidable theories. An encounter of \(\mathsf{WTC}\) and \(\mathsf{S2S}\)
• Current research on Gödel's incompleteness theorems
• Finding the limit of incompleteness. I
• Mathematical intuition and natural numbers: a critical discussion
• Peano Corto and Peano Basso: a study of local induction in the context of weak theories
• scientific article; zbMATH DE number 2236644 (Why is no real title available?)
• Undecidable sentences generated by semantic paradoxes
• First-order Frege theory is undecidable
• Decidability without mathematics
• INTERLEAVING LOGIC AND COUNTING
• A weak theory of building blocks
• Quantifier-free induction for lists
• On elementary theories of weighted and labelled trees
• A weak first-order theory of sequences
• Structuralism and meta-mathematics

This page was built for publication: Undecidability without arithmetization

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