Show $\vDash \phi \to \psi \Leftrightarrow \{\phi\} \vDash \psi$.

Dirk van Dalen. "Logic and Structure (Universitext)" (p. 29)

Definition 1.2.1 A mapping $$v : PROP \to \{0, 1\}$$ is a valuation if $$v(\phi \land \psi) = min(v(\phi), v(\psi)),\\ v(\phi \lor \psi) = max(v(\phi), v(\psi)),\\ v(\phi \to\psi)=0 \leftrightarrow v(\phi)=1 \text{and} v(\psi)=0,\\ v(\phi \leftrightarrow \psi)=1 \leftrightarrow v(\phi)=v(\psi), v(\lnot\phi) = 1 − v(\phi)\\ v(\bot) = 0\\$$

Definition 1.2.4 (i) $$\phi$$ is a tautology if $$[[\phi]]v$$ = 1 for all valuations $$v$$, (ii) $$\vDash \phi$$ stands for ‘$$\phi$$ is a tautology’, (iii) Let $$\Gamma$$ be a set of propositions, then $$\gamma \vDash \phi$$ iff for all $$v$$ : $$([[\phi]] v = 1 \text{for all } \psi \in \Gamma) \to [[\phi]]v = 1$$.

My proof skeleton of one side of the proof: $$\{\phi\} \vDash \psi \Rightarrow \, \vDash \phi \to \psi$$.

Since $$\{\phi\} \vDash \psi$$, I know that for all valuations $$v$$, $$[[\phi]]_v = 1 \Rightarrow [[\psi]]_v = 1$$. Proof:

• I start assuming $$[[\phi]]_v = 1$$
• $$[[\phi]]_v = 1 \to [[\psi]]_v = 1$$
• $$[[\psi]]_v = 1$$
• $$[[\phi]]_v = 1 \to [[\psi]]_v = 1$$
• $$\vdots$$

Am I on the right track ?

• You should not use the symbol $\rightarrow$ as both a logical symbol in well-formed formulas and as a meta-logical simple for "implies" in statements of propositions. For example, $\{\phi\}\models\psi\rightarrow\models\phi\rightarrow\psi$ is both difficult to read and prone to parsing errors. In general, I suggest you rewrite your proof attempt using more words and sentences, and fewer symbols and bullets. Commented Oct 9, 2020 at 18:35
• To add to halrankard's remark, if you like using abbreviations, you could use a double arrow $\Rightarrow$ for a meta-linguistic "if then". Commented Oct 9, 2020 at 18:39
• After your edit, your implication in "If $[[\phi]]_v = 1$ then $[[\psi]]_v = 1$" should also be a $\Rightarrow$: It is an English statement, rather than a formula. Commented Oct 9, 2020 at 19:40
• "$[[\phi]]_v = 1$" and "$[[\psi]]_v = 1$" are statements of the meta language (~= "mathematical English"): They are equations and thus mathematical facts. They use abbreviatory symbols ("$=$", "[[.]]"), but technically are expressions in ordinary language ("The truth value of $\phi$ under $v$ is $1$"). When asserting a conditional between two mathematical facts, such as "If $\phi$ is true under $v$ then $\psi$ is true under $v$", that will be a meta-linguistic, informal "if ... then", abbreviated $\Rightarrow$. Commented Oct 9, 2020 at 21:10
• On the other hand, the symbol $\to$ is a symbol of the inductively defined formal language of logic and can only connect formulas to form a new formula. Putting an object language implication $\to$ between two facts (such as truth value equations) does not make sense, because $\to$ only connects formulas, and $[[\phi]]_v = 1$ is not a formula. Hence why you probably mean $\Rightarrow$. Commented Oct 9, 2020 at 21:10

Starting with the assumption that $$[[\phi]]_v = 1$$ is correct.
The $$[[\psi]]_v$$ in your first sub-bullet point is strange; that's just an unknown number (a yet to be determined truth value) standing there, but after an "if ... then" one expects a statement. So just do without the sub bullet points and conclude $$[[\psi]]_v = 1$$ directly.
You should also generally add brief justifications how you obtain your results: Here, you used the assumption that $$\phi \vDash \psi$$.
Afterwards, you want to use this result to conclude that the implication $$\phi \to \psi$$ is true under the given valuation, justified by definition 1.2.1.

To complete the proof for the first direction, you then have to cover the other case: $$[[\phi]]_v = 0$$. That is, you do a proof by cases on the possible truth values of $$\phi$$, and obtain that the implication follows in eihter case.

Finally, you should make it clear what that $$v$$ is you are talking about: You are carrying out the proof for an arbitrary $$v$$, then conclude that since $$v$$ was arbitary, the above holds for all valuations, hence $$\vDash$$.

Taking this together, an improved version of your attempt looks as follows:

Assume $$\phi \vDash \psi$$.
Let $$v$$ be an arbitrary valuation.
There are two cases to distinguish:

1. $$[[\phi]]_v = 1$$.
By the assumption $$\phi \vDash \psi$$, it follows that $$[[\psi]]_v$$ = 1.
Then by the truth table of implication, $$[[\phi \to \psi]]_v = 1$$.
2. $$[[\phi]]_v = 0$$.
$$\vdots$$

In both cases it holds that $$[[\phi \to \psi]]_v = 1$$.
Since $$v$$ was arbitrary, the above holds for all valuations, hence $$\vDash \phi \to \psi$$.

• Thank you so much, @lemontree. Really appreciate your insight and deep explanations. Commented Oct 9, 2020 at 19:53
• This is my attempt: 2. $[[\phi]]_v = 0$. By the truth table of implication, $[[\phi \to \phi]]_v = 1$. Is it correct ? Commented Oct 9, 2020 at 19:53
• In $\vDash \phi \to \psi$, the set of hypothesis is empty. Does it play a role in these proofs ? As there is no valuation that makes the hypothesis false (because there are none), it means that $\phi \to \psi$ is a tautology ? Commented Oct 9, 2020 at 19:56
• Yes to both of your comments. Commented Oct 9, 2020 at 20:15
• That there are no premises in $\vDash$ plays a role in the proof in so far as the statement "$[[\phi \to \psi]]_v = 1$ "is not conditioned on the truth value of any premises (because, as you say, there aren't any), and yes, this means it is a tautology. Does this answer what you were after? Commented Oct 9, 2020 at 20:18