#proof theory

[pv1isalsoimportant]

As a consequence of this lack of interest, we do not have a reasonable answer to even the trivial question!

(The question being what it means for proofs to be equivalent.)

(Amir Akbar Tabatabai on why we should do categotical proof complexity.)

[qonphuceingey]

I’ve been thinking a bit about AI and its cognition for the past few days.

When an AI thinks about an problem and figured out the idea to solve it, there are a couple cases for the solution.

Case 1) It already knows the solution. It just presents the solution near instantly.

Case 2) If it synthesises n different ideas together linearly, like a chain of logical deduction with n axioms in use along the way, it can arrive at the solution. The n ideas needed are probably whatever the question is about. The AI already knows each of these n ideas in the way mentioned in the previous case. This is somewhat like applying a known theorem to a problem.

Case 3) If it needs to chain asymptotically more than n ideas to get the solution (like n^{2} ideas or e^{n}). Once all of these sub problems are solved, this reverts back to a Case 2 problem. While there are different algorithms, like nlogn or n!, that I could use to describe the problems that fit into this case, and I’m sure I could extend these categories infinitely by picking bigger and bigger algorithms, I don’t think it really matters how much further over n it is, since it all depends on what the AI already knows. The point is that problems in this category require solving sub problems.

Currently I feel like AI and LLMs are stuck at the level of category 2, and probably only for low values of n. I’m thinking of this as something like halfway up the category.

I think once they get into the level of category 3, where they’re not just applying information we already know but sort of synthesising it themselves, that’s when we get a runaway AGI effect, since they can perform research on themselves.

It’s also interesting to think about the recursive nature of discovery and invention and research. You should really be able to solve any problem by applying the method in category 2 to it, and attempting to guess what ideas you’d need to prove for each stage and checking their validity via the exact same method.

I think AIs current limitations on this are probably things like the context window (so they forget stage 1 once they hit stage 17) and perhaps the ability to recursively apply this idea. I don’t know enough about how they’re training the models to say if they’ve been trying to implement this recursion or not, although I assume they have, as this is a pretty obvious idea to try.

What I do think the AIs are pretty good at right now is guessing what ideas might be useful to try and prove. I’m sure they could be better, but it’s impressive they’ve risen to essentially my level at this task. To be fair though, the AI typically goes for the most surface level answer possible, and doesn’t try to get deeper into a topic unless prompted. This lack of curiosity might be a downside too. They certainly know enough and can think clearly enough to come to these conclusions, but they can’t be bothered to since a standard answer is just as well received generally.

Very interesting. I’m excited to see where it goes.

[studyinglogic]

Normative pragmatics and proof theory: unfinished notes on Restall

How can proof theory give us a normative account of communication? This post is an exposition of (what I think is) Restall’s answer.

These are my (unfinished) notes on a talk by Restall on proofs and what they’re good for: very roughly, this is my recap of the part on normative pragmatics and proof theory. I originally wrote them up for a friend and the notes stop abruptly; I leave them here as a quick primer for those who may be interested. Further detail can be found in Restall’s paper on multiple conclusions. 

Notation: I use X and Y for sets, A and B for propositions, and CAPITALS WITH ITALICS for logical connectives.

I. What does proof have to do with communication?

People assert things. They also deny things. These assertions and denials are part of communication. There are norms on these assertions and denials. We can be more precise by representing assertions and denials as [X:Y], where X is a set of assertions and Y is a set of denials.

It is out of bounds (intuitively, not legitimate) to assert and deny certain things at the same time. For example, we have the norm of Identity.

Identity: [A:A] is out of bounds. We can’t assert A and deny A at the same time.

Weakening: If [X:Y] is out of bounds, then so is [X, A:Y] and [X:Y, A]. If we can’t assert X and deny Y, then adding anything to the assertions or the denials doesn’t change that. (This doesn’t hold in cases of nonmonotonicity - like with typicality assumptions.)

Cut: If [X, A:Y] and [X: A,Y] is out of bounds, then so is [X:Y]. If asserting A or denying A is out of bounds, then the original position must have been out of bounds anyway.

These norms are named that way because they mimic the familiar structural rules of the sequent calculus. Replace “:” with the turnstile. Identity is then the sequent calculus structural rule of identity, and so on.

Our rules of communication give us our structural rules for proof. 

II. How do we define logical connectives?

What does it mean to define words? Here’s a take on it: something is square iff it is a rectangle and has all sides equal. On this picture, definitions are more like abbreviations. Notice that we’re using logical vocabulary for our definitions: square are things which are rectangles and have all sides equal. This means that we use logic in our definitions. How do we define logical words, then? 

We can define logical connectives in terms of other connectives. How can we define A AND B? Well, we can define it in terms of NOT and OR, such that A AND B is defined as NOT A OR NOT B. How do we define NOT A? Well, we can take it to be an abbreviation for IF A THEN FALSUM. And so on. But this process need never end.

Another way of defining logical terms is by how we use them. Take AND. When can we assert A AND B? We can give the following rule: [X, A AND B: Y] iff [X, A, B:Y]. Take that as definitional. When do we deny A AND B? Well, we put A AND B on the right of the turnstile (since that’s where denials go), and grind through the definitions until we get our answer. (Restall’s slides use Cut.)

[pv1isalsoimportant]

Paper of the week.

[pv1isalsoimportant]

Hilber-style proof systems will be the bane of my existence. In this house we stan sequent calculus.

[superpte]

No Philosophy, No Science, No Science, No Philosophy

No Advancing Philosophy, No Advancing Science, No Advancing Science, No Advancing Philosophy The philosophical method consists in reasoning from happenstance(s) to generalities, and the scientific method consists in making sure those general guesses are right in some sense. Both inquiry methods are entangled, but philosophy always comes first, even in the most abstract, mathematical or…

View On WordPress

[logichangouts]

New Seminars Coming Up!

The reading group hangouts dedicated to "An introduction to non-classical logic: From if to is" by Graham Priest are officially over. However, the following two ideas for further readings came up during our meetings:

1. Algebraic approach to non-classical logics The idea is to have an advanced seminar based on the book of the same title by Helena Rasiowa. The knowledge of basic algebra is advised, but we will not discourage participants who are new to the field either.

See the book here.

2. Goal-directed proof theory This will be an entry-level seminar for people interested in proof theory, relevance, programming, intuitionistic logic and other non-classical logics. The hangout will be roughly based on the book of the same title by Dov Gabbay et al.

See the book here.

Both seminars may feature other (shorter) texts and an occasional short talk. We will pick a date for each meeting after we have the final list of participants, so  please let me know (by sending a PM or an e-mail) if you are interested in participating in any of the following online hangouts.

Each seminar is planned for ca 20 meetings which will happen in May and June, and continue from mid-September 2018.

[characteristica-blog]

by Sara Negri

«The axiomatic presentation of modal systems and the standard formulations of natural deduction and sequent calculus for modal logic are reviewed, together with the difficulties that emerge with these approaches. Generalizations of standard proof systems are then presented. These include, among others, display calculi, hypersequents, and labelled systems, with the latter surveyed from a closer perspective». Non-normal modal logics: a challenge to proof theory by Sara Negri  «A general procedure that follows the guidelines of inferentialism is presented for generating G3-style sequent calculi for non-normal modal logics on the basis of neighbourhood semantics»