This Week in Logic at CUNY:

– – – – Monday, Oct 10, 2011 – – – –

– – – – Tuesday, Oct 11, 2011 – – – –

Computational Logic Seminar

Room 3309. October 11.

Time 3:00 – 4:00 PM

** ATTENTION: an unusual time. **

Speaker: Ren-June Wang (Graduate Center) – dissertation proposal Title: Timed Modal Epistemic Logic

Abstract: The thesis consists of three parts. In the first part, a survey of epistemic logic will be given. Epistemic logic was first introduced by philosophers, and later found its applications in fields such as Computer Science and Economics. This survey will cover both the philosophical debates and applications of epistemic logic and also discussions of the logical omniscience problem will be included.

The second part is the introduction of a new logical framework called timed Modal Epistemic Logic, tMEL. tMEL is extended from ordinary modal epistemic logic, MEL, by adding numerical labels to knowledge statement to indicate when the statement is known. We will argue that a logical framework with the expressivity for reasoning about both knowledge and the time of reasoning can help to resolve the problem of logical omniscience, and tMEL serves well as a logically

non-omniscient epistemic system.

Finally, we will discuss the syntactical relations between MEL, tMEL, and Justification Logic, from which the study of MEL is originated, and the focus will be on the relations between axiomatic proofs in these logical frameworks. We will first determine a proper subclass of modal logical proofs called non-circular, and prove that this class of proofs is complete. And then we will show that every non-circular MEL proof can be turned into a tMEL proof by finding suitable number labels, and prove that there is a two-way translation between proofs in tMEL and Justification Logic. Combining these results, a formal connection between non-circular proofs and proofs in Justification Logic can be established, and the whole procedure will give us an alternative algorithm for the realization between theorems in modal logic and Justification Logic.

– – – – Wednesday, Oct 12, 2011 – – – –

– – – – Thursday, Oct 13, 2011 – – – –

– – – – Friday, Oct 14, 2011 – – – –

Model Theory Seminar

Friday, October 14, 2011 12:30 pm GC 6417

Dr. Mauro Di Nasso (University of Pisa)

Nonstandard analysis in combinatorics of numbers: some examples

Abstract. By using nonstandard analysis, R. Jin [3] showed a beautiful property of sumsets of integers, namely that A + B = {a + b | a ∈ A; b ∈ B} is piecewise syndetic whenever A and B have positive Banach density. (A set of integers is piecewise syndetic if it has bounded gaps on arbitrarily large intervals. The Banach density is a reﬁnement of the upper asymptotic density.) That result raised the attention of several researchers, and has been re-proved by measure-theoretic techniques by V. Bergelson, H. Furstenberg and B. Weiss [2], obtaining an improvement. Last year, M.Beiglboeck [1] found a really nice ultraﬁlter proof of Jin’s theorem.

Starting from his initial work, R. Jin applied again nonstandard methods to attack density problems in additive number theory, producing a series of relevant results (see e.g. [4,5]). Interesting applications of nonstandard methods have also been recently obtained by S. Leth, which are related to the plane ﬁxed point problem (see [6]). The goal of my talk is to present three examples of new proofs in combinatorial number theory that suggest nonstandard analysis as a useful tool in this area of research.

The ﬁrst example is about intersection properties of sets of diﬀerences A − A which only depend on relative density. The second example is an ultraﬁlter proof of the partition regularity of injective solutions of linear diophantine equations (the point here is that, in a nonstandard setting, ultraﬁlters can be identiﬁed with points, namely hypernatural numbers). This technique also showed potentiality in the study of some non-linear equations. The third example is a property that improves on Jin’s theorem, which is obtained by elementary combinatorial arguments applied in the nonstandard setting.

(Bibliography is available here:

http://nylogic.org/ModelTheory/Fall2011/MauroDiNasso)

Logic Workshop

Friday, October 14, 2011 2:00 pm GC 6417

Professor Philip Ehrlich (Dept. of Philosophy, Ohio University) The absolute arithmetic continuum

Abstract. In his monograph On Numbers and Games, J. H. Conway introduced a real-closed field containing the reals and the ordinals as well as a great many less familiar numbers including -ω, ω-1, and a square root of ω, to name only a few, where (as the notation suggests) ω is the least infinite ordinal. Indeed, this particular real-closed field, which Conway calls No, is so remarkably inclusive that, subject to the proviso that numbers -— construed here as members of ordered “number” fields —- be individually definable in terms of sets of NBG (von Neumann-Bernays-Gödel set theory with global choice), it may be said to contain “all numbers great and small.” In this respect, No bears much the same relation to ordered fields that the system R of real numbers bears to Archimedean ordered fields.

We suggest that whereas R should merely be regarded as constituting an arithmetic continuum (modulo the Archimedean axiom), No may be regarded as a sort of absolute arithmetic continuum (modulo NBG). We draw attention to the unifying framework No provides not only for the reals and the ordinals but also for an array of non-Archimedean ordered number systems that have arisen in connection with the theories of non-Archimedean ordered algebraic and geometric systems, the theory of the rate of growth of real functions and nonstandard analysis.

In addition to its inclusive structure as an ordered field, No has a rich algebraico-tree-theoretic structure that emerges from the recursive clauses in terms of which it is defined. In our treatment of No, which differs markedly from Conway’s treatment, the

algebraico-tree-theoretic features of No are brought to the fore and play central roles in the aforementioned unification of systems of numbers great and small and in some of the more revealing

characterizations of No as an absolute continuum.

Seminar in Logic and Games

Friday, October 14, 2011, 4:15 PM

Room 4419, CUNY Graduate Center

Yair Tauman (Economics Department, SUNY at Stony Brook)

The Decision to Attack a Nuclear Facility: The Role of Intelligence

Abstract: We study the impact of intelligence in a simple model of two rival countries. Country 1 wishes to develop a nuclear bomb. Country 2’s aim is to frustrate 1’s intention. She operates an intelligence system (IS) on 1 of a certain precision. Based on the signal of the IS, 2 decides whether (or with what probability) to attack 1. Several results are quite surprising. If the IS is sufficiently accurate, 2 chooses not to attack 1 if the signal is “nb” ( not build a bomb). But even if the signal is “b” still 2 does not attack 1 with significant probability, even though her worst case is allowing 1 having a bomb. However, 2 acts aggressively if the IS is less accurate. She attacks with certainty if the signal is “b” and she even may attack 1 if it is “nb”. Furthermore, BOTH countries benefit from a higher precision IS.

Joint work with Dov Biran

Next Week in Logic at CUNY:

– – – – Monday, Oct 17, 2011 – – – –

– – – – Tuesday, Oct 18, 2011 – – – –

– – – – Wednesday, Oct 19, 2011 – – – –

– – – – Thursday, Oct 20, 2011 – – – –

– – – – Friday, Oct 21, 2011 – – – –

Model Theory Seminar

Friday, October 21, 2011 12:30 pm GC 6417

Professor Roman Kossak (The City University of New York)

Models and types of PA, IV

Abstract. Countable recursively saturated and short recursively saturated models will be used in an example of an abstract elementary class with a special property.

Logic Workshop

Friday, October 21, 2011 2:00 pm GC 6417

Dr. Daisuke Ikegami (University of Helsinki)

Ω-logic and Boolean-valued 2nd-order logic

Abstract. Ω-logic discusses “forcing absoluteness”, which is the preservation of truth-values of statements between ground models and their set forcing extensions. Ω-valid sentences are those which are true in any set forcing extension, while Ω-provable sentences are those which are true in all transitive models of ZFC that are closed under some “universally Baire sets”, that are the key notion tying forcing absoluteness with large cardinals. The Ω-conjecture states that those two collections of sentences are exactly the same assuming the existence of a proper class of Woodin cardinals, that are the essential large cardinals when discussing forcing absoluteness. Although the Ω-conjecture is consistent and its truth value does not change by forcing, it is still open whether it is true or not.

Boolean-valued 2nd-order logic is a Boolean-valued logic for 2nd-order statements: “subsets” and “relations” of a given 1st-order universe M can be seen as functions sending n-tuples of elements of M to elements of a given complete Boolean algebra B and one can assign an element of B to each 2nd-order formula as a truth value. Boolean valid sentences are those 2nd-order sentences whose truth values are 1 in any such assignment while one can define Boolean provable sentences with the help of universally Baire sets and suitable “Henkin models,” which are the key notion when investigating 2nd-order logic. We do not know whether those two collections of sentences are the same while any Boolean provable sentence is Boolean valid.

In this talk, we introduce Ω-logic and Boolean-valued 2nd-order logic and discuss the connection between them. We show the following two things:

1. Ω-validity is as complex as Boolean-validity. As a corollary, Boolean-validity is Δ2 in set theory assuming Ω-conjecture.

2. If Boolean valid sentences are exactly the same as Boolean provable sentences, then the Ω-conjecture holds.

The first result contrasts the fact that the validity of full 2nd-order logic is Π2-complete in set theory.

This is joint work with Jouko Väänänen.

Seminar in Logic and Games

Friday, October 21, 2011, 4:15 PM

Room 4419, CUNY Graduate Center

Matthew Moore (Philosophy – Brooklyn College)

– – – – Other Logic News – – – –

NERDS: New England Recursion theory and Definability Seminar

The New England Recursion theory and Definability Seminar will start this fall with the first meeting on Sunday October 30 at Assumption College in Worcester, MA. The general plan for the seminar is to meet once a semester to give people working in recursion theory and related areas (reverse mathematics, randomness, computable analysis, computability in uncountable settings, etc.) in the northeast region a chance to listen to three or four talks and to facilitate initiating and continuing joint projects. Of course, we welcome attendance by anyone interested in these topics regardless of your area of research and our intention is to view recursion / computability theory in a broad manner. We do not have funding to cover any travel or meal expenses.

The specific details of our initial meeting are below. For anyone who wishes to be put on a regular email list for seminar announcement, please send your name, affiliation (if appropriate) and email address to

Reed Solomon, david.solomon@uconn.edu

Reed will send out additional information (such as the building and room information at Assumption College) to the seminar email list as it becomes available. We will also have a website set up before the first meeting, although probably not for another week or so.

The details of the first meeting are as follows:

Sunday October 30 at Assumption College in Worcester, MA

(The building and room information, travel instructions, parking information and so on will be distributed via the seminar email list as it become available.)

Program

11:00 – 12:00 — Marcia Groszek (Dartmouth), An open problem in reverse mathematics and infinitary combinatorics

12:15 – 2:00 — Lunch and discussion time

2:00 – 3:00 — Russell Miller (Queens College, CUNY), Computable differential fields

3:15 – 4:15 — Johanna Franklin (University of Connecticut), Degrees which are low for isomorphism

– – – – Web Site – – – –

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