Talk:Linear logic

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated C-class, Low-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
C Class
Low Priority
 Field: Foundations, logic, and set theory
WikiProject Philosophy (Rated Start-class)
WikiProject icon This article is within the scope of WikiProject Philosophy, a collaborative effort to improve the coverage of content related to philosophy on Wikipedia. If you would like to support the project, please visit the project page, where you can get more details on how you can help, and where you can join the general discussion about philosophy content on Wikipedia.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.

Better Introduction[edit]

Please consider motivating the rest of the article with the resource discussion near the end. The article proceeds too quickly into explaining the symbols and formal rules without giving any clue what they mean "intuitively" (not meaning to pun on intuitive logic)


  • better examples
  • connexion to proof nets, ludics, etc.
  • linear type theory (Wadler et al)
  • Fix symbols (most symbols show up as boxes) —Preceding unsigned comment added by (talk) 10:11, 30 July 2008 (UTC)

--Kaustuv Chaudhuri 00:03, 2 Jun 2004 (UTC)

  • make it less chatty. Please snip "non-encyclopedic" parts.

--Kaustuv Chaudhuri 09:06, 2 Jun 2004 (UTC)

There are two kinds of non-commutativity: self-dual and non-self-dual. Discussion required. Charles Stewart 02:47, 12 Aug 2004 (UTC)

"While this freeness of truth is usually what is desired, for example in formal mathematics, but for many applications of logic truth can be abstract and unwieldy." I think the word "While" should be removed, changing the sentence to 2 sub-sentences joined by the conjunction "but". But I don't understand the subject well enough to know if that's what he meant to say. Art LaPella 02:14, Aug 21, 2004 (UTC)

Either the "but" or the "while" should be removed. On a more general note, the present version of this article has major expository issues: it is currently not accessible to the lay reader. Examples that should be illuminating are obscure and ill-constructed. — Kaustuv 03:27, 2004 Aug 21 (UTC)

Internal and external choice[edit]

Can someone please confirm that the names given for the & and ⊕ operators are really internal and external choice, respectively. The reason I ask is that this is exactly the opposite to what I've encountered in other contexts, e.g. process algebra, where an internal choice is one you can't control and an external choice is one you can. I didn't find the names in the papers linked off the bottom of the article (but I only skimmed them).--Malcohol 14:47, 11 August 2006 (UTC)

I have removed the names as I don't think they are common, and anyway it is probably not meant to be opposite to other computational contexts. 18:38, 11 August 2006 (UTC)

Intuitionstic linear implication[edit]

I expect the answer is {{sofixit}}, but:

Intuitionistic linear logic (ILL) allows only a single conclusion. Unlike CLL, connectives in ILL do not have perfect duals... As a result, linear implication is a basic connective in ILL.

The statement is correct, but the rules for linear implication are not given in the article. They should be. 03:52, 2 January 2007 (UTC)

Does linear logic have a not function?

To answer the previous two questions: there is a linear negation, but it and linear implication are not given in the table of rules (for the CLL sequent calculus). I can't edit that table, and there is some sense to its organisation for purposes of symmetry, and in fact there are (now) explained after it, but I'll try to make that clearer. --Toby Bartels 20:29, 29 June 2007 (UTC)
It depends what you mean by a "not". There's a perfectly good involution which (in the presence of contraction and weakening) would be equivalent to classical not, but which is not the same as linear negation (implies falsity). Francis Davey 09:14, 18 October 2007 (UTC)

Mostly, this makes sense, but the explanations for the & and ? operators really need some work. Can someone who understands this look into it?

I really agree with this; we need to talk about implication in ILL. This (I think) introduces a lot of new complications though, as we need to talk about assumptions on the LHS of the turnstile, which is very different from the presentation given here. mkehrt (talk) 12:07, 26 June 2009 (UTC)

It makes no sense to give the two inference rules for ILL's linear implication when all the context we have is the one-sided presentation of CLL. This is a case for a new article, which is a bit of a job. — Charles Stewart (talk) 12:43, 26 June 2009 (UTC)
Good point. I'm not sure LL really needs two articles, but given the depth of presentation in this article, it may make sense to split it. I'm not really the person for the job, though, so if anyone knowledgeable is up to the job...? —Preceding unsigned comment added by Mkehrt (talkcontribs)
I am not sure I see the need to specifically discuss ILL implication (as opposed to just adding more discussion of implication in CLL) in the current version of the article. What specifically did you (Mkehrt, Charles, ...) have in mind? Noamz (talk) 04:48, 27 June 2009 (UTC)

Vending-machine example[edit]

I know it seems less professional, but the vending-machine example was much clearer to me when it was in first person rather than third. Having just read a bunch of stuff on linear logic, I think that I finally understand things (at least as far as the distinction between times and par; 1 versus bottom is still subtle). So I'm going to rewrite much of that (especially the bit on par) using what seems the clearest language of all (IMHO): the second person! --Toby Bartels 20:32, 29 June 2007 (UTC)

first example ?![edit]

The introduction's example is wrong:

<< One example: churning cream into butter. Suppose we represent a quart of cream by the proposition A, and a pound of butter by B. To state the fact that a quart of cream can be churned into a pound of butter, we might write the implication A ⇒ B. But in ordinary (classical or intuitionistic) logic, from A and A ⇒ B one can conclude A ∧ B. >>

Seems to state that "(A ∧ (A ⇒ B)) ⇒ (A ∧ B)" does not fit reality. Actually, what is false here is expressing "a quart of cream can be churned into a pound of butter" using "A ⇒ B". There is no implication here in the formal logic sense of the term. There is "potential transformation" instead. So that, indeed, later conclusions are wrong, too...

Sorry not to propose a better example -- I do not know much about linear logic (the reason why I was reading the article ;-). This one, sure, cannot properly convince any reader that the topic is of highest interest :(.

Denis --Denispir (talk) 13:50, 10 March 2009 (UTC)

possible new version[edit]

<< One example: cream can be churned into butter. Let us try to express that using classical logic. Suppose we represent the fact that we have a quart of cream by the proposition A, and a pound of butter by B. To state the fact that a quart of cream can be churned into a pound of butter, a naive attempt may be to write the implication A ⇒ B. But in ordinary (classical or intuitionistic) logic, from A and A ⇒ B one can conclude A ∧ B, meaning that we have now both cream & butter.

What is wrong in our trial is to "translate" the possible churning of cream into butter using a logical implication. This shows anyway that classical if often unable to express simple facts of the reality.

[Please improve and correct, for english is not my mother tongue.] Denis --Denispir (talk) 14:17, 10 March 2009 (UTC)

I'm not an expert in linear logic, though I am familiar with logic, and the example reads as nonsense to me. 'Suppose we represent a quart of cream by the proposition A' - a quart of cream is not a proposition for a start. Ridiculous. (talk) 10:52, 10 April 2009 (UTC)

It is in linear logic. Note that one interpretation of LL is as a logic of resources rather than truths. A proposition is merely a syntactic structure, and any "meaning" we give this is only a product of how we interpret it. In propositional logic (the terminology here is not so great), we interpret these propositions as truths we want to prove the truth of. In LL, however, we interpret these propositions as resources (i.e., things) we want to prove the existence of. mkehrt (talk) 22:37, 26 June 2009 (UTC)

Major revision[edit]

I made a first pass at improving the article -- comments welcome. I have some time now to work on this article -- I'd still like to add a section on models of linear logic, and give more explanation of the applications of linear logic. Noamz (talk) 22:13, 10 June 2009 (UTC)

A context ( Γ, Δ) is a list of propositions A1, ..., An ??[edit]

What does the sentence above mean? The list A1, ..., An does not match the pattern ( Γ, Δ), so I am at a loss what Γ and Δ thus introduced mean individually. Could somebody please rephrase this sentence? Marc van Leeuwen (talk) 11:17, 2 February 2011 (UTC)

This means that either Γ or Δ can be used as a metavariable for a context. Note that the parentheses are not in math mode, and indicate a parenthetical remark in the sentence, rather than being part of the notation. mkehrt (talk) 04:16, 11 February 2011 (UTC)
Yes this is a standard notational convention, but there's no harm in being more explicit. I've edited the paragraph to do this, and also tried to make a few other minor improvements. Noamz (talk) 16:13, 12 February 2011 (UTC)

On this note, the turnstile doesn't appear to work in the equations the way it's explained in the text; in the text it appears to be an infix operator, but in the equations symbols only appear after it. Also, in the semi-distributivity formula, there is a symbol - a curly p or rho - which does not appear anywhere else and appears to be some sort of binary operator. Cyrapas (talk) 00:12, 4 April 2013 (UTC)

The Classical linear logic of Girard has an operator (the dual introduced in the article) which has the property that A |- G is the same as |- ~A, G (where I am using ~ for the dual - sorry I don't know how to do this sort of thing in wiki code). In other words you can always shift formulae from the left to the right hand side of the turnstile. For economy one can then present the logic with no formulae on the left hand side. I hope that explains the turnstile question. I think the "curly p" you see if an upside-down ampersand. It is an infix operator - the multiplicative "or". The intuitive way to think of it in proof-style is that A p B means "if I have a refutation of A I can prove B AND if I have a refutation of B I can prove A" (where I have used the "p" letter for the upside-down ampersand, again because I don't know how to do this right). Francis Davey (talk) 09:20, 4 April 2013 (UTC)

algebraic properties[edit]

i think the section "remarkable formulae" should be greatly expanded (to something like the equations and implications listed here: and here: and propably brought closer to the beginning. as someone unfamiliar with sequent calculus, i find these formulae (together with the vending machine analogy) are very helpful for understanding the topic. — Preceding unsigned comment added by Opensofias (talkcontribs) 08:48, 26 July 2014 (UTC)

Doubtful use of the concept of a proposition[edit]

Suppose we represent a candy bar by the atomic proposition candy, and a dollar by $1.[dubious ]

But a proposition refers to a state of affairs, an assertion about the world that can be true or false -- not to an object. Does the original source really make this conflation?

We seem to be entering the "Politicians lie in cast iron sinks" territory of verbal recombination. See (talk) 12:42, 2 May 2015 (UTC)

Changed statement to Suppose we represent having a candy bar by the atomic proposition candy, and having a dollar by $1. Ghartshaw (talk) 05:04, 27 October 2015 (UTC)

Is Girard one-sided sequent calculus the best way to explain the logic?[edit]

It's true that the one-sided sequents give a more economical presentation, and it's easier to translate the one-sided form into further understandings (like the resource lambda calculus). But it's a harder presentation to grasp. I think it would be easier to first explain things in the two-sided form, then later explain how it can be translated to one-sided form (and explicitly show how the dual harmony develops).

First, for people who aren't used to one-sided sequents, that's an extra complexity to get over.

But, even for people who are familiar with the one-sided form, they're still going to be stuck on grasping the rules until they've fully internalized the duality rules. And, since those rules are the definition of the operators, and the duality rules are hard to intuitively grasp without already grasping what the operators do, they have to see the entire circle and grasp it all at once instead of just going step by step.

For example, look at the conjunction rules. If X entails A and Y entails B then X,Y (or XxY) entails AxB; if a single premise multiset Z (such as XxY) entails both A and B, then it entails A&B. That's all you need to understand multiplicative vs. additive. Plus, you immediately get that it's multiplicative conjunction in the premises and disjunction in the conclusions. Sure, you need almost twice as many rules, but they're all rules that mean something on first reading. By contrast, the one-sided form requires you to have already internalized the duals of each operator—which is hard to do before you understand what the operators mean, and since the operators are defined by the very rules you're trying to understand… -- (talk) 02:25, 3 December 2016 (UTC)

Intuitive descriptions of the operators?[edit]

Another way of solving the same problem mentioned in the last section might be to give a good-enough intuitive explanation for each operator before getting into the rules. Once you do that, the more economical one-sided presentation of the rules should be fine. I can think of three ways to do this.

The first is just moving (maybe a shortened version of?) the resource explanations up top, although this has the problem with intuitively defining par. You can put it in terms of trading ("A par B" means that we can trade the negation of A to get B), but that's not nearly as clear as alternative vs. cumulative conjunction. (In the case of the vending machine, "($1 negated) par (candy & chips & drink)" almost works, but it also means that we could trade our choice of candy, chips, and drink for $1, which is how money works, but not how vending machines work…)

Another way to do it is in terms of provability: "A or B" means "it's provable that if not A then B, and vice-versa", but "A par B" means "if A is disprovable then B is provable, and vice-versa", and so on.

A third way, which may be a lot more verbose (and basically equivalent to showing the two-sided sequent rules), is to show how "and" splits into "times" and "with" and how "or" splits into "plus" and "par" by directly showing what taking away weakening does. We can define "and" as a language-internal notation for a comma in the premises, or as a way of conjoining the premises of two separate sequents, and it's trivial to prove that these definitions are the same. But any such proof requires weakening, which is what we're giving up. So, if they're not equivalent definitions, let's let them define different things: "times" is the comma in the premises, while "with" is conjoining separate premises. And likewise for the disjunctives. (I realize that my explanation here is terrible, but maybe someone can come up with a better one.) -- (talk) 03:34, 3 December 2016 (UTC)