# Course descriptions

## Fundamentals of metalogic

**Content: Completeness theorems, Model theory and proof theory.**

**Course description**: This course provides an introduction to the metatheory of elementary logic. Following a "refresher" on the basics of notation and the use of classical logic as a representation language, we concentrate on the twin notions of models and proof. An axiomatic system of first order logic is introduced and proved complete for the standard
semantics, and then we give a very brief overview of the basic concepts of proof theory and of formal set theory. The material in this course is presupposed by other courses in the Summer School, which is why it is presented first.

**Pre-requisites: ** it is assumed that students are at least familiar with logical notation for connectives and quantifiers, and can manipulate truth tables, some kind of proof system or semantic tableaux or the like. Normally they will have done a first logic course at tertiary level. Some basic mathematical competence is also presupposed, to be comfortable with the notion of a formal language, follow proofs by induction, be OK with basic set-theoretic notation and the like.

**Lecturer: **
John Slaney is the founder and convenor of the Logic Summer school. He originated in England, ever so long ago, and discovered Australia in 1977. Undeterred by the fact that it had apparently been discovered before, he gradually moved here, joining the Automated Reasoning Project in 1988 on a three-year contract because he could not think of anywhere better to be a logician. He is still here and still can't. His research interests pretty much cover the waterfront, including non-classical logics, automated deduction and all sorts of logic-based AI. He was formerly the leader of the Logic and Computation group at the ANU, and of the NICTA program of the same name.

## Introduction to modal logic

**Content: Kripke models, Hilbert calculi, Frame correspondences, Tableaux-based decisions procedures and
Propositional linear temporal logic**

**Course description: ** We cover the syntax, Kripke semantics, correspondence theory and tableaux-style proof theory of propositional modal and temporal logics. These logics have important applications in a diverse range of fields incuding Artificial Intelligence, Theoretical Computer Science and Hybrid Systems.

**Pre-requisites: ** You should have a good grounding in classical propositional and first-order logic, including material covered in the "Fundamentals of Metalogic" course. Some very basic notions from graph theory would also be useful, but are not essential.

**Lecturer: **
Rajeev Gore is currently a a professor in the ANU, and leader of the Logic and Computation research group. He was an Australian Research Council Queen Elizabeth II Fellow at the ANU from 1997-2001, a Research Fellow and later Senior Fellow at the ANU from 1994-2011, and a Research Associate at the University of Manchester from 1992-1993. He obtained his PhD in Modal Theorem Proving from the University of Cambridge in 1992.

## Overview of automated reasoning

**Content: Automated propositional theorem proving; automated first-order theorem proving; Interactive theorem proving**

**Course description: ** In many applications, we expect computers to reason logically. We might naively expect this to be what computers are good at, but in fact they find it extremely difficult. In this overview course, we look at various methods to automate logical reasoning, which are needed to support a variety of application domains.

Automated reasoning procedures are parametrized by the logic they are capable of reasoning with. We distinguish between propositional logic and first-order logic. Development and application of propositional logic procedures, also called SAT solvers, received considerable attention in the last ten years, e.g., for solving constraint satisfaction problems, applications in hardware design, verification, and planning and scheduling. Regarding automated deduction in first-order logic, we discuss applications, standard deductive procedures such as resolution, and basic concepts, such as unification. We also examine the dual problem of theorem proving, viz., generating models of a given theory, which has applications to finding counterexamples for non-theorems, and we provide an overview of some recent trends (instance-based methods, satisfiability modulo theories). Finally, we describe in some depth so-called quantifier elimination methods for theorem proving in decidable fragments of arithmetics over the reals and the integers.

**Pre-requisites: ** Elementary logic, as provided by the "Fundamentals of Metalogic" course of this Summer School.

**Lecturer: **
Peter Baumgartner is a researcher in the Canberra Laboratory of Data61 (part of CSIRO). In NICTA, the precursor of Data61, he was a Principal Researcher in Software Systems and formerly the lab manager of the "Managing Complexity" theme. Previous employments were at the Max Planck Institute for Computer Science and the University of Koblenz, both in Germany. His research interest is automated deduction, particularly for first-order logic, and its applications. He holds a PhD and a Habilitation degree in Computer Science.

## Computability and incompleteness

**Contents: Computability; recursive Functions and Turing machines; diagonalisation; Peano arithmetic and Gödel numbering; undecidability of first-order logic; incompleteness of Peano arithmetic.**

**Course Description: ** We begin with two formal accounts of the intuitive notion of computability: recursive functions and Turing machines. They turn out to be the same, hence Church's Thesis: functions that can be computed by any means are precisely the partial recursive functions. Then we revisit the old Cretan who says that all Cretans always lie, and other forms of diagonalisation argument such as Halting Problem. Next we look at an axiomatic theory of arithmetic, known as Peano Arithmetic (PA), and show how we can represent all recursive functions in PA. This will lead to Goedel numbering: a neat trick enabling us to effectively encode notions like "theorem", "proof" and "provability in PA" within PA itself. We spend a while discussing Diagonalisation Lemma and Derivability Conditions. Finally, in one fell swoop we prove undecidability of first-order logic (Church's Theorem), undefinability of truth (Tarski's Theorem), incompleteness of PA given consistency of PA (First Goedel's Theorem) and unprovability of consistency of PA given consistency of PA (Second Goedel's Theorem).

**Pre-requisites: ** Foundations of first-order logic

**Background reading: ** G. Boolos and R. Jeffrey, *Computability and Logic*.

**Lecturer: **
Michael Norrish is a Pricipal Researcher in the Canberra Laboratory of Data61 (CSIRO). He is originally from Wellington, New Zealand, and is very happy to be back in the southern hemisphere, after an extended stint in Cambridge, England. It was there that he did his PhD, and then spent three years as a research fellow at St. Catharine's College. His research interests include interactive theorem-proving, and the application of this technology to areas of theoretical computer science, particularly the semantics of programming languages.

## Deviant Logics

**Contents: ** Substructural logics as solutions to some philosophical problems; proofs in distributive substructural logics; semantics; γ and other metatheorems; substructural arithmetic

**Course description: **
We consider a range of non-classical paradigms called by the late Richard Sylvan "Relevant Logics and their Rivals". These have proof systems with restrictions on structural properties of proofs such as the ability to permute or reiterate assumptions, and semantics based on "worlds" rather like those of modal logics. Many of these logics reject the classical (Boolean) dogma that any contradiction logically entails everything; we examine that, and also the proof that preferred theories such as logic itself nonetheless admit some rules which classically depend upon that dogma. Finally, we look at the project of formulating number theory with a reduced logical base, and observe some startling effects of dropping the structural rule of weakening.

**Lecturer: **
John Slaney is the guy who spoke the truth about classical first order logic in week 1 of this summer school. In week 2 he reveals his true colours as a logical deviant who has been working on distributive substructural logics for around 40 years.

## Tableaux metatheory for propositional and syllogistic logics

**Contents: **
propositional logics (classical and non-classical ones), syllogistic
logics (traditional and others), metatheory of tableaux-style proofs, producing
complete tableaux system for semantically determined logic.

**Course description: **
The tableau approach to the logic is one of the most common approaches when forming deductive systems. For usually it is quite easy --- compared for instance to the axiomatic system --- to formulate a tableau system for a given semantically defined logic. One of the advantages of the tableau approach is that a failed tableau proof enables generation of a countermodel. On the other hand, however, it is very difficult to provide any abstract or formal notions that would allow, as in the case of the axiomatic systems, to investigate the general properties of the tableau systems, regardless of the semantics and syntax of a given logic.

The tableau metatheory is precisely a tableau system theory in which we shall consider the general notions relevant to the structures of tableau systems for various logics. It is an attempt to realize~some program of~formalization of~a~notion of tableau proof that is inspired by Melivin Fitting who said that standard tableau notions were instances of certain abstract notions [D'Agostino M., Gabbay D., Haehnle R., Posegga J., 1999, p. 5], but in fact no abstract and general notions were delivered ever.

A structure of the tableau system for a given semantically determined logic depends on the syntax and semantics of that logic. Within the presented metatheory, we shall cover the tableau metatheory for propositional logics and syllogistic logics. Hence, for such logics, we shall present the general notions of: tableau expressions, tableau rules, branch (complete, open, closed), tableau (complete, open, closed), tableau consistency, and finally, tableau system. Subsequently, we shall demonstrate how the application of these general notions simplifies a process of constructions of tableau systems for:

a) propositional logics determined by: possible worlds semantics, many- -valued semantics, semantics featuring additional components such as for instance Routley star or inheritance relation etc., and the combinations of all of them

b) syllogistic logics of such propositions as:

classical categorical propositions (such as for instance {Every man is mortal}, {No plant is human}, etc.),

modal categorical propositions {de dicto} (such as for instance {It is necessary that every man is mortal}, {It is possible that some plant is not human} etc.),

modal categorical propositions {de re} (such as for instance {Every man is necessarily mortal}, {Some plant may not be human} etc.),

numerical categorical propositions (such as for instance {At least 5 men are not philosophers}, {At most 5 men are philosophers}, {Exactly 5 men are men}, etc.)

combinations of the above kinds of propositions.

Following the presentation of the general relations between the tableau notions of our metatheory, it is easy to go forward from a given semantically defined propositional logic or syllogistic logic to a complete and sound tableau system.

So, we shall look into the problems of defining the tableau systems for various propositional and syllogistic logics from a single, unifying metatheoretical perspective, providing some common tools for the structures of various tableau systems.

**Lecturer: **
Tomasz Jarmużek
is an associate professor at Department of Logic, in Nicolaus Copernicus University. His research interests include: non-classical logics, especially positional logics (logics with operator of realization), relating logics, connexive logics; non-classical syllogistic logics; non-classical proof methods, particularly tableaux methods; semantics of relating logics motivated by philosophical problems.

## Milestones in Descriptive Complexity Theory

**Contents: **
Model-checking games, Capturing NP, Capturing regular languages, Capturing P

**Course description: **
This course is about the relationship between logical definability and computational complexity on finite structures. Computational complexity theory focuses on the amount of computational resources (e.g., time, space) for solving problems. Descriptive complexity theory focuses on the amount of logical resources (e.g., quantifiers, variables) for defining problems. Amazingly, there is a beautiful and tight connection between these two notions of complexity.

Pre-requisites: Basics (e.g., a first course) in algorithms, computational complexity, and logic.

**Lecturer: **
Sasha Rubin
is senior lecturer in the School of Computer Science at the University of Sydney. He was previously in Italy, Austria and the USA. He is broadly interested in the scope and limits of computation, and since 2014 has been working at the intersection of logic and artificial intelligence.