Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Some background: Łukasiewicz many-valued logics were intended as modal logics, and Łukasiewicz gave an extensional definition of the modal operator: $\Diamond A =_{def} \neg A \to A$ (which he attributes to Tarski).

This gives a weird modal logic, with some paradoxical, if not seemingly absurd theorems, notably $(\Diamond A\land \Diamond B) \to \Diamond (A\land B)$. Substitute $\neg A$ for $B$ to see why it's been relegated to a footnote in the history of modal logic.

However, I've realised that it's less absurd when that definition of a possibility operator is applied to Linear Logic and other substructural logics. I have an informal talk about this earlier in the month. A link to the talk is at http://www.cs.st-andrews.ac.uk/~rr/pubs/lablunch-20110308.pdf

(One of the reasons that I asked about substructural modal logics was to compare the expressiveness of those logics with the use of this operator.)

Anyhow, the only non-critical work that I found a reference to is a talk by A. Turquette, "A generalization of Tarski's Möglichkeit" at the Australasian Association for Logic 1997 Annual Conference. The abstract is in the BSL 4 (4), http://www.math.ucla.edu/~asl/bsl/0404/0404-006.ps Basically Turquette suggested applications in $m$-valued logics for $m$-state systems. (I've not been able to obtain any notes, slides or other content of this talk, so I would appreciate hearing from anyone who has more information.)

Is anyone here aware of other articles or papers on this?

(I don't have any applications for it, but I find the properties to be interesting enough to merit a paper.)

share|improve this question
I've never seen anything about this modality, but I did like your slides. If nothing turns up here, you might also try MathOverflow (or even the FOM mailing list). –  Neel Krishnaswami Apr 7 '11 at 13:33
I didn't know about MathOverflow. Thanks! –  Rob Apr 8 '11 at 9:10
I've posted the same question to MathOverflow mathoverflow.net/questions/61134/… –  Rob Apr 9 '11 at 11:55
I've never heard about Tarski's Möglichkeit before, but I'm curious whether you are sure the interpretations $\Diamond A = A⅋A$ and $\Box A = A\otimes A$ are faithful? You know there are other possible translations of the (classical/intuitionistic?) proposition ¬A→A even into classical MALL... –  Noam Zeilberger Apr 10 '11 at 17:17
@Noam It has nothing to do with interpreting formulae in MALL. Those equivalences hold in Łukasiewicz Logic, which corresponds to AMALL plus $((A\to B)\to B)\to ((B\to A)\to A)$. –  Rob Apr 12 '11 at 19:36
show 5 more comments

1 Answer 1

Rob, I didn't know this was called the Tarskian Möglichkeit, but Martin Escardo and I have been studying this operator (A -> B) -> A, in the more general case when falsity is an arbitrary formula B, for the past few years, mainly in connection with computational interpretations of classical theorems. If we let B be fixed, then we define

J A = (A -> B) -> A

It is easy to show that this is a strong monad. We call it the "selection monad" or the "Peirce monad", as J A -> A is Peirce's law. In fact, the seemingly absurd theorem you mentioned in your post is the cornerstone for our work on interpreting ineffective principles such as the Tychonoff theorem, for instance. Have a look at some of our papers, e.g.

Martín Escardó and Paulo Oliva. Sequential games and optimal strategies. Proceedings of the Royal Society A, 467:1519-1545, 2011.

Martín Escardó Paulo Oliva, The Pierce translation. Annals of Pure and Applied Logic, 163(6):681-692, 2012.

Or others found on our webpages: http://www.eecs.qmul.ac.uk/~pbo/

Any paper which mentions "selection functions" or "game" is related to the operator you are asking about.

I must warn we have been studying this operator in the setting of intuitonistic (minimal) logic. But I find it very interesting that you are looking at this in the more refined (substructural) settings of linear logic and Lukasiewicz logic.

Best regards, Paulo.

share|improve this answer
add comment

Your Answer


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.