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

  • $\begingroup$ What did you try ? $\endgroup$ – Kevin Quirin Oct 22 '15 at 11:30
  • $\begingroup$ 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. $\endgroup$ – hardmath Oct 22 '15 at 11:32
  • $\begingroup$ Right @KevinQuirin. Edited. Thanks $\endgroup$ – Ricardo Brandao Oct 22 '15 at 13:23
  • $\begingroup$ What did you get asked to do for the exercise? $\endgroup$ – Doug Spoonwood Oct 22 '15 at 16:50
  • $\begingroup$ @KevinQuirin, I found $\sigma$ = $\bot$. $\endgroup$ – 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.


I think there's a lot of confusion here. I'm going to give a full solution to this problem, and I encourage the OP to figure out why they're own argument does not work.

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

So we are done.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.