Saturday 15 September 2007

lo.logic - In what sense Fraissean view point shows Model Theory can be done without any formal syntax and deduction rule?

This is a partial answer to the above question. It is too long for a comment. I write it hear hoping to hear idea from those senior than me, and in case it is useful.



Here is some back ground, you might skip it if you are familiar with Poizat's definition:



There are two definitions of p- equivalent given in Poizat's A course in Model Theory, one via local isomorphism and the other via formal language. I think to compare the two view, it is crucial to compare this twos definitions.



Let ${bf M}=(M, R)$, ${bf N}=(N, S)$ structures with $ R, S$ $m$-ary relations.



Formal language definition:



Two $n$-tupe $vec{a},vec{b}$ are $p$-equivalent if and only if they satisfy the same formula in the language with quantifier rank at most $p$.



Local isomorphism definition: (Fraissean point of view)



A local isomorphism $s$ from $bf M$ to $bf N$ is defined to be an isomorphism between the a restriction of $bf M$ to a finite set $vec{a}$ to the restriction of $bf N$ to a finite set $vec{b}$.
0-isomorphism are local isomorphisms. A local isomorphism $s$ is a $p+1$-isomorphism iff



1) Forth condition: for any element $c$ in $M$ there is $d$ in $N$, and $t$ a $p$-isomorphism which map $c$ to$d$ and extends $s$.



2) Back condition: for any element $d$ in $N$ there is $c$ in $M$, and $t$ a $p$-isomorphism which map $c$ to $d$ and extends $s$.



Two $n$-tupe $vec{a},vec{b}$ are $p$-equivalent if there is a $p$ automorphism that maps one into another



First, we try to answer the question about syntax. We can unravel the local isomorphism definition to make it more like the language one, we get the following:



Two $n$-tupe $vec{a},vec{b}$ are $p$-equivalent iff all the following are satisfied



$ forall c_p in M, exists d_p in N,$ $ forall c_{p-1} in M, exists d_{p-1} in N,$...( all statements about $vec{a}, c_p, c_{p-1}, c_{p-2}, ...c_1 ) leftrightarrow$ ( all statements about $vec{b}, d_p, d_{p-1}, d_{p-2}, ...d_1 $ )



$ forall d_p in N, exists c_p in M,$ $ forall c_{p-1} in M, exists d_{p-1} in N,$...( all statements about $vec{a}, c_p, c_{p-1}, c_{p-2}, ...c_1 ) leftrightarrow$ ( all statements about $vec{b}, d_p, d_{p-1}, d_{p-2}, ...d_1 $ )



... ( all alternation between $c_i in M$ and $d_i in N$).



I think was wrong in the question. There was some genuine difference between the Fraissean view and the traditional view. In both cases we do use (formal or informal) quantifiers. But in traditional view the quantifier was on each domain and in the Fraissean view the quantifier is running back and forth between two domains. However, this difference does NOT shows Fraissean view point is anymore free from language than the traditional view. (The quantifier is even more complicated, in fact. But it is not the point).



I think the difference is like this: The traditional view point characterize local morphism in term of invariance. (In this case, it preserve the statements with at most p quantifier). The Fraissean view point describe the morphisms directly through induction.
Both are useful. The traditional view point is used in the proof of compactness (I don't know if this can be done in an easy way using the Fraissean view). The Fraissean view is important in many applications: To show that many theories are complete.



How about deduction rules?



I think we can define the deduction rule on the model side in an adhoc way (or may be not so adhoc) but it seems rather irrelevant here. So my previous concern is not correct.



I think that it is right that model theory can be developed independent of deduction rules. Perhaps that is because two equivalent statement are exactly the same to all model. I still don't understand exactly the relationship between Fraissean approach and this.

No comments:

Post a Comment