a relation in logic

Question

Suppose $\prec$ is a relation defined in the set of well defined formulas such that

$\phi \prec \psi$ iff $\models \phi \rightarrow \psi$ and $ \nvDash \psi \rightarrow \phi$

I would like to prove the following:

1. If $\phi \prec \psi$ then there exists $\chi$ such that $\phi\prec\chi\prec\psi$.

2. I'd like to find $\phi_1\prec\phi_2\prec\phi_3\prec...$

Thank you.

Answer 1

The best way to explain this is going to be with the aid of an example. Consider two basic formulae $\phi$ and $\psi$ consisting of propositional variables $p$ and $q\,$. That is let $\phi :=p\,$, and $\psi:= p\lor q\,$. Now, since $\vDash p\rightarrow (p \lor q )\,$, and $\not\vDash (p \lor q )\rightarrow p\,$, it follows that $\phi \prec \psi\,$.

Now to show that we can always find a formula $\chi$ such that $\phi\prec\chi \prec\psi\,$. Probably the best way to see this is by (i) taking into account that the introduction of an additional propositional variable gives us the required freedom to fashion such a formula $\chi\,$, and (ii) recourse to functional completeness, to be understood that the set of logical connectives or Boolean operators of our formal language is adequate to express all the all possible truth tables. This is achieved by composition of the basic connectives.

In this example I work with a particular pair of formulae $\phi$ and $\psi$ (defined earlier) such that $\phi \prec \psi\,$, but the method (algorithm) applies to any such formulae. Consider the following truth table. $$ \begin{matrix} p & q & r & (p \lor q) & (p \rightarrow (p \lor q) ) &( (p \lor q) \rightarrow p ) & \chi :=f (p,q,r) \\ \hline 1 & 1 & 1 & 1& 1& 1& 1\\ 0 & 1 & 1 & 1& 1& 0& 0\\ 1 & 0 & 1 & 1& 1& 1& 1\\ 0 & 0 & 1 & 0& 1& 1& 0\\ 1 & 1 & 0 & 1& 1& 1& 1\\ 0 & 1 & 0 & 1& 1& 0& 1\\ 1 & 0 & 0 & 1& 1& 1& 1\\ 0 & 0 & 0 & 0& 1& 1& 0\\ \end{matrix} $$

Note how introducing an additional propositional variable $r$ doesn't have any effect on the formulae that don't have $r$ in them. Introducing $r$ creates copies of the valuations of formulae without it. See the values of $p$ and $q$ -- they just repeat, once when $r$ is $1$ and again when $r$ is $0\,$.

The idea is to make $\chi$ weaker then $p$ yet stronger than $p\lor q\,$. Note how row $2$ and it's repeated counterpart (as far as $p$ and $q$ are concerned), row $6\,$, are those rows that are responsible for $\not\vDash (p \lor q )\rightarrow p\,$. That is, those are the rows where $p \lor q$ is true, but $p$ is false.

The trick that I suggest is to keep the top half of $\chi$'s valuation the same as $p$'s, and the bottom half the same as that of $p \lor q\,$. This achieves two things: it maintains $\chi$ strictly weaker than $p$, i.e. $\not\vDash \chi \rightarrow p\,$, since on the $6$'th row $\chi$ is true and $p$ is false, but otherwise $\chi$ is the same as $p\,$, and as a matter of fact $\vDash p \rightarrow \chi\,$, so $p \prec \chi\,$. Also it is the top half of $\chi$'s valuation thus constructed that gives $\not\vDash (p \lor q) \rightarrow \chi \,$, in virtue of row $2$, yet otherwise $\vDash \chi \rightarrow (p \lor q)\,$, hence $\chi \prec (p \lor q)\,$.

Hence $p \prec \chi \prec (p \lor q)\,$. That is, $\phi \prec \chi \prec \psi \,$, as required.

That we can always construct such a formula $\chi$ is granted by function completeness, i.e. $f$ denotes a composition of functional connectives from the adequate set, say $\{\neg, \lor \} \,$ and $f(p,q,r)$ denotes the complex formula that includes the new propositional variable $r\,$, that we need to introduce.

Answer 2

HINT: I’m assuming that you’re dealing with propositional logic and have a countably infinite set of propositional variable available.

• For the first one, consider the truth table for $\varphi\to\psi$; it must have at least one row $r$ in which $\varphi$ is false and $\psi$ is true. Let $A_n$ be a propositional variable that does not appear in $\varphi$ or $\psi$, and add it to the table; there will now be two rows corresponding to the original row $r$, one in which $A_n$ is true, and one in which $A_n$ is false. You want a formula $\chi$ that has all of the propositional variables of $\psi$ together with $A_n$ and that agrees with this extended truth table for $\psi$ except in one of the rows corresponding to the original row $r$. Note that you don’t actually have to construct $\chi$ explicitly: you just have to show that a formula with the desired truth table must exist.

• For the second one, note that if $A_n$ is a propositional variable that does not appear in $\varphi$, then $\varphi\prec\varphi\lor A_n$, unless $\varphi$ is a tautology.