Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I came across the following theorem that for any class $K$ of truth assignments, $K\subseteq Mod(Th(K))$, and if $K$ is axiomatizable, then $K=Mod(Th(K))$. Together these seem to me to imply that there is some class $K$ such that $K\neq Mod(Th(K))$, however, I can't find any class $K$ that would verify my assumption.

I do know that $K$ would have to contain more than one truth assignment, since if $K$ were to have only one assignment $V$, $Th(V)$ has a unique model $V$, so then $K=V=Mod(Th(K))$. Does anyone know of any example where $K\neq Mod(Th(K))$, or at least how to construct one?

share|improve this question
1  
en.wikipedia.org/wiki/… have you seen that? I think it might be useful to your question, if I understood it correctly. –  Asaf Karagila Sep 13 '10 at 10:34
    
Thanks for the link! It's a little over my head, since I haven't had experience with first-order logic. Also, I was hoping to explicitly construct at least two atomic truth assignments, and then extend them to a general truth assignment, and then show that the theory the generate is also modeled by a third truth assignment, thus showing that $K\subset Mod(Th(K))$. I'm just not sure how easy this is, since it's very difficult for me to tell what sentences will be true for both truth assignment when we only have their atomic truth assignments defined. –  yunone Sep 13 '10 at 16:52

1 Answer 1

up vote 3 down vote accepted

Your use of the term "truth assignments" indicates that you are asking this question in the context of propositional logic, rather than the context of model theory and first order logic, where it often arises.

The answer is Yes, there are $K$ for which $K\neq Mod(Th(K))$.

In the propositional logic context, we have a collection $K$ of truth assignments of a fixed set of propositional variables to {true,false}. That is, $K$ is a set of rows in the truth table. In this case, $Th(K)$ is the set of propositional assertions true in all those rows, and $Mod(Th(K))$ is the set of all models of all those assertions. Since the rows appearing in $K$ do model all those assertions, we see that immediately that $K\subset Mod(Th(K))$.

But here is a counterexample showing that $K\neq Mod(Th(K))$ is possible. Suppose that there are infinitely many propositional variables $p_0,p_1,\ldots$, and let $K$ be the rows for which at most finitely many $p_n$ are true. In this case, I claim $K\neq Mod(Th(K))$. The reason is that any statement $\varphi$ involves only finitely many variables, and so if it is not tautological, that is, if it fails anywhere, then it will fail in a model for which only finitely many variables are true (just ignore all variables not in $\varphi$). Thus, $Th(K)$ includes only the tautologies, and so $Mod(Th(K))$ includes all truth assignments. So this is a counterexample.

It is not difficult to see that any counterexample will involve infinitely many propositional variables, since if there are only finitely many variables, then the assingments in $K$ can be explicitly described and the theory axiomatized.

In the context of first order logic, we take $K$ to be a set of first order structures, and there are numerous examples of $K$ not forming an elementary class, as in the link provided by Asaf. One example is the collection $K$ of all countably infinite structures (of a fixed consistent theory in a countable language). This will not be $Mod(Th(K))$, since by Lowenheim-Skolem, there are arbitrary large structures of any consistent theory.

share|improve this answer
    
Thanks for your answer, JDH. Just to clarify, are $p_0,p_1,\dots,$ all atomic sentence statements that usually come in the leftmost columns of a truth table, or are they all sentences in general? In the former, I see that if $\varphi$ is not a tautology, and contains $j$ variables, then at least one truth assignment in $K$ that is true for $n$ atomic sentences for some $0\leq n\leq j$ will be false for $\varphi$, and hence $\varphi\notin Th(K)$. I apologize if this is very elementary, I'm just trying to get a good footing. –  yunone Sep 13 '10 at 21:31
    
Yes, I mean the former; the $p_0, p_1,\ldots$ were meant to enumerate just the propositional variables, not all assertions. Now, the point is that any sentence $\varphi$ mentions only finitely many variables, and so if it fails in any propositional model, then we can set all other variables to false and thereby obtain a model of $\neg\varphi$ in which there are only finitely many propositional variables that are true. This is why $Th(K)$ consists of all tautologies. –  JDH Sep 13 '10 at 22:27

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.