3
$\begingroup$

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 :)

$\endgroup$

migrated from cstheory.stackexchange.com Jun 2 '13 at 5:35

This question came from our site for theoretical computer scientists and researchers in related fields.

  • $\begingroup$ You have not defined the set of all truth assignments. Does it consist of maps from all the denumerable variables to truth values? In that case, no singleton assignment is definable. Or do you mean the disjoint union of assignments over every finite subsets of all variables? In this case your class of models looks quite different. $\endgroup$ – Vijay D Jun 1 '13 at 8:09
  • $\begingroup$ Thank you @Vijay D for a comment. I've edited and added some details to make it clearer. $\endgroup$ – Pachara Jun 1 '13 at 8:40
  • $\begingroup$ The claim does not hold. You are assuming that the formulae contain only finitely many variables, but if there are infinitely many variables, you would need infinitely long formulae. Consider specific examples. The assignment with even indexed variables being true and others being false. How will you define this singleton set? $\endgroup$ – Vijay D Jun 1 '13 at 22:34
  • $\begingroup$ @Vijay D, He tackles this problem by asking that infinitely many formulae are true, each forcing the value of variables numbered up to bigger and bigger bound. So each formula is finite, but their conjunction (in $\Sigma$) forces the value of infinitely many variables $\endgroup$ – Denis Jun 1 '13 at 23:11
  • $\begingroup$ It looks like an exercise in propositional logic and easy to solve if you look at them as paths in $2^\omega$. What is the motivation for the question? $\endgroup$ – Kaveh Jun 2 '13 at 0:26
4
$\begingroup$

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).

$\endgroup$
  • 2
    $\begingroup$ To finish the topological characterization that Kaveh is hinting at: notice that the atomic propositions denote precisely a compact-open subbase for the product topology. Therefore, a formula will always denote a compact-open subset of $2^\omega$, and so will finitely many formulas (just make a big conjunction). A model described by denumerably many formulas will always be a closed set (in fact also a $G_\delta$-set). $\endgroup$ – Andrej Bauer Jun 2 '13 at 19:34
1
$\begingroup$

Your proof seems ok, by the following argument:

Let $v$ be a truth assignement satisfying $\Sigma$. Then for each $j\in\mathbb{N}$, $v$ has to satisfy at least one of the $\varphi_j^i$ (where $i\in[1,k]$).

Therefore, there is $i\in[1,k]$ such that infinitely many of the $\varphi_j^i$ are satisfied by $v$. This is enough to conclude that $v=v_i$.

$\endgroup$
  • $\begingroup$ Well, I'm still wondering how to choose such $i$. Since $v$ satisfies $\Sigma$, then for each $j\in\mathbb{N}$, $v$ satisfies at least one of the $k$ disjuncts in $\chi_{j}$, that is, $\{i\in[1,k]:v(\varphi^{i}_{j})=T\}\neq\varnothing$. Then I'm stuck here, having no idea how to proceed. Could you please hint more about this? $\endgroup$ – Pachara Jun 1 '13 at 13:37
  • 1
    $\begingroup$ when you choose infinitely many times from a finite set, you must choose the same element infinitely many times. Here each $j\in\mathbb{N}$ chooses an $i\in[1,k]$, therefore infinitely many $j$'s are choosing the same $i$. $\endgroup$ – Denis Jun 1 '13 at 14:28
  • $\begingroup$ Here is my conclusion. Hope it works this time :P ...For each $j\in\mathbb{N}$, since $\{i\in[1,k]:v(\varphi^{i}_{j})=T\}\neq\varnothing$, let $m_{j}=\max\{i\in[1,k]:v(\varphi^{i}_{j})=T\}$. Let $a=\max\{m_{j}:j\in\mathbb{N}\}$. Then $v(\varphi^{a}_{j})=T$ for any $j\in\mathbb{N}$. Thus, $v=v_{a}$. Thank you very much, @dkuper, for your kind help. $\endgroup$ – Pachara Jun 1 '13 at 15:28
  • 1
    $\begingroup$ Not exactly, the principle is to choose for $a$ any $m_j$ which appears infinitely often (for instance the maximum). If you want to say it formally, you can say that $m$ is a function:$\mathbb{N}\to[1,k]$ which to $j$ associate $m_j$. Then, the sets $m^{-1}(i)$ for $1\leq i\leq k$ form a partition of $\mathbb{N}$. So take $a$ maximal such that $m^{-1}(a)$ is infinite, and you get $v=v_a$. $\endgroup$ – Denis Jun 1 '13 at 21:29
  • 1
    $\begingroup$ If you just take for $a$ the max of the $m_j$ (as you propose), it could be that you get $a=k$, while $k$ is just reached once by the function $m$. $\endgroup$ – Denis Jun 1 '13 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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