2

The semantic version of the deduction theorem says

$\Sigma ,A\vDash B$ iff $\Sigma \vDash(A\to B)$

I know that there exists proof for this in formal systems. But how can i prove this without using a system.

asddf
  • 1,733

2 Answers2

4

Since we're working with semantics, we'll need to talk about structures. First remember what $\models$ means:

  • "$\Sigma, A\models B$" means that every model of $\Sigma\cup\{A\}$ satisfies $B$.

  • "$\Sigma\models A\implies B$" means that every model of $\Sigma$ satisfies $A\implies B$.

Now do you see a way to prove one from the other? HINT: to prove the latter from the former, what can you say about a counterexample to "$\Sigma\models A\implies B$"? Similarly, think about a counterexample to the former - why does the existence of such a thing mean that the latter is false?

Noah Schweber
  • 245,398
  • 1
    latter from former would be smth along the lines of. Let $\Sigma$ be fulfilled. If it cant be then we are done. Suppose $A \to B$ was 0. Then $A=1$ and $B=0$. But since $\Sigma$ and A is fulfilled then B has to be true so contradiction ??? – asddf Sep 24 '17 at 21:35
  • 1
    For latter to former: Let $\Sigma$ be fulfilled then $A \to B$ is fulfilled. Suppose $\Sigma , A$ is fulfilled and $B$ is not fulfilled. Then this is a contradiction because of the former state.??? – asddf Sep 24 '17 at 21:39
  • @asddf Yes, that's basically correct. – Noah Schweber Sep 24 '17 at 21:47
1

$\Sigma , A \vDash B$ iff (definition $\Sigma \vDash \varphi$)

for all interpretations $I$: If $I\vDash \Sigma \cup \{ A \}$ then $I\vDash B$ iff (definition $I \vDash \Sigma$)

for all interpretations $I$: If $I\vDash \varphi$ for all $\varphi \in \Sigma \cup \{ A \}$ then $I\vDash B$ iff (pure logic)

for all interpretations $I$: If $I\vDash \varphi$ for all $\varphi \in \Sigma$ then if $I \vDash A$ then $I\vDash B$ iff (semantics $\rightarrow$)

for all interpretations $I$: If $I\vDash \varphi$ for all $\varphi \in \Sigma$ then $I \vDash A \rightarrow B$ iff (definition $I \vDash \Sigma$)

for all interpretations $I$: If $I\vDash \Sigma$ then if $I \vDash A \rightarrow B$ iff (definition $\Sigma \vDash \varphi$)

$\Sigma \vDash A \rightarrow B$

Bram28
  • 100,612
  • 6
  • 70
  • 118