Prove a proposition containing only the connective ∧,∨ is "monotonic"

209 Views Asked by At

For an assignment $v$ and $i ∈ ℕ$, define $v_{i}$ to be the assignment with $v_{i}(x_{i})=T$ and $v_{i}(x_{k})= v(x_{k})$ for every $i ≠ k$. (So $v_{i}$ agrees >with $v$ on all variables, except possibly $x_{i}$, which it sets to True).

A proposition $ α$ is said to be monotone if for any assignment $v$ satisfying $α$, it holds that every assignment $v_{i}$ also satisfies $α$, for every $i ∈ ℕ$.

Prove that every proposition containing only the connectives $∧,∨$ (in addition to constants and variables) must be monotone.

The solution proves this with structural induction, but there is a thing I fail to understand in the proof, in the inductive step in the situation where $α = β ∧ δ$, where $β,δ$ are monotone strict subformulas of $α$, the claim the following

$α = β ∧ δ$: Suppose $v$ is an assignment that satisfies $β ∧ δ$. This means that $v$ must satisfy both $β$ and $δ$. Since $β$ and $δ$ are each individually monotonic, we know for every $i ∈ ℕ$ that $v_{i}$ satisfies $β$ and also satisfies $δ$. By the truth table of $∧$, this means every $v_{i}$ satisfies $β ∧ δ$. That is, $β ∧ δ$ is monotonic.

Why does $v_{i}$ satisfy both $β$ and $δ$? We know that as $β$ and $δ$ are monotonic there exists a $v_{i}$ that satisfy $β$, and a $v'_{i}$ that satisfies $δ$, but I don't understand why there exists a single $v_{i}$ that satisfies them both? I feel like I'm missing something important in my understanding of the subject and I can't move on from it..

1

There are 1 best solutions below

0
On BEST ANSWER

Remember that $v_i$ is totally determined by $v$: it's the valuation you get by taking $v$ and modifying it (or leaving it alone) so that it assigns $T$ to $x_i$. There aren't two different versions of $v_i$ floating around, one for $\beta$ and one for $\delta$.


In detail, the argument is the following. Supposing $v$ is a valuation satisfying $\beta\wedge\delta$ and $i\in\mathbb{N}$, we want to show that the uniquely define valuation $v_i$ also satisfies $\beta\wedge\delta$.

  • $v$ satisfies $\beta$ and $v$ satisfies $\delta$ (definition of satisfaction for $\wedge$).

  • Since $v$ satisfies $\beta$, $v_i$ also satisfies $\beta$ (since $\beta$ is monotonic).

  • Since $v$ satisfies $\delta$, $v_i$ also satisfies $\delta$ (since $\delta$ is monotonic).

  • So $v_i$ satisfies $\beta\wedge\delta$.