1
$\begingroup$

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 ?

$\endgroup$
12
  • 3
    $\begingroup$ 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. $\endgroup$ Commented Oct 9, 2020 at 18:35
  • $\begingroup$ To add to halrankard's remark, if you like using abbreviations, you could use a double arrow $\Rightarrow$ for a meta-linguistic "if then". $\endgroup$ Commented Oct 9, 2020 at 18:39
  • $\begingroup$ 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. $\endgroup$ Commented Oct 9, 2020 at 19:40
  • 1
    $\begingroup$ "$[[\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$. $\endgroup$ Commented Oct 9, 2020 at 21:10
  • 1
    $\begingroup$ 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$. $\endgroup$ Commented Oct 9, 2020 at 21:10

1 Answer 1

1
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ Thank you so much, @lemontree. Really appreciate your insight and deep explanations. $\endgroup$
    – F. Zer
    Commented Oct 9, 2020 at 19:53
  • $\begingroup$ This is my attempt: 2. $[[\phi]]_v = 0$. By the truth table of implication, $[[\phi \to \phi]]_v = 1$. Is it correct ? $\endgroup$
    – F. Zer
    Commented Oct 9, 2020 at 19:53
  • $\begingroup$ 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 ? $\endgroup$
    – F. Zer
    Commented Oct 9, 2020 at 19:56
  • $\begingroup$ Yes to both of your comments. $\endgroup$ Commented Oct 9, 2020 at 20:15
  • $\begingroup$ 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? $\endgroup$ Commented Oct 9, 2020 at 20:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .