patternMinor
Definability of Truth Assignments
Viewed 0 times
assignmentsdefinabilitytruth
Problem
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
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
Solution
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).
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).
Context
StackExchange Computer Science Q#12425, answer score: 4
Revisions (0)
No revisions yet.