2

I was given the following problem.

Determine the truth value of the following statement: If $\Gamma$ is a consistent set, then $\Gamma' = \{\neg \varphi : \varphi \in \Gamma\}$ is also consistent.

$\Gamma$ is understood to be a set of propositional formulas. Such a set is consistent iff there is a valuation $v$ such that $[\varphi]_v$ is true for all propositions in the set. Another way to think about this is to say the set is free of contradiction.

My response is that statement above is true. Indeed, let $v$ be a valuation that makes all formulas in $\Gamma$ true. Then

\begin{align*} f(\varphi) = \begin{cases} 1 & [\varphi]_v = 0 \\ 0 & [\varphi]_v = 1 \end{cases} \end{align*}

makes all propositions in $\Gamma'$ true as well. The reason is that, because $f(\varphi) = 0$ when $[\varphi]_v = 1$, and $f(\varphi) = 1$ when $[\varphi]_v = 0$, it becomes clear that $f(\varphi) = [\neg \varphi]_v$. It directly follows that $f(\neg \varphi) = [\varphi]_v$. That every statement in $\{\neg \varphi : \varphi \in \Gamma\}$ is true under the assignment $f$ is then clear, because $[\varphi]_v$ is true by definition.

My question is whether this is sufficient proof of the consistency of $\Gamma'$. I have shown that $f$ makes every formula true, but not that it does so in a way that's free of contradiction. This seems completely obvious from the fact that $v$ makes the formulas in $\Gamma$ true without contradiction, and $f$ is simply a "reversed" $v$. But I haven't been able to rigorously prove this.

Asaf Karagila
  • 393,674
lafinur
  • 3,322

1 Answers1

1

HINT: what if $\Gamma$ contains, say, the formula $x\to x$?

Franklin Pezzuti Dyer
  • 39,754
  • 9
  • 73
  • 166
  • Isn't that the unproblematic case? The formula is a tautology and hence is true under any valuation. Particularly, $[x \to x]_v = 1$ and then $f\big( \neg(x \to x)\big) = 1$ and no issues there. What am I missing? – lafinur Jul 10 '23 at 16:55
  • @lafinur I was referring more to the original problem. Suppose, for instance, that $\Gamma = {x\to x}$ where $x$ is a sentence symbol. Then $\Gamma' = {\neg(x\to x)}$. Is this consistent? – Franklin Pezzuti Dyer Jul 10 '23 at 17:01
  • @lafinur Regarding your argument, it looks like you're misunderstanding what a valuation does. It doesn't assign a true/false value to every formula, but rather a true/false value to every sentence symbol (assuming we are talking about sentential logic here). Then the truth value of every formula is determined by that assignment. The $f$ you've defined is not a valuation at all. – Franklin Pezzuti Dyer Jul 10 '23 at 17:07
  • For instance, consider $\Gamma = {x\land y, \neg(x\lor y)}$. By your reasoning, one might say "define $f$ such that $f(x\land y) = 1$ and $f(\neg(x\lor y)) = 1$, then $f(\gamma) = 1$ for all $\gamma\in\Gamma$ and therefore $\Gamma$ is consistent". But this $\Gamma$ certainly is not consistent. Really you should be assigning values for $f(x)$ and $f(y)$, and the truth value of each formula involving $x,y$ is determined by these truth assignments. You'll find that no assignment of $x,y$ makes both formulas of $\Gamma$ true. – Franklin Pezzuti Dyer Jul 10 '23 at 17:09
  • 1
    Your last two comments seems to hit the nail in the head in what comes to my confusion. If valuations refer to propositional atoms (or sentence symbols) and not formulas - it makes sense that this is the case now that I think about it -, any $\Gamma$ consisting of a tautological formula is consistent with $\Gamma'$ necessarily inconsistent. – lafinur Jul 10 '23 at 17:11
  • Thank you very much! – lafinur Jul 10 '23 at 17:11
  • @lafinur Sure thing, glad it helped! :-) – Franklin Pezzuti Dyer Jul 10 '23 at 17:14
  • Let us continue this discussion in chat. – Franklin Pezzuti Dyer Jul 10 '23 at 17:16