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)