NCB: What is logic?

Hi, welcome back to NCB. This post is not about any specific talk. Rather, it is about a question I have been wondering about recently, after seeing philosophers going on about it at various conferences.

So, I am pretty happy to tell people that I work in logic (despite the odd looks I get). But when they ask for more details of what logic actually is, I flounder. There does not seem to be an all-encompassing answer. So, what is logic anyway?

If you're an old timer, you may say that logic is the study of truth. This is usually modelled algebraically by looking at something like (A,F), where A is some sort of (universal) algebra and F is a filter on A. For instance, for propositional logic we can take A to be a boolean algebra. For first order logic, we may like to use a polyadic algebra. The algebra A is essentially the term algebra of well formed formulae of our logic. The filter F is the set of "true" statements of our logic. Dually, we may like to look at the collection of all "false" well formed formulae, which forms an ideal I. We can rephrase logical statements in a nice way using algebra. For instance, sticking with boolean algebras, the associated logic is consistent iff I is a proper ideal. If (A,I) is consistent, then it is complete iff I is maximal in A. From this, it follows that (A,I) is consistent and complete if and only if the quotient A/I is the unique boolean algebra on two elements. For more on this view of logic, have a look at the following beautiful paper:

The basic concepts of algebraic logic. Paul Halmos. American Mathematical Monthly vol. 63 (1956) pp 363--387.

Ok, very well, so there is some nice algebra associated with the view that a logic ought to be equated with the concept of truth. But this does not seem to capture what is usually meant by logic. For instance, generations of students have had it hammered into their heads that logic is the study of reasoning. So how do we know that a given statement is true? Is it handed to us by some higher power?

The spiffy modern logician views logic as the study of consequence or deduction. That is, logic is more about "correct" forms of reasoning than about truth. Immediately we run into a problem.

Given that there is some collection of true statements, is there more than one correct way of deriving those statements? That is, is there only one logic or a multitude of logics?

If you answered yes to the first question, then you are a logical pluralist. If you answered no, then you are a logical monist. Now, for a mathematician, pluralism is perfectly reasonable. For instance, say I look at a category whose objects are smooth manifolds. Then what are the "correct" maps? Continuous? Differentiable? Smooth? Truth is, the choice of which class of maps you work with depends on what you are trying to capture. So why should it not be that way in logic?

The pluralism position has been parodied by saying something to the effect of "If you give me a piece of an argument, I'll give you a logic wherein it is valid". I highly doubt that any pluralist seriously thinks of things this way.

So, what is the answer to the subject of this post? Well, it seems reasonable to take logic to be the study of methods of deduction. If you're a philosopher, you'd probably want to change that to "...correct methods of deduction". But such a statement seems presumptious. Taking logic to be the study of deduction, it incorporates aspects of mathematics, computer science, philosophy and linguistics and should not be seen as lying completely in any one of these.

NCB: Probably True?

How many tautologies are there in propositional logic? Yeah yeah, countably many of the critters. Fine. But what happens if I pick a propositional formula at random? What are my chances of lucking out and picking a tautology? This is the question that Alan Woods set out to answer. Alan is the one in the middle.

It turns out that it matters what you mean by random. Let's think about how we would do this asymptotically. Well, for a start, we'll just represent formulae using and, or, not and parentheses. So, we may think of a propositional formula as being a binary tree. Let's focus our attention on such trees with m literals over n variables. Actually, let's fix n throughout. Let T(m) denote the total number of such trees and let True(m) denote the number of such trees that represent tautologies. Then, unsurprisingly, we can say that the probability of a tautology is the limit as m goes to infinity of True(m)/T(m). Let's call this number P(True).

Another way to consider random formulae is to take a random walk to construct a tree and see what formula we end up with. To do this, start by flipping a fair coin. If it is heads, then roll a 2n-sided die to pick a literal. Stop at this stage. If it is tails, then we are goingto make the node a boolean connective. Flip the coin again to decide if it is a conjunction or disjunction. Then, rinse wash and repeat for the two conjuncts/disjuncts. Notice that there is no guarantee that this process even terminates, but it can be shown that it does so with probability 1. Now, what we have is a well defined probability of any particular formula appearing as a result of this process. Define p(True) to be the sum of the probabilities for each tautology.

Now, it turns out that P(True) and p(True) compute different numbers, though they are related. What can be shown is that p(True) < P(True) for every n (remember that n is the number of variables we are working with). Moreover, as n tends to infinity, p(True) is asymptotically 1/(4n) and P(True) is asymptotically 3/(4n). Want precise numbers? Ok, with n=3, we get p(True) = 0.0642 and P(True) = 0.165.

Of course, there is nothing really special about counting tautologies. Why not consider the probability of hitting some other propositional formula? All this and more has been done! For the details, look no further than:

And/or tree probabilities of boolean functions. Daniele Gardy and Alan Woods.

Stay tuned for more NCB fun tomorrow!

NCB: Provability Thresholds

Welcome to the first Neo Conference Blogging (NCB) post! Today's post covers some things discussed by Andreas Weiermann, hailing from The University of Utrecht (and not just because he knows where I blog). That's Andreas on the left, standing next to Alan Woods of The University of Western Australia and Andrew Brook-Taylor of The University of Vienna. We'll see Alan again in a later NCB post.

Now, we all know that Peano Arithmetic (PA) is incomplete, thanks to that crazy hipster Goedel. Problem is, not all of us are particularly enamoured of sentences that say naughty things about themselves. Do there exist natural number theoretic statements which are true for the natural numbers but unprovable in PA? Wouldn't it be deliciously scandalous if Goldbach or Riemann were in on such a conspiracy? Wouldn't it indeed!

As a matter of fact, there do exist number theoretic statements that are "naturally independant". One example is the Goodstein Sequence. This gizmo converges, but to prove that we need to use transfinite induction up to epsilon zero. Thanks to Gentzen, we also know that this is precisely what is needed to prove the consistency of PA. So, the Goodstein Sequence cannot be proven to converge from within PA. Pretty neat, huh?

One salient feature of the Goodstein Sequence is that it converges slower than Eric Moussambani approaching the finish line in a 10,000 meter race. Perhaps it is this sort of slow convergence that is behind its unprovability? Andreas showed us that it is, as well as a whole lot more, such as how to pinpoint precisely how fast a certain function has to grow for the associated statement (say about goodstein sequences) to be provable in PA.

I won't go through the actual results, since they rely on some technical definitions and, anyway, are explained in the paper below. Here's a neat logical limit law that Andreas mentioned, though. let &phi be a sentence in the language of linear orders. For some ordinal &alpha, let us say that &alpha |= &phi if &phi holds on the set of predecessors of &alpha. Suppose that we pick some ordinal &beta at random. What is the probability that &beta |= &phi? One way is to some asymptotic trickery and define a norm functions on ordinals (I won't get into the details). Then, fix some ordinal &alpha that lies between &omega^&omega and epsilon zero. Consider the number of ordinals &beta of norm n less than &alpha such that &beta |= &phi divided by the total number of ordinals of norm n less than &alpha. Then, it turns out that the limit as n goes to infinity of this ratio is either zero or one! So, depending on your choice of &alpha, a random ordinal less than &alpha almost surely satisfies &phi or almost surely does not. I told you it was neat!

Andreas has a survey paper discussing some trickery with phase transitions and such:

Analytic combinatorics, proof theoretic ordinals and phase transitions for independence results. Andreas Weiermann.

For the phase transition characterisation of Goodstein Sequences, see:

Classifying the phase transition for Hydra games and Goodstein sequences. Andreas Weiermann

More NCB tomorrow!

Neo Conference Blogging

I have arrived back in Canberra after attending the AAL and AustMS conferences, both of which were lots of fun. While I had planned on partaking in some live conference blogging, this proved too much when coupled with going to talks, giving talks, chatting with fellow conference attendees, eating with fellow conference attendees, drinking with fellow conference attendees....oh and sleeping.

One thing that I could do is to give a summary of the conferences based on the notes that I scrawled and the handouts that were...uh...handed out. I'm not sure how valuable this would be and I would be sure to give short thrift to talks that were too far from my core interests. Not to mention the other worries brought up a while ago over at logicandlanguage.net.

So, I have decided on an alternative style of conference blogging. I will make a series of posts describing various things that I learned about at the conferences, either in official talks or unofficial chats. If I can hunt down relevant articles (preferably online), I'll point to those too. I will try to make an effort to convey the intentions of the official talks, but will not have qualms about going off on a tangent. I will also make no attempt to give a complete overview of the conferences, focusing instead on those aspects that I understood the best. In all, I think this approach is more suited to my blogging style, in as much as I have one.

Subject to other constraints, I will try and make one post a day until I run out of conference topics to talk about and return to my usual posting rate of every week or so. This time I will keep to my blogging promise. Pinky swear!

Aargh Spam

I have been on holiday for a few days and returned to find my blog covered in filthy comment spam. I have reverted the comment system back to the standard blogger system and have turned on word verification. Hopefully this will be enough to filter out the spambots.

I am on holiday for a few more days, regular posting will resume soon.