7

How should we understand the distinction between ⇒ and ⊢ ?

I often see that A ⇒ B lives in the object language and A ⊢ B in the meta language. But I need a different interpretation, without any reference to "meta-logic".

An interesting text, What the Tortoise Said to Achilles (Lewis Carroll) seem to provide an implicit answer. How should we interpret that to understand the distinction ?

Some interesting points of view suggested by J.Y Girard that I don't fully understand :

  • The distinction is not accessible to realism because they have the same semantic. Inspired by Kant, he often says that ⊢ refers to "implicit", "synthetic" and ⇒ refers to "explicit", "analytic".

La nuance entre imbrication ⊢ et l'implication ⇒ est inaccessible au réalisme : elles ont, en effet, la même sémantique. L'acte fondateur de la logique moderne est ainsi franchement déréaliste. Alors que ⊢ réfère au synthétique d'usage, l'implicite et son substrat analytique performatif, ⇒ ne réfère plus qu'à l'usine explicite et son substrat analytique constatatif.

J.Y Girard, le fantôme de la transparence.

  • About Lewis Carroll's text, the Tortoise is said to be "without cut" while Achilles use "cut" (The Blind Spot, Part 3.A.2, J.Y Girard).

  • ⇒ is said to be "incremental" while ⊢ is said to be "destructive"

  • ⇒ is said to be "terminated" while ⊢ is said to be "non-terminated"

  • Logic lies on the dialectic between ⇒ and ⊢

Boris
  • 878
  • 6
  • 14
  • a quibble: he does *not* say the have the same semantic. he says they *effectively* (en effet) have the same semantic. i'm not sure i agree, since it could be argued that there are different notions of "semantic" involved. –  Feb 26 '17 at 20:31
  • e.g. nothing compells us to give a representationalist reading of either symbol. an anti-representationalist might argue that there is no semantic, only meaning, and => and |- surely have different meanings. –  Feb 26 '17 at 20:38
  • I rather translate that as something like "They have, indeed, the same semantic" (I'm a native French speaker). I think he's refering to deduction theorems. In the Blind Spot (Chapter 3.1.2), many years before *Le fantôme de la transparence*, he also wrote that (About the LK system of Gentzen) *"The creation of '⊢' makes no sense, it's a duplication since the deduction theorem makes them equal. The sequent calculus only makes sense when we're going beyond provability, when we're working in finesse"*. Don't know if his view changed with the time... – Boris Feb 26 '17 at 20:56
  • I'm not a native speaker of french, but I am a sometime professional translator (not of french),and this strikes me as clearly an ambiguous case. he could have said "en fait" (de fait?) or something similar if he wanted to say they are the same. but i don't think that was his intention. after all, they clearly are not _the same thing_. –  Feb 26 '17 at 21:10
  • damn, i'd like to read that stuff. any english translations you know of? or free online french versions? –  Feb 26 '17 at 21:12
  • @mobileink J.Y Girard is known for his kind of obscure view of logic. His works are quite new/modern (Linear Logic, Transcendal Syntax, Ludics...). You can find most of his works there http://iml.univ-mrs.fr/~girard/Accueil.html (see "Articles techniques" and "Articles non techniques" in the bottom). You can also check the texts I linked to Mauro ALLEGRANZA in the bottom of that StackExchange question. – Boris Feb 26 '17 at 21:18
  • when he says "inaccessible au réalisme" doe he mean sth like "cannot be accomodated by representationalism"? that would make sense to me. –  Feb 26 '17 at 21:18
  • oh, he's a serious badass, but he's also a bit like Derrida: very important, but kinda hard to read. :) –  Feb 26 '17 at 21:20
  • @mobileink As for the Blind Spot you can find some pages there https://books.google.it/books?id=eVZZ0wtazo8C&pg (maybe somewhere else but I don't know). As for what he meant by "inaccessible au réalisme" I think he's refering to essentialism/platonism (see [Blind Spot - Existence vs Essence](https://books.google.it/books?id=eVZZ0wtazo8C&pg=PA3&hl=fr&source=gbs_toc_r&cad=3#v=onepage&q&f=false). – Boris Feb 26 '17 at 21:22
  • @mobileink Yeah, most people say he's hard to read but I think there're interesting things hidden behind his texts. He's also a bit "provocative/biased/controversial" in his style of writing. – Boris Feb 26 '17 at 21:24
  • back to your original question: why do you need an interp without meta-logic? just cuious. –  Feb 26 '17 at 21:27
  • @mobileink I don't really *need* it, I was just curious. As I understand it, according to J.Y Girard, the traditional distinction syntax/semantic and objet-language/meta-language is a quite naive view : it's made of a lot of prejudices. We refer to an external reality beyond logic/reason. He's seeking for a Logic where the rules could be justified by "themselves", a kind of internal justification of the rules of Logic : we should forget "reality". I just wanted to understand that point of view regarding ⇒ and ⊢ because he seems to give an interesting importance to that distinction. – Boris Feb 26 '17 at 21:42
  • very interesting. i really must read his stuff, i'm interested in the same things, philosophically. have you looked at proof-theoretic semantics? –  Feb 26 '17 at 21:51
  • i highly recommend Etchemendy's "The Concept of Logical Consequence". https://books.google.com/books/about/The_Concept_of_Logical_Consequence.html?id=XibXAAAAMAAJ&hl=en. Very short, very hard to read (took me about 4 tries), but _very_ enlightening. –  Feb 26 '17 at 21:55
  • Hum. I'm not sure about what you mean by "proof-theoretic semantics" but I'm interested in proof theory (in a technical point of view), logic and its connections with Computer Science (I'm initially a Computer Scientist). I just happened to be there because Linear Logic (created by J.Y Girard) and his other ideas (Transcendental Syntax, Geometry of Interactions, Ludics...) have some connections with philosophy (I think we shouldn't extend too much that conversation). – Boris Feb 26 '17 at 22:05
  • proof-theoretic semantics go back to gentzen: the meaning of logical operators is determined by their rules of use, not their semantics. put differently, use determines meaning, not the other way around. just do a web search - i'm away from my machine orherwise i'd give you links. ok, google "Dag Prawitz". –  Feb 26 '17 at 22:18
  • see e.g. https://plato.stanford.edu/entries/proof-theoretic-semantics/ –  Feb 26 '17 at 22:24
  • @mobileink Oh ok, I will check that. I'm quite aware of that but I didn't know it was studied under that aspect. It remind me of the famous quote "Meaning is use" from Wittgenstein. Speaking of which, according to Girard, meaning can be split into "Usage" (use) and "Usine" (a kind of refinement of Wittgenstein's view of meaning). Something that I currently don't fully understand. – Boris Feb 26 '17 at 22:54
  • I am not sure I understand the question. Are you thinking of some universalist version of logic without object/meta hierarchy (like logicism)? Girard's idea seems to be along the lines of distinguishing [semantic/deductive logical consequence](http://www.iep.utm.edu/logcon/#H3) which can in principle be done without object/meta. Are you unhappy with that for some reason? – Conifold Feb 27 '17 at 16:53
  • @Conifold (1) An answer I often see is [that one](http://math.stackexchange.com/questions/286077/implies-vs-entails-vs-provable) or [that one](http://math.stackexchange.com/questions/90787/whats-the-difference-between-to-implication-and-vdash-therefore?noredirect=1&lq=1). I'm not sure but Girard seems to provide an alternative answer to the same question. That's what I wanted to understand. (2) I think he's really refering to "implication" and "deductive consequence" as we can see in, say, the Modus Ponens rule (hint in the message below). – Boris Feb 27 '17 at 17:28
  • @Conifold In a more technical discussion (Curry-Howard Isomorphism), in *le fantôme de la transparence* he wrote "The distinction between imbrication (⊢) and implication (⇒) lies on the duality of the reading of functionality, which already opposed the sin x function and the sinus application. The former, giving us a result depending on its argument is the program we use. The latter, becoming an application, don't wait for any argument, it is only focusing on the functionality itself, it's the program we write." Then he provide some examples from the Curry-Howard Isomorphism. – Boris Feb 27 '17 at 17:28
  • @Conifold Maybe you can also check that page : https://books.google.it/books?id=eVZZ0wtazo8C&lpg=PA70&hl=fr&pg=PA55#v=onepage&q&f=false – Boris Feb 27 '17 at 17:46

3 Answers3

4

Briefly, the distinction is not Girard's, it is already present in Frege's work in the late 19th century. If logic is the science of deduction, then entailment is the expression of deducibility, of a conclusion from hypotheses.

Entailment is not at all a "meta" concept; that is simply incorrect. It is, however, prior to implication in that implication internalizes entailment as a connective. That is, an implication is true exactly when one can deduce the consequent from the antecedent.

Analogously, in categories the Hom is prior to the exponential. That is, we have maps before we have objects that classify them.

Analogously, in type theory we have open terms (with free variables) before we have lambda's, which are elements of function types.

Analogously, in school you learned to use polynomials before you learned that one could define, say, a differential operator.

  • Nice answer. But I'm not sure to understand your analogies (I'm familiar with the concepts but I don't see how it's related). Can you provide more analogies or develop the one you provided ? – Boris Nov 26 '17 at 18:38
3

I am not sure if Le Fantôme de la Transparence is translated into English but the themes from the quote are familiar from Girard's Transcendental Syntax, which is. Here is the full quote in my translation:

"The nuance between imbrication ⊢ and implication ⇒ is inaccessible to realism: they have, indeed, the same semantics. The founding act of modern logic is thus frankly derelict. While ⊢ refers to the synthetic use, and implicitly to its performative analytic substrate, ⇒ refers only to the explicit use, and its declarative analytic substrate."

The "founding act of modern logic" is Frege's predicate calculus with logical consequence based on semantics. This last part, a.k.a. "realism", is, according to Girard, fatally flawed. Here are some of his reasons why:

"The fact is that semantics — whatever quality they may have — are all incomplete: they fail to catch the specificity of language. We can indeed see "the" reality as a way of quotienting the language; there are various styles of quotients, of variable quality; this variability may even be linked to the freshness of the interpretation... In the same way, the experience of philosophical logic is that of ad hoc realities, monkeying the syntax, typically Kripke models: semantics as prejudice, so to speak. One interprets the language (written in italics) by the same thing (written in boldface), thus making (almost) no quotient at all... To sum up, there is no ultimate reality the language is referring to. There are, however, a few pseudo-realities of interest, all of them exploiting some aspect of the language. Anyway, since the semantic construction takes place in the language of mathematics, semantics is eventually an internal interpretation of the language!"

On my reading, in the quote Girard is pointing out that "realists" can not distinguish ⊢ from ⇒, or rather that their distinction is purely contextual (language vs. metalanguage) rather than substantive. The reason is that "there is no ultimate reality the language is referring to". This makes Fregean logic (and by extension all of its modern successors) "derelict". On ⇒ specifically Girard contrasts proof theoretic interpretation of A ⇒ B as a function that sends proofs of A to proofs of B, to the Tarskian tautology that it is true when the truth of A implies the truth of B, commenting that "such a truism may sometimes be useful, but it is clearly meaningless: tarskian truth is a classified topic". See also Why is Tarski's notion of logical validity preferred to deductive one? I do not see, however, that he necessarily wants to rehabilitate ⊢, which presupposes stepping outside of language to "perform" logic, something Girard denounces:

"The Fregean opposition between sense and denotation is philosophically extremely naive and part of the totalitarian regression of thought, possibly linked with the abominable political opinions of Frege... for the technical reasons just expounded, but also from a common sense remark: the language formats the reality. Frege’s description of logic reminds me of this explanation of vision of my childhood: the landscape is projected on the retina of an ox. OK, so what? It still remains to understand how this retinal image is analysed."

The distinction on which Fregean logic is "derelict" can perhaps be manifested differently. I can only speculate that "analytic substrate" probably refers to the substrate of Girard's self-sufficient language, and "performative"/"declarative" dichotomy is related to the two sides of Curry-Howard correspondence between logical proofs and typed λ-terms, "execution" and "construction". This is the basis of Girard's idea of justifying syntax from within syntax, by uncovering (Kant inspired) conditions of the possibility of its practical functioning without infinite loops. On this I find Abrusci-Pistone's expose of Girard's program somewhat easier to follow :

"Research on typed λ-calculi usually privileges, indeed, an approach directed to the dynamical features of logic: proofs, as isomorphic with programs, are taken as mathematical objects that must not only be constructed following the rules, but also be executed following the dynamics of those rules. The duality construction/execution is made explicit by the so-called formulae-as-types correspondence, by which logical formulas are associated with types, that is, with sets of proofs satisfying the norms associated by logical rules to those formulas... Logical syntax can thus be seen both as a constructive tool, enabling the formation of (normalizing) typed terms, and as a constraining one, imposing a custom on pure terms (and their socialization) in order to force termination. In analogy with Kant’s transcendentalism, indeed, the program tries to raise the issue to deduct, that is, to legitimize the authority exercised by logical languages... without reference to those entities whose representability crucially relies on the use of what is charged of being justified."

For a more detailed commentary see Rouleau's 2013 thesis Towards an Understanding of Girard's Transcendental Syntax: Syntax by Testing.

Conifold
  • 42,225
  • 4
  • 92
  • 180
  • Interesting analysis. (1) " I do not see, however, that he necessarily wants to rehabilitate ⊢, which presupposes stepping outside of language to "perform" logic, something Girard denounces". According to him, that distinction was already established by Gentzen but not expressed explicitly. He's refering to that in some talks but I don't know where you can find that in a text (beside the page I already mentionned). In the slide of one of his talks we can read : "Sequent calculus distinguishes finished from unfinished. A ⇒ B: pure, decorative, implication. A ⊢ B: give me A and you will get B" – Boris Feb 27 '17 at 22:30
  • (2) Another quote from his [slides](http://iml.univ-mrs.fr/~girard/hapoc2013.pdf) : "⇒ ambiguous too. Sequents (Gentzen 1934) distinguish: Implication: ⇒ explicit and incremental: subformulas. Entailment: ⊢ implicit and destructive through cut." – Boris Feb 27 '17 at 22:31
  • (3) As I understand it, "performative" and "declarative" are subjective. For instance, in the lambda calculus, "performative" refers to non-normal terms (the rewriting rules used to reduce lambda terms being the associated "performance") and "declarative/constat" refers to the normal form of a lambda terms. It's subjective because we can ask "Do we need to go further ?" depending on the context (he gives as example the formula 2^{64}-1 which is declarative because satisying in his opinion). – Boris Feb 27 '17 at 22:36
  • (4) As for Rouleau's thesis, I already saw it but it was mainly technical details. I read the non-technical parts but the technical ones seems to difficult for me to follow. Maybe I should re-check that. As for Abrusci-Pistone's paper, I read some parts but I should re-try as well. – Boris Feb 27 '17 at 22:42
  • @BorisEng I'd have to read what he says in context to say something definitive. It might be (from your quotes) that Girard distinguishes between ⊢ and the horizontal line, i.e. treats ⊢ as part of the object language. But frankly, on the usual interpretation of the sequent calculus (which Girard's "give me A and you will get B" seems to endorse), ⊢ still functions as a metasymbol (although proof-theoretic rather than semantic). Then again, maybe this is the point, treat declaration and performance as interpretative aspects of the same language rather than of language and meta-language. – Conifold Feb 28 '17 at 00:14
  • "on the usual interpretation of the sequent calculus, **⊢** still functions as a metasymbol" NO; see G.Takeuti, [Proof Theory](https://books.google.it/books?id=Idl6K-W69NYC&pg=PA8) (2nd ed 1987), page 8: in the *calculus of sequents* "for arbitrary **Γ** and **Δ**, **Γ→Δ** is called a *sequent*" (with the original Gentzen's notation: **→**). Compare J-Y. Girard, [Proof Theory and Logical Complexity:Volume I](https://books.google.it/books?hl=it&id=TN_uAAAAMAAJ) (1990), page 97: "**Def.2.1.1**. A *sequent* is a formal expression **Γ⊢Δ** where **Γ** and **Δ** are finite sequences of formulas." – Mauro ALLEGRANZA Feb 28 '17 at 09:10
  • @BorisEng I was referring to the implication introduction Γ, A ⊢ B / Γ ⊢ A→B, but Mauro's is a good point. Upon thinking it seems to me that Girard is not so much against language/meta-language divide as against *semantic* meta-language, the model-theoretic view of it. To wit, "*since the semantic construction takes place in the language of mathematics, semantics is eventually an internal interpretation of the language*". He may further want to collapse the hierarchy, but that can be done nominally as in sequent calculus, and even meta-language may do if it is treated proof-theoretically. – Conifold Feb 28 '17 at 21:42
  • @Conifold I also read that. I'm a bit confused now. – Boris Feb 28 '17 at 22:04
  • 1
    @BorisEng Sequent calculus treats both ⊢ and → "in house" in the object language. But ⊢ functions there as in the meta-language of standard logic with respect to implication and other connectives. In effect, it duplicates the horizontal line of sequent calculus's meta-language in the object language. I am thinking that Girard's issue is not with meta-language (sequent calculus still has it) but rather with referring to outside of language. His idea may be to treat all languages proof-theoretically, but then we need to put constructive and executive tools together into the *same* language. – Conifold Feb 28 '17 at 22:29
  • @Conifold OK. Can you clarify your last sentence ? What do you mean by "into the same language" ? I'm not sure to understand. Nonetheless, his statements will remain a bit "cryptic" but it's fine. – Boris Feb 28 '17 at 22:41
  • 1
    @BorisEng On the standard approach we declare in a language and give performing instructions in the meta-language. This works for semantic instructions ("truth conditions"). But if we want to give proof-theoretic instructions (and for other Girard's reasons) we need a language that can both declare *and* say things like "give me A and you will get B" within. We may still use meta-language (set theory say) to interpret a language (arithmetic say), but now they will have the same proof-theoretic expressive means, which eliminate references to "reality" beyond languages, and lets them format it. – Conifold Mar 01 '17 at 02:43
  • @Conifold Can you also clarify the following sentence "since the semantic construction takes place in the language of mathematics, semantics is eventually an internal interpretation of the language". How is semantics an internal interpretation of the language ? – Boris Mar 02 '17 at 21:57
  • 1
    @BorisEng It is easiest to explain on model theory in mathematics. A formal theory is interpreted by assigning sets to constants, set-theortic relations to predicates, etc. But what are sets, etc., if not denizens of another formal theory, the axiomatic set theory? Unless of course we believe in the Platonic realm and direct access to what goes on there. Semantic "truths" are not "seen" by Platonic mindsight, they are still deduced from axioms, but of set theory. Girard extends the idea to all interpretations of "reality", even empirical "truths" are not "seen" but derived through language. – Conifold Mar 02 '17 at 22:20
  • @Conifold So, we can say that "semantics is eventually an internal interpretation of the language" because it's itself represented in a formal language and interpret expressions in a formal language as well ? – Boris Mar 02 '17 at 23:20
  • 1
    @BorisEng Yes, more or less. What initially appears semantic/real to us (and was naively taken at face value by Frege et al.) upon reflection turned out to be "formatted" by another language, which itself is so formatted, etc. "Eventually", we realize that all semantic "realities" are "semantic constructions in the language of mathematics" (more often some imperfect approximation of it), so despite the appearances the whole enterprise of "interpretation" is not establishing a correspondence with "reality" but is internal to language, broadly construed. – Conifold Mar 03 '17 at 02:39
1

After some researches I think I have a quite satisfying answer.

Suppose we're in the Sequent Calculus (we don't care whether it is classical or intuitionistic). We know that the cut rule act on ⊢ while the implications rules act on ⇒.

The turtle tells us that we have the premises ⊢ A and A ⊢ B and asks us to get ⊢ B. We have two possible things we can do:

  • Use the cut rule to infer ⊢ B (that's one should answer to the turtle)
  • Use the left-implication rule to infer A ⇒ A ⊢ B (that's what Achille does)
    • In that case, with another cut (that's what the turtle want) with ⊢ A ⇒ A which is indeed provable we can have have ⊢ B
    • Or you can also use the left-implication rule again (that's what Achille does) to get (A ⇒ A) ⇒ (A ⇒ A) ⊢ B. That rule can be repeated as much as we want.

Conclusion

  • The usual model-theoretic interpretation of sequents is associated to realism. The sequent ⊢ A ⇒ B and A ⊢ B have the same interpretation in term of truth values. So no distinction can be seen.

  • The distinction lies in the computation behaviour of ⊢ and ⇒:

    • ⊢ moves the reasoning forward, that's why it is destructive. It is a real computation. We reach an information we didn't have, that's why it is implicit (close to the synthetic).
    • ⇒ is static because A ⇒ B is a mere frozen object we can manipulate without performing any activation of computation. The implication rules can be seen as a way to "freeze" computation (or unfreeze when reading from bottom to top). That also explains why it is explicit, terminated.
  • Through the Curry-Howard isomorphism we can also have a simple interpretation with programs. The cut-rule is related to the process of computation while the implication rules simply manipulates application of functions f(x) as a frozen object.

EDIT : I edited my answer to a new one without mentioning Linear Logic.

Boris
  • 878
  • 6
  • 14