Skip to main content
added 255 characters in body
Source Link
Kaveh
  • 22.5k
  • 4
  • 52
  • 112

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

You can generalized this construction to findThere is a topological characterization of the setsets 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).

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

You can generalized this construction to find a topological characterization of the set of truth assignments that can be defined. You may be interested in Stone duality and type (model theory).

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

Source Link
Kaveh
  • 22.5k
  • 4
  • 52
  • 112

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

You can generalized this construction to find a topological characterization of the set of truth assignments that can be defined. You may be interested in Stone duality and type (model theory).