Hi everyone,

Note the following updates:

– Model Theory talk this Friday (tomorrow)

– Fixed several typos

– Conference announcement at bottom (NYCAC 4)

Regards,

Jonas Reitz

This Week in Logic at CUNY:

– – – – Monday, Oct 31, 2011 – – – –

– – – – Tuesday, Nov 1, 2011 – – – –

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.’

– – – – Wednesday, Nov 02, 2011 – – – –

– – – – Thursday, Nov 03, 2011 – – – –

– – – – Friday, Nov 04, 2011 – – – –

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

Mr. Thomas Ferguson (Ph.D. Program in Philosophy, Graduate Center of CUNY) More on indiscernible types of PA

Logic Workshop

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:

– – – – Monday, Nov 7, 2011 – – – –

– – – – Tuesday, Nov 8, 2011 – – – –

– – – – Wednesday, Nov 9, 2011 – – – –

– – – – Thursday, Nov 10, 2011 – – – –

– – – – Friday, Nov 11, 2011 – – – –

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

Friday, November 11

Kit Fine (Philosophy – NYU)

– – – – Other Logic News – – – –

The New York Colloquium on Algorithms and Complexity

Friday, November 18, 2011, The Graduate Center, CUNY, Room 4102

NYCAC, the New York Colloquium on Algorithms and Complexity is an annual event. Its purpose is to give the opportunity to graduate students in New York to observe talks

of researchers from all areas of the theory of Algorithms and Computational Complexity.

Invited Speakers:

Eric Allender (Rutgers U.)

Martin Fürer (Penn State U.)

William Gasarch (U. Maryland)

George Karakostas (McMaster U.)

Michael Lampis (KTH)

Aris Tentes (NYU)

Christos Tzamos (MIT)

Vassilis Zikas (U. Maryland)

http://www.sci.brooklyn.cuny.edu/~zachos/nycac4/

– – – – Web Site – – – –

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