Logic games

(pdf version of this post)

In a recent post, Terence Tao evokes statements that cannot be formalized in first-order logic. David Corfield has left a comment to that post where he mentions “independence-friendly logic”. I thought it was a nice pretext to make a post about evaluation games.

The standard Tarskian definition of truth for first-order formulas is a recursive statement that disassembles a formula down to atomic formulas whose truth can be more or less directly established from the model. Evaluation game is another way to look at this process.

Take a formula, a model and imagine two players, one of which tries to find evidence that the formula is not true in the model

A bird’s eye view of modal logic I. Syntax and semantics

(the pdf version of this entry)
It is strange to start this blog with a text on modal logic. Historically, the language of model theory has been the language of first-order logic (although recently there are efforts to go beyond first-order context), and this choice turned out to be so good that all the other logics that use other languages has become known under the name of “non-classical logics”. Among those non-classical logics modal logics is probably the simplest and the most general class of logics.

Indeed, the least that you expect from a logic is to be able to express boolean connectives: “and”, “or”, “not” and such. Modal logics add very little to those: they add one or several so-called modalities,