# Creating a new connective in Propositional Logic

In the exercise below, is included a new connective ($\sqsubset$), and I'm stuck in how to deal with it.

We can view the relation $\vDash$ $\varphi$ → $\psi$ as a kind of ordering. Put $\varphi$ $\sqsubset$ $\psi$ := $\vDash \varphi \rightarrow \psi \space and \nvDash \psi \rightarrow \varphi$.

(i) For each $\varphi, \psi$ such that $\varphi \sqsubset \psi$, find $\sigma$ with $\varphi \sqsubset \sigma \sqsubset \psi$.

I suppose, it's need to prove:
$\varphi \rightarrow \sigma$ and $\sigma \nrightarrow \varphi$,
$\sigma \rightarrow \psi$ and $\psi \nrightarrow\sigma$

Considering $\varphi \sqsubset \psi := \space\vDash\varphi\rightarrow\psi$ and $\nvDash \psi\rightarrow\varphi$, we can write:

$\varphi \sqsubset\psi \leftrightarrow(\varphi\rightarrow\psi)\space\land\space\lnot\space(\psi\rightarrow\varphi)$

$$\begin{array}{rcc|c|cccc} (\varphi & \rightarrow & \psi ) &\land & \lnot & (\psi&\rightarrow&\varphi) \\ \hline \ 0&1&0&0&0&0&1&0 \\ \ 0&1&1&1&1&1&0&0 \\ \ 1&0&0&0&0&0&1&1 \\ \ 1&1&1&0&0&1&1&1 \\ \end{array}$$

So, we can define the truth table of $\space\sqsubset$

$$\begin{array}{c|cc} \sqsubset & 0 & 1 \\ \hline \ 0&0&1 \\ \ 1&0&0 \\ \end{array}$$

The problem is find $\sigma$ such that $\varphi\sqsubset\sigma\sqsubset\psi$

Truth table:

$$\begin{array}{ccc|c|ccc} (\varphi & \sqsubset&\sigma)&\land&(\sigma&\sqsubset&\psi) \\ \hline \ 0&0&0&0&0&0&0 \\ \ 0&0&0&0&0&1&1 \\ \ 0&1&1&0&1&0&0 \\ \ 0&1&1&0&1&0&1 \\ \ 1&0&0&0&0&0&0 \\ \ 1&0&0&0&0&1&1 \\ \ 1&0&1&0&1&0&0 \\ \ 1&0&1&0&1&0&1 \\ \end{array}$$

We found a contradiction, so we can conclude $\sigma = \bot$

Is this a right way? I'm a bit confusing about the symbol $\sqsubset.$

• What did you try ? – Kevin Quirin Oct 22 '15 at 11:30
• I suspect (i) has a typo, in that you probably intended $\varphi \sqsubset \sigma \sqsubset \psi$ rather than $\varphi \sqsubset \sigma \sqsubset \varphi$. Also, please review How to Ask, and add your own approach to the problem. – hardmath Oct 22 '15 at 11:32
• Right @KevinQuirin. Edited. Thanks – Ricardo Brandao Oct 22 '15 at 13:23
• What did you get asked to do for the exercise? – Doug Spoonwood Oct 22 '15 at 16:50
• @KevinQuirin, I found $\sigma$ = $\bot$. – Ricardo Brandao Oct 22 '15 at 17:43

If you consider the language with only one fundamental proposition $P$, and take $\phi = \perp$, $\psi = P$, then $\phi \sqsubset \psi$ but it is clear that no formula referring to $P$ alone can lie between them.
So in general (i) is true only if you are allowed to introduce a new propositional letter, and then the formula $\sigma$ needs to have value $T$ everywhere in the new truth table that $\phi$ does, but not everywhere that $\psi$ does.
HTFB's answer is correct - so let's assume we're working in a propositional language with infinitely many propositional variables. Then given $\varphi\sqsubset\psi$, we can let $P$ be a propositional variable not occurring in either $\varphi$ or $\psi$ (since $\varphi$ and $\psi$ are both only finitely long). Now, consider the formula $$\sigma:\quad \varphi\vee (\psi\wedge P).$$ This formula is true whenever $\varphi$ is true, so $\models \varphi\implies \sigma$; meanwhile, since $\varphi\sqsubset\psi$ and $P$ is not involved in $\varphi$ or $\psi$, we can find a truth assignent making $\psi$ and $P$ true but $\varphi$ false. So $\varphi\sqsubset\sigma$.
Meanwhile, it's clear that $\models\sigma\implies\psi$, but the converse is not true: since $P$ isn't used in $\varphi$ or $\psi$, we can find a truth assignment making $\psi$ true but $P$ and $\varphi$ (and hence $\sigma$!) false. (It must be possible to find a truth assignment making $\psi$ true, since otherwise "$\varphi\sqsubset\psi$" would be absurd.) So $\sigma\sqsubset\psi$.