more from this thinker     |     more from this text

Single Idea 13626

[filed under theme 5. Theory of Logic / B. Logical Consequence / 4. Semantic Consequence |= ]

Full Idea

It follows from Gödel's incompleteness theorem that the semantic consequence relation of second-order logic is not effective. For example, the set of logical truths of any second-order logic is not recursively enumerable. It is not even arithmetic.

Gist of Idea

Semantic consequence is ineffective in second-order logic

Source

Stewart Shapiro (Foundations without Foundationalism [1991], Pref)

Book Ref

Shapiro,Stewart: 'Foundations without Foundationalism' [OUP 1991], p.-16

A Reaction

I don't fully understand this, but it sounds rather major, and a good reason to avoid second-order logic (despite Shapiro's proselytising). See Peter Smith on 'effectively enumerable'.

Related Idea

Idea 10083 A set is 'effectively enumerable' if a computer could eventually list every member [Smith,P]

The 16 ideas with the same theme [fitting with the truth of some formulae]:

19237 Deduction is true when the premises facts necessarily make the conclusion fact true [Peirce]
13344 X follows from sentences K iff every model of K also models X [Tarski]
10694 Logical consequence is when in any model in which the premises are true, the conclusion is true [Tarski, by Beall/Restall]
10479 Logical consequence: true premises give true conclusions under all interpretations [Tarski, by Hodges,W]
13347 Validity is a conclusion following for premises, even if there is no proof [Bostock]
13348 It seems more natural to express |= as 'therefore', rather than 'entails' [Bostock]
13349 Γ|=φ is 'entails'; Γ|= is 'is inconsistent'; |=φ is 'valid' [Bostock]
10477 |= in model-theory means 'logical consequence' - it holds in all models [Hodges,W]
13626 Semantic consequence is ineffective in second-order logic [Shapiro]
13637 If a logic is incomplete, its semantic consequence relation is not effective [Shapiro]
10893 Γ |= φ for sentences if φ is true when all of Γ is true [Zalabardo]
10899 Γ |= φ if φ is true when all of Γ is true, for all structures and interpretations [Zalabardo]
21611 Formal semantics defines validity as truth preserved in every model [Williamson]
10695 Logical consequence is either necessary truth preservation, or preservation based on interpretation [Beall/Restall]
13240 A sentence follows from others if they always model it [Beall/Restall]
14506 'Roses are red; therefore, roses are colored' seems truth-preserving, but not valid in a system [Koslicki]