I'm not expert in mathematical logic. I have an elementary question.
Are "atomic diagram" and "quantifier-free type" the same?
(I.e. if A is a finite subset of a given structure, then does the following statement hold? $diag(A)=qtp(A)$)
I'm not expert in mathematical logic. I have an elementary question.
Are "atomic diagram" and "quantifier-free type" the same?
(I.e. if A is a finite subset of a given structure, then does the following statement hold? $diag(A)=qtp(A)$)
The atomic diagram $\text{diag}(A)$ and the quantifier-free type $\text{qftp}(A)$ are not literally the same, but they encode exactly the same information.
Why they're different:
When we form the atomic diagram, we introduce a new constant symbol $c_a$ for every element $a\in A$. So the atomic diagram is a set of sentences (with no free variables) in the language $L\cup \{c_a\mid a\in A\}$. On the other hand, when we form the quantifier-free type, we use a set of variables, one, $x_a$, for every element $a\in A$. So the quantifier-free type is a set of formulas in the language $L$ with free variables from $\{x_a\mid a\in A\}$. In practice, this distinction is purely cosmetic: there is a bijection between sentences in the language $L\cup \{c_a\mid a\in A\}$ and formulas in the language $L$ with free variables from $\{x_a\mid a\in A\}$, given by substituting $x_a$ for $c_a$ wherever it appears. [Note: It is often the convention to index free variables appearing in types as $x_1,\dots,x_n$ (if there are finitely many) or $\langle x_\alpha \rangle_{\alpha<\beta}$ for some ordinal $\beta$ (in the general case that there are infinitely many). Again, it's easy to make the translation from variables indexed by elements of $A$ to variables indexed by numbers/ordinals, just by picking a well-ordering of $A$. If your convention is that types must have only finitely many free variables, then then $\text{qftp}(A)$ only makes sense for finite $A$.]
The other difference between $\text{diag}(A)$ and $\text{qftp}(A)$ is that the atomic diagram contains all those atomic and negated atomic sentences which are true of $A$, while the quantifier-free type contains all those quantifier-free formulas which are true of $A$; this is a wider class of formulas. For example, $R(x,y)\land (x = y \lor \lnot P(x))$ is quantifier-free but not atomic.
Why they encode the same information:
Every atomic and negated atomic formula is quantifier-free, so if a sentence $\psi(c_{a_1},\dots,c_{a_n})$ is in $\text{diag}(A)$, the corresponding formula $\psi(x_{a_1},\dots,x_{a_n})$ is in $\text{qftp}(A)$. In the other direction, every quantifier-free formula is a Boolean combination of atomic formulas. So once you know the truth value of all the atomic formulas, you know the truth value of all the quantifier-free formulas. In other words, if a quantifier-free formula $\varphi(x_{a_1},\dots,x_{a_n})$ is in $\text{qftp}(A)$, then $\text{diag}(A)\vdash \varphi(c_{a_1},\dots,c_{a_n})$.