[Solved]: Definability of Truth Assignments

Problem Detail: 

I have a question about definability of truth assignments. Suppose that I am working in the context of propositional logic. Let me give some definitions first.

Let $L$ be a propositional language with the set $Prop_{L}$ of propositional variables. A truth assignment is a map $v\colon Prop_{L}\to\{F,T\}$. Denote the collection of truth assignments in $L$ by $TA_{L}$. Note that in a language $L$ with $|Prop_{L}|=n$ for some $n\in\mathbb{N}$, $|TA_{L}|=2^{n}$, while in a language with $|Prop_{L}|=\aleph_{0}$ (denumerably many), $|TA_{L}|=2^{\aleph_{0}}=\mathfrak{c}$ (continuum many).

Definition 1. Let $\Sigma$ be a set of propositional formulas. The set of models of $\Sigma$ is $$Mod(\Sigma):=\{v:v\ \mbox{is a truth assignment and $v(\varphi)=T$ for each $\varphi\in\Sigma$}\}.$$

Definition 2. Let $K\subseteq TA_{L}$. Then $K$ is definable if $K=Mod(\Sigma)$ for some set $\Sigma$ of formulas.

I have tried to prove a couple of things. In a propositional language with only finitely many propositional variables, any set of truth assignments is definable. Now, I want to show that, in a propositional language with denumerably many propositional variables, any finite set of truth assignments is definable. Imitating the idea in the proof about finite language, I have an outline of the proof about infinite language. Here is the detail:

Convention. Let $p$ be a propositional variable and $v$ a truth assignment. Define $$ p^{v}:= \begin{cases} p &\mbox{if}\ v(p)=T;\\ \neg p &\mbox{otherwise}. \end{cases} $$ Then it can be seen easily that $\widehat{v}(p^{v})=T$. (Here $\widehat{v}$ denotes the extension of $v$ to the set of propositional formulas.)

Claim. In a language $L$ with $|Prop_{L}|=\aleph_{0}$, any finite set of truth assignments is definable.

Proof. Assume that $Prop_{L}=\{p_{1},p_{2},\ldots\}$. Let $K\subseteq TA_{L}$. Assume that $K$ is finite. Then $K=\{v_{1},v_{2},\ldots,v_{k}\}$ for some $k\in\mathbb{N}$. Let $1\leq i\leq k$. For each $j\in\mathbb{N}$, define $$\varphi^{i}_{j}:=p^{v_{i}}_{1}\wedge p^{v_{i}}_{2}\wedge\cdots\wedge p^{v_{i}}_{j}$$ and define $$\chi_{j}:=\varphi^{1}_{j}\vee\varphi^{2}_{j}\vee\cdots\vee\varphi^{k}_{j}.$$ Let $\Sigma=\{\chi_{j}:j\in\mathbb{N}\}$. Claim that $K=Mod(\Sigma)$.

Now, the part $K\subseteq Mod(\Sigma)$ is easy. What is hard for me is the reverse inclusion: any truth assignment satisfying $\Sigma$ must be $v_{i}$ for some $1\leq i\leq k$. Since I am dealing with infinitely many propositional variables, to show that two truth assignments coincide is to show that they agree on infinitely many propositional variables. Yet I have no idea how to show that, because truth assignments in $K$ seem to involve only finitely many propositional variables. Could anyone please advise me about this?

Any suggestions would be greatly appreciated :)

Asked By : Pachara

Answered By : Kaveh

Let $T=\{\tau_1,\cdots, \tau_k\}$ be the set of truth assignments. Consider the tree of the truth assignments $2^\omega$.

Consider the formula $\Gamma_T = \{ \underset{\tau \in T}\lor \tau_{|n} \mid n \in \omega\}$ where $\tau_{|n}$ is the formula that expresses $\tau$ up to atom $p_n$, i.e. $\underset{i\leq n}\wedge l_i(\tau)$ where $l_i(\tau) = \begin{cases} p_i & \tau(p_i)=\top \\ \lnot p_i & \tau(p_i)= \bot \end{cases}$.

It is easy to show that every $\tau \in T$ we have $\tau \vDash \Gamma_T$.

For any $\tau \notin T$, there is some $n\in \omega$ such that $\tau_{|n}$ is different from those in $T$ and therefore $\tau$ does not satisfy $\underset{\tau \in T}\lor \tau_{|n}$ and therefore $\tau\nvDash \Gamma_T$.

There is a topological characterization of the sets of truth assignments that can be defined. Consider $2^\omega$ as space of points with product topology. Consider the sets of points that can be captured using sets of formulas. They are closed under finite unions (consider the disjunctions of the pairs of formulas from the product) and arbitrary intersections (union of two sets).

You may be interested in Stone duality and type (model theory).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12425