Single Idea 18758

[catalogued under 5. Theory of Logic / K. Features of Logics / 7. Decidability]

Full Idea

Church showed that logic has a proof procedure, but no decision procedure. If an argument is invalid, there is a model with true premises and false conclusion, but the model will typically be infinite, so there is no way to display it concretely.

Clarification

'proof' is for validity; 'decisions' are for validity or invalidity

Gist of Idea

Validity is provable, but invalidity isn't, because the model is infinite

Source

report of Alonzo Church (A Note on the entscheidungsproblem [1936]) by Vann McGee - Logical Consequence 5

Book Reference

'Bloomsbury Companion to Philosophical Logic', ed/tr. Horsten,L/Pettigrew,R [Bloomsbury 2014], p.41