Proving a Tautological implication in logic

473 Views Asked by At

Ok so we are asked to prove the following:

$\Sigma \cup\phi\vDash\psi$ if and only if $\Sigma\vDash\psi\rightarrow \phi $ where $\Sigma$ is a set of types(not empty set), and $\phi$ and $\psi$ are also types of propositional logic.

My first thought is to prove this by induction in atopic for both directions. For the right direction:

$\Sigma \cup\phi\vDash\psi \Longrightarrow \Sigma\vDash\psi\rightarrow \phi $

i think its pretty easy. We assume that

$\Sigma \cup\psi\vDash\phi$

is true and that $\Sigma\vDash\phi\rightarrow \psi $ is false. We then analyze the above statement and reach an atopic easily.

The other half though:

$\Sigma \cup\phi\vDash\psi \Longleftarrow \Sigma\vDash\psi\rightarrow \phi $ i cant find how it can be proved by induction to atopic because if we take $\Sigma\vDash\psi\rightarrow \phi $ as true then we have to take that there a valuation $\upsilon$ where this $\upsilon$ is making all types of $\Sigma$ true(including $\phi$) and at the same time $\bar\upsilon$$ (\psi)=0 $ so that when we go back to $\Sigma\vDash\psi\rightarrow \phi $ we can make and induction to atopic.

But even if we say that $ (\psi)=0 $ that won't lead to atopic simply because if the same valuation $\upsilon$ gives us $\bar\upsilon$$(\phi)=0 $ and still the valuation could make all types of $\Sigma$ true and therefor the tautological implication will be true.

So what have i done wrong here? And if i haven't, how do i prove this?

Extra: what does the whole phrase : $\Sigma \cup\phi\vDash\psi \Longleftrightarrow \Sigma\vDash\psi\rightarrow \phi $ stands for in predicate logic??

1

There are 1 best solutions below

0
On BEST ANSWER

Preparations

First, I assume the correction made by Carl Mummert, i.e. you're trying to prove:

$$\Sigma \models \phi \to \psi \Rightarrow \Sigma \cup \{ \phi \} \models \psi$$

Here, the $\phi$ slides from the left side just to the beginning of the right side.

I further assume that you've defined

$$\nu(\phi \to \psi) = \begin{cases}1 &\text{ if }\nu(\phi) = 0 \text{ or }\nu(\psi) = 1\\0 &\text{ otherwise.}\end{cases}$$

and also:

$$\Sigma \models \phi \text{ if and only if for every } \nu \models \Sigma \text{ it holds that } \nu(\phi) = 1$$

where I define that $\nu \models \Sigma$, if for every $\varphi \in \Sigma$, we have $\nu(\varphi) = 1$, i.e. $\nu$ makes every type in $\Sigma$ true (usually one says $\nu$ is a model for $\Sigma$).

Now, things are straight forward.

A possible proof

Say it holds that $\Sigma \models \phi \to \psi$, which actually means:

$$\text{for any $\nu$, if }\nu\models\Sigma\text{ then }\nu(\phi\to\psi) = 1$$

which can be expanded to (just by definition of $\nu(\phi\to\psi)$):

$$\begin{align}\text{for any $\nu$, if }\nu\models\Sigma\text{ then either }\nu(\phi) = 0\text{ or }\nu(\psi) = 1 & &\text{ (1)}\end{align}$$

Now, let $\nu_0$ be any assignment such that $\nu_0 \models \Sigma \cup \{ \phi \}$, which is by definition: for every $\varphi \in \Sigma\cup\{\phi\}$ we have $\nu_0(\varphi) = 1$, so it follows that:

$$\nu_0\models\Sigma\text{ and }\nu_0(\phi) = 1.$$

By (1), we can follow $\nu_0(\psi) = 1$, which shows $\Sigma\cup\{\phi\}\models\psi$, since $\nu_0$ was arbitrary.

What you might got wrong

The statement $\Sigma \models \phi \to \psi$ does not state, that there is a $\nu$, such that $\nu\models\Sigma$ and $\nu(\phi\to\psi) = 1$, but if there is one, satisfying the first part, it satisfies also the second one; but there might be none.