Take the 2-minute tour ×
Philosophy Stack Exchange is a question and answer site for those interested in logical reasoning. It's 100% free, no registration required.

I'm taking basic discrete math course which includes basic intuitive introduction to logic (only things like statements, tautology truth tables, etc.). During the learning, I've wondered what is the difference, if any, between a->b to a |- b?

thanks!

share|improve this question
3  
NO, they are not the same. See this post for details and also this one. The relation Γ ⊨ φ of logical consequence is a relation between a set of (one or more) sentences and a sentence, while → is a connecetive. –  Mauro ALLEGRANZA Jul 25 at 15:51

3 Answers 3

up vote 6 down vote accepted

As Mauro pointed out in the comments, logical consequence (both in its semantic and syntactic variants) is a relation between sentences of the object language, while the conditional is a truth-functional operator on those sentences. Let's look at each in turn. I'll start with the conditional.

The conditional (→) is a binary operator on sentences: it takes two sentences (φ, ψ) and 'connects' them to form a compound sentence: (φ → ψ) or (ψ → φ). These compounds are still sentences of the so-called object language.

  • Example 1. Let's take as our object language JavaScript. Consider the expressions φ ≡ i != 0, and ψ ≡ k / i. You need to divide k by i, but you want to avoid a division by zero error, so you form the compound expression: if(i != 0) {k / i;} else {...;}. If we ignore the else-clause for a moment, the structure is the same as that of the material conditional: if(P) {Q} vs (P → Q). Had I chosen Lisp as our object language we could have a nicer correspondence.

The implication (which may be syntactical or semantical) is a relation between sentences of the object language in the metalanguage. Let's look at semantic consequence ( |= ): it takes a set of sentences Γ and a conclusion sentence ψ, and forms the compound sentence Γ |= ψ, which unlike (φ → ψ), is not in the object language. Let's look at an example.

  • Example 2. Let's again take as our object language JavaScript. Consider the set of expressions: φ1var a = 24;, φ76var b = 73, ψ ≡ a + b. You can imagine the compound expressions we can form using the conditional out of those expressions. But for implication, we form the meta-sentence {φ1, φ2} |= (ψ== 100). This says that any truth-assignment that makes the two φs true, makes (ψ = 100) true, which means that: any environment where a is bound to 24 and b to 73 is one that justifies the equality between ψ and 100.

Two two notions are intimately linked:

Fact. The truth of an implication ( |= ) is the validity of the conditional (→).

This gives us a decision procedure for implication. Let's take the second example. To test whether the implication {var a = 24;, var b = 73} |= (a + b) == 100 is true, we simply test the corresponding conditional for validity: we ask whether (var a = 24;var b = 73) → (a + b) == 100 is true under all assignments of values to the free variables occurring in it. Since all variables/identifiers are bound and the equality holds, the validity is immediately verified, and with it — the truth of the implication.

I apologize for the trivial examples; the hope is that they will help emphasize the distinction between object languages (e.g. JavaScript) and meta-languages (e.g. ordinary, semi-mathematical English).

share|improve this answer
    
Thank you very much! –  user1767774 Jul 26 at 18:20
    
@user1767774 You're very welcome. –  Hunan Rostomyan Jul 26 at 18:21

a -> b is a statement within a logical system, while a |- b is a statement about a logical system.

This is a distinction I also found very confusing when first encountering advanced formal logic. The compelling superficial similarities between the two statements make it tempting to blur the distinctions between them, but the high level reasoning is as follows: We need to keep strict barriers between the statements we make within logical systems and the statements we make about them or else a variety of significant paradoxes arise (notably the Liar's Paradox, see the notes on Tarski for more).

When modern formal logic was first developed, distinctions like these were not made, but it soon became obvious that some kind of intervention of this sort was necessary in order to save the entire enterprise.

share|improve this answer
    
Thank you very much! –  user1767774 Jul 26 at 18:27

"a->b" is read "a materially implies b," where "a" and "b" are sentences. Material implication is defined by a truth table such that a->b is false when a is true and b is false, otherwise it is true. So, we have semantic concepts here.

"a |- b" can be read in various ways: "b is theorem on a"; "there is a derivation of b from a"; "a proves b." These are syntactic concepts in the sense that b is the last line of a sequence that applies rules of inference to a, which is typically a set of sentences. To get a proof, you match logically valid structures already defined, e.g., modus ponens or whatever you need. There is no truth table for the turnstile symbol.

It's easy to see that a |- b implies a->b, i.e., that if b is a theorem on a, then a->b is a theorem. The other way around is not easy.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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