more from this thinker     |     more from this text

Single Idea 18108

[filed under theme 5. Theory of Logic / A. Overview of Logic / 5. First-Order Logic ]

Full Idea

First-order logic is not decidable. That is, there is no test which can be applied to any arbitrary formula of that logic and which will tell one whether the formula is or is not valid (as proved by Church in 1936).

Gist of Idea

First-order logic is not decidable: there is no test of whether any formula is valid

Source

David Bostock (Philosophy of Mathematics [2009], 5.5)

Book Ref

Bostock,David: 'Philosophy of Mathematics: An Introduction' [Wiley-Blackwell 2009], p.152

The 23 ideas with the same theme [logic where variables only refer to objects]:

22873 Liberalism should improve the system, and not just ameliorate it [Dewey]
21495 Theoretical and practical politics are both concerned with the best lives for individuals [Russell]
18956 Asserting first-order validity implicitly involves second-order reference to classes [Putnam]
10767 Elementary logic is complete, but cannot capture mathematics [Tharp]
13840 First-order logic is the strongest complete compact theory with Löwenheim-Skolem [Hacking]
13844 A limitation of first-order logic is that it cannot handle branching quantifiers [Hacking]
18108 First-order logic is not decidable: there is no test of whether any formula is valid [Bostock]
18109 The completeness of first-order logic implies its compactness [Bostock]
10478 Since first-order languages are complete, |= and |- have the same meaning [Hodges,W]
19315 In quantified language the components of complex sentences may not be sentences [Kirkham]
17788 First-order logic only has its main theorems because it is so weak [Mayberry]
13624 The 'triumph' of first-order logic may be related to logicism and the Hilbert programme, which failed [Shapiro]
13660 Maybe compactness, semantic effectiveness, and the Löwenheim-Skolem properties are desirable [Shapiro]
13662 First-order logic was an afterthought in the development of modern logic [Shapiro]
13673 The notion of finitude is actually built into first-order languages [Shapiro]
10588 First-order logic is Complete, and Compact, with the Löwenheim-Skolem Theorems [Shapiro]
10897 A first-order 'sentence' is a formula with no free variables [Zalabardo]
10986 Not all validity is captured in first-order logic [Read]
13534 In first-order logic syntactic and semantic consequence (|- and |=) nicely coincide [Wolf,RS]
13535 First-order logic is weakly complete (valid sentences are provable); we can't prove every sentence or its negation [Wolf,RS]
20100 Classical liberalism seeks freedom of opinion, of private life, of expression, and of property [Micklethwait/Wooldridge]
21122 Liberal Nationalism says welfare states and democracy needed a shared sense of nationality [Shorten]
22609 Philosophers accepted first-order logic, because they took science to be descriptive, not explanatory [Ingthorsson]