Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This is a follow-up to question Completeness vs Compactness in logic 68788. One common theme was that compactness in logic is a purely semantic notion, so should have no need of completeness.

The definition of compactness seems to depend in an irreducible way on the concept of a sentence, which appears to be a syntactic notion. So my question is: Is there any purely semantic definition of a sentence in first-order logic?

share|improve this question
    
I do not think that compactness in logic is a purely semantic notion. True, it is its semantic version which is nontrivial. That is why the semantic version is the one that is used widely. On the other hand, in logic, the notion itself, in a sense, is of syntactic origin. Actually, the usual way to infer the Compactness Theorem from the Completeness is to use the (trivial) syntactic version of compactness: a theory is consistent iff its every finite subset is consistent. –  Gyorgy Sereny Jun 30 '11 at 15:59

2 Answers 2

up vote 6 down vote accepted

One way to completely avoid syntax is to use Ehrenfeucht–Fraïssé games. If $\mathfrak{A}$ and $\mathfrak{B}$ are two structures with the same signature, then two $k$-tuples $\bar{a}$ and $\bar{b}$ from these respective structures satisfy the same type if and only if duplicator wins every finite length EF game between $(\mathfrak{A},\bar{a})$ and $(\mathfrak{B},\bar{b})$. This is a perfectly semantical way of defining the space $S_k$ of $k$-types for a given signature. One can show directly that the resulting space $S_k$ is a compact zero-dimensional space. The $k$-ary formulas of the language basically correspond to clopen sets in $S_k$. The compactness of $S_0$ is basically a restatement of the Compactness Theorem. Similarly, the Omitting Types Theorem is basically a restatement of the Baire Category Theorem for these spaces $S_k$.

This is the approach used by the Fraïssé school of model theory. One recent book which tries to promote this approach is Bruno Poizat's A Course in Model Theory.

share|improve this answer
    
Could you add a word about how to define the topology on the space of types? The reason I ask is that, as far as I know, in some other contexts (certain abstract elementary classes), one can have notions of types for which it's non-trivial to produce an associated notion of formula. I suspect this is related to the lack of compactness in AEC's and therefore won't be a problem in first-order logic, but at the moment I don't see the details. –  Andreas Blass Jun 30 '11 at 16:51
    
When working with a finite relational signature, the fixed length $n$ EF games define equivalence classes of types which form the basic open sets. This idea extends to general signatures, but there is a fair amount of fiddling to do... –  François G. Dorais Jun 30 '11 at 17:14

I suspect you've misunderstood what you quoted from the earlier question, since the semantics discussed there was the semantics of sentences, presupposing a notion of sentence. Nevertheless, your present question makes sense, and the (probably rather uninformative) answer is yes. The idea is to mimic semantically the definitions of formulas and their satisfaction, without ever mentioning the strings (or trees, etc.) of symbols that syntax deals with. Fix a vocabulary $L$ and (to avoid set-versus-class problems) consider only $L$-structures included in some fixed large set. "Formulas" will, in this approach, be certain collections of pairs $(A,s)$ where $A$ is a structure and $s$ is a finite tuple of elements of $A$. (The length of the tuple $s$ is to be the same for all pairs in a specific formula, but it may be different for different formulas). To define which collections of pairs count as formulas, one uses an inductive definition whose main clauses look like

  • If $R$ is an $n$-ary predicate symbol of $L$ then there is a formula consisting of exactly those pairs $(A,s)$ where $s$ is an $n$-tuple satisfying $R$ in $A$.

  • If $\phi$ and $\psi$ are two formulas in which the $n$-tuples have the same length, then $\phi\cup\psi$ is a formula.

  • The complement of any formula $\phi$, within the collection of all pairs $(A,s)$ whose tuples $s$ have the same length, is again a formula.

  • If $\phi$ is a formula whose tuples have non-zero length, say $n+1$, then there is a formula consisting of those pairs $(A,s)$ in which $s$ is an $n$-tuple and $(A,(a)^\frown s)\in\phi$ for some $a\in A$.

  • If $\phi$ is a formula whose tuples have length $n$ and if $f:\{1,2,\dots,m\}\to\{1,2,\dots,n\}$ then there is a formula consisting of exactly the pairs $(A,s\circ f)$ with $(A,s)\in\phi$.

The first clause says that atomic formulas are formulas; the next three say that the class of formulas is closed under the usual first-order constructors (disjunction, negation, and existential quantification), and the last allows trivial manipulations of the components in tuples (permutation, identifications, and adding dummy components).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.