Timeline for Completeness vs Compactness in logic
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 1, 2019 at 5:45 | comment | added | Michael Hardy | @AndreasBlass : ok, That's an exercise that will wait until tomorrow$\,\ldots \qquad$ | |
| Jan 1, 2019 at 2:34 | comment | added | Andreas Blass | @MichaelHardy As far as I can see, recursive enumerability of the valid sentences gives you completeness in the form "Any logical consequence of any finite set of hypotheses is deducible from those hypotheses (in a suitable deductive system)." But the stronger version of completeness, omitting "finite", seems not to follow unless you also have compactness. | |
| Dec 31, 2018 at 20:53 | comment | added | Michael Hardy | Isn't the recursive enumerability of all valid sentences essentially the same thing as the completeness of some system of proof for which a proof-checking algorithm exists, that being what is asserted by the completeness theorem? | |
| Jun 27, 2011 at 15:01 | comment | added | Emil Jeřábek | The "other fact" is not just recursive enumerability of valid sentences, but of the finitary consequence operator (in other words, finite strong completeness). This distinction is of utmost importance in logical systems lacking the deduction theorem. | |
| Jun 26, 2011 at 11:27 | comment | added | Joel David Hamkins | This is how the Wizard of Oz treats A. Miller's Micky Mouse system, which I mention in the answer mathoverflow.net/questions/9309/…, which Qiaochu linked to above. | |
| Jun 26, 2011 at 4:29 | history | answered | Andreas Blass | CC BY-SA 3.0 |