*Computational Logic Seminar*

Room 3309. Time 2:00 – 4:00 PM

Tuesday, November 1.

Speaker: **Hidenory Kurokawa** (Graduate Center)

Title: Tableaux and Hypersequents for Logic of Proofs and Provability .

Abstract. Goedel-Lob logic (GL) has been used as the fundamental modal logic of formal provability in arithmetic (e.g., PA). Logic of Proofs (LP) was introduced by Artemov to study combinatorial structures of proofs from the point of view of explicit modality.

It is a natural question how we can combine GL and LP. Variants of the combined logic of proofs and provability (LPP, LPGL, and GLA) have already been explored. Arithmetic interpretations for LPP and LPGL have been established, and Fitting-style semantics is given for GLA. However, no tableau systems or sequent calculi for them have been proposed so far. In this talk, we present a cut-free prefixed tableau system and a cut-free hypersequent calculus for GLA. The main goal is to prove cut-admissibility of the hypersequent calculus for GLA by a semantic method. We prove this by using a translation from the prefixed tableau system to the hypersequent calculus. Along the way, we also study similar proof systems for a combined logic (GrzA) of proofs and strong provability, which means `provable in PA and true.’

*Set Theory Seminar*

Friday, November 4, 2011 10:00 am GC 6417

Mr. **Spencer Unger** (Carnegie Mellon University)

New Branch Lemmas

Abstract. A branch lemma is a statement of the form “Forcing of type X cannot add a branch through a tree of type Y.” Branch lemmas often form an essential part of arguments involving forcing and large cardinals. As a warm up I’ll state and prove two classical branch lemmas. As a sample application, I will give a brief sketch of a forcing argument due to Mitchell for obtaining the tree property at ω2 from a weakly compact cardinal. I will then state a generalization of each classical branch lemma. I will prove one of the lemmas and mention the technique of the proof of the other. To conclude I will mention applications of both lemmas and time permitting I will sketch the proof of one the applications.

*Model Theory Seminar*

Friday, November 4, 2011 12:30 pm GC 6417

Speaker TBA

More on finitely generated models of PA

*Set Theory Seminar*

Friday, November 4, 2011 2:00 pm GC 6417

**Dr. Samuel Coskey** (The Fields Institute and York University) The Borel Tukey order on cardinal invariants

Abstract. Many cardinal invariants admit a natural definition of the form min { |F| : ∀x ∃y∈F xRy }

where R is some relation, x ranges over the domain of R, and F ranges over subsets of the codomain of R. For instance, the dominating number is defined by the relation ≤* (domination mod finite) on ωω.

If R and R’ are two relations, then R is said to be above R’ in the Tukey order iff there exist maps φ from the domain of R’ to the domain of R and ψ from the codomain of R to the codomain of R’ such that φ(x) R y ⇒ x R’ ψ(y)

The Tukey ordering is important because it corresponds very closely with inequality of the associated cardinal invariants. However, in practice one is more concerned with true inequalities, that is, inequalities which hold in all models of ZFC. For this reason, Blass proposed that we consider the Borel Tukey order, which is defined as above except that now R,R’ are assumed to be on standard Borel spaces and the maps φ and ψ are required to be Borel. The Borel Tukey order is known to have applications of a combinatorial nature in areas such as parameterized diamond principles and Borel equivalence relations.

In this talk, we will build upon some work of Mildenberger on the Borel Tukey ordering for a family of unsplitting relations. More generally, we will discuss the similarities and differences between the usual ordering and the Borel Tukey orderings on a modest collection of classical combinatorial cardinal invariants. For this, we will need to widen our attention slightly to cardinals which admit a definition of the form

min { |F| : P(F) & ∀x ∃y∈F xRy }

where R is as above and P is some second order property of the families F. This will allow us to consider the Borel Tukey order on many more cardinals. For instance, we shall be able to speak of the pseudo-intersection number, which is defined to be the least cardinality of a family F such that F is centered and ∀x∈[ω]ω ∃y∈F such that x⊄*y.

This is joint work with Juris Steprāns and Tamás Mátrai.

Logic and Games Seminar

Friday, November 4, 2011 4:15 pm GC, Room 4419

Professor Robert Lurz (Brooklyn College)

Belief and Belief Attribution in Animals

Next Week in Logic at CUNY:

*Set Theory Seminar*

Friday, November 11, 2011 10:00 am GC 6417

**Professor Thomas Johnstone** (NYC College of Technology (CUNY)) What is ZFC set theory when the power set axiom is removed?

Abstract. When prompted, many set theorists offer the following list of axioms: extensionality, pairing, union, infinity, separation, foundation, replacement and choice. In this talk we will prove that this formulation of set theory without power set is weaker than commonly supposed, and it is inadequate to prove several basic facts often desired in its context. For example, infinite successor cardinals can be singular, Los’ ultrapower theorem can fail, Gaifman’s theorem can fail (i.e. cofinal Sigma_1-elementary embeddings need not be fully elementary), and Sigma_1-formulas need not be closed under bounded quantification. Nevertheless, these deficits are completely repaired if one uses collection, rather replacement in the

axiomatization above. This is joint work between Joel Hamkins, Victoria Gitman and myself, and a pre-print is available at

http://arxiv.org/abs/1110.2430.

*Model Theory Seminar*

Friday, November 11, 2011 12:30 pm GC 6417

Professor Alfred Dolich (Kingsborough Community College)

Integer parts of real closed fields

*Logic Workshop*

Friday, November 11, 2011 2:00 pm GC 6417

**Professor Samson Abramsky** (Oxford University)

Independence in Quantum Foundations and Social Choice

*Computational Logic Seminar*

Room 3309. Time 2:00 – 4:00 PM

Tuesday, November 11

Kit Fine (Philosophy – NYU)

– – – – Web Site – – – –

The majority of this information, including an interactive calendar of future events, can be found at our website: