Timeline for In model theory, does compactness easily imply completeness?
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 30, 2023 at 11:50 | history | edited | Martin Sleziak | CC BY-SA 4.0 |
http -> https (the question was bumped anyway)
|
| S Jul 30, 2023 at 11:18 | history | suggested | C7X | CC BY-SA 4.0 |
MathJaxify
|
| Jul 30, 2023 at 5:02 | review | Suggested edits | |||
| S Jul 30, 2023 at 11:18 | |||||
| Sep 6, 2014 at 19:27 | comment | added | zpavlinovic | @JoelDavidHamkins My understanding of tatulogical validities was wrong. Sorry for that. | |
| Sep 6, 2014 at 11:41 | comment | added | Joel David Hamkins | @bellpeace I don't follow your remarks. The set of tautological validities is not computable, but only computably enumerable, and one way to see this is by finding a computable list of validites $\Delta$ that prove all validities. Are you questioning whether Enderton's proof of completeness is correct? | |
| Sep 6, 2014 at 3:58 | comment | added | zpavlinovic | A bit late, but I have a comment on the $MM$ system. In Enderton's book, he basically makes the proof (for FOL) $\Sigma \vdash \alpha$ iff $\Sigma \cup \Delta$ tautologically implies $\alpha$. $\Delta$ are his axioms. The proof he gives is just as the one here for system $MM$. But, tautological validity is computable and provable, so why does his proof do not constitute a proof of completeness for FOL also? | |
| Jan 25, 2010 at 3:47 | history | edited | Joel David Hamkins | CC BY-SA 2.5 |
typo
|
| Jan 25, 2010 at 3:41 | comment | added | Joel David Hamkins | I added a description of A. Miller's entertaining MM system at the end. | |
| Jan 25, 2010 at 3:40 | history | edited | Joel David Hamkins | CC BY-SA 2.5 |
Added material from Millers' notes about MM
|
| Jan 7, 2010 at 4:46 | vote | accept | Pete L. Clark | ||
| Dec 18, 2009 at 23:42 | comment | added | Joel David Hamkins | What I meant about Completeness being a foregone conclusion, is that when you start proving Completeness, you periodically need to know various things about the formal system you defined. So, if you are not so interested in having the optimal proof system, then you can simply add them to the system on the fly as the proof proceeds. Of course, this method only works because the theorem is true! But it does mean that you don't have to remember the exact proof system in advance, as long as you remember the essential proof outline. | |
| Dec 18, 2009 at 23:38 | comment | added | Joel David Hamkins | Yes, that proof was merely about the finite obstacle, which Compactness provides. The situations where one seems to need Completeness over Compactness, as I mentioned in my answer, have to do with the effectivity of the finite obstacle, for example, when if the question concerns the computability of a theory or model, or whether there is a computable procedure for eliminating quantifiers, and so on. | |
| Dec 18, 2009 at 23:03 | comment | added | Pete L. Clark | Come to think of it, I guess you can take F a nonprincipal ultrafilter on the set of primes, define for each prime number p an algebraically closed field of characteristic p, and let K be the ultraproduct of the K_p's with respect to F. Then Los' theorem asserts that any first order sentence that is true in every algebraically closed field of positive characteristic is true in every algebraically closed field of characteristic zero. | |
| Dec 18, 2009 at 22:13 | comment | added | Pete L. Clark | Also, for whatever it's worth, I don't understand your remark about completeness being a foregone conclusion. It is certainly not clear that incompleteness can be remedied by adding further axioms on the fly (c.f. the Incompleteness Theorem!). | |
| Dec 18, 2009 at 22:10 | comment | added | Pete L. Clark | I know that model theorists tend to view compactness as of primary importance whereas completeness is seen to belong more to proof theory and logic in general. However, both of the above texts appeal to completeness in places where it is not so obvious to me how to use compactness instead. See for instance Corollary 2.5 of msri.org/communications/books/Book39/files/marker.pdf (this article is a shorter, freely available precursor to Marker's book). Do you know of an introductory model theory text which is "completeness free"? | |
| Dec 18, 2009 at 21:44 | history | answered | Joel David Hamkins | CC BY-SA 2.5 |