Seminar: On-Line Algorithms and Reverse Mathematics

On Tuesday, January 17, Seth Harris of Drew University will be speaking about "On-Line Algorithms and Reverse Mathematics."  The talk will be from 2:30-3:30 PM in Kemeny 004.

Abstract:

Consider a two-player game (played by Alice and Bob) in which Alice asks a sequence <a_0, ..., a_k> and Bob responds with a sequence <b_0, ..., b_k> with no knowledge of Alice's future requests. A problem P is solvable by an on-line algorithm if Bob has a winning strategy in this game, where Bob wins the game if (\bar{a}, \bar{b}) constitutes a solution to P. For example, if we take P to be a graph coloring problem, Alice plays by adding a new vertex and edges connecting it to previous vertices; Bob chooses a color for that vertex. The graph is on-line colorable if Bob has a winning strategy in this game.

Given a problem P, the corresponding sequential problem SeqP asserts the existence of an infinite sequence of solutions to P.

We will show that the reverse-mathematical strength of SeqP is directly related to the on-line solvability of P, and we will exactly characterize which sequential problems are solvable in RCA_0, WKL_0, and ACA_0. This is joint work with François Dorais.

Posted in Seminar | Leave a comment

Seminar: What do we believe?

Mingzhong Cai will be speaking this coming Tuesday, May 19.  The talk will be held in Kemeny 120 from 2:00-3:00 PM.

Title: What do we believe?

Abstract:

Mathematics is the process of certifying truth by proofs.  However, by Gödel’s incompleteness theorems, a true sentence could be unprovable. So a natural questions is, if a true sentence is really unprovable, are there ways that we can still "believe" it? We will examine a natural approach:

A sentence is called "believable", roughly speaking, if the base axiom
system (e.g., PA) proves, formally, that the sentence is provable from a
true sentence. We also need to formalize this correctly to avoid
Tarski's undefinabiliy of truth. We give an exact characterization of
the believable sentences using the notion of Sigma_n-soundness.

Posted in Seminar | Leave a comment

Seminar and Colloquium this Thursday

Jeff Hirst of Appalachian State University will give both a logic seminar and a Math Colloquium this Thursday, April 23.  The seminar will be held at 11:00 AM in Kemeny 120 and the colloquium will be held at 4:00 PM in Kemeny 008.  After seminar, at about 11:45 AM, we will have an informal "logic lunch" off campus; please let Seth Harris know if you need a ride.  As usual, tea will be held prior to colloquium at 3:30 PM.

______________________________________

Logic Seminar, 11:00 AM

Title:  Questions in reverse mathematics

Abstract:

An informal discussion of connections between second order arithmetic and notions of uniform reducibility in computability theory, including Weihrauch reducibility.

______________________________________

Colloquium, 4:00 PM

Title:  Sets and Sequences

Abstract:

Mathematical logicians often use sets and sequences to represent each other. For example, the set {3,1,0} might be associated with the binary sequence 1011. Interesting issues arise when translating between infinite sets and infinite sequences. The behavior of the translations depends on the logical framework employed. We will explore this using axiomatic set theory and subsystems of second order arithmetic.

This talk will be accessible to: graduate students

Posted in Seminar | Leave a comment

Seminar: Fully Homomorphic Encryption

Ewa Infeld will be speaking this Tuesday, April 7.  The seminar will be held at 2:00 PM in Kemeny 120.

Title: Fully Homomorphic Encryption

Abstract:

Lattice cryptography is all the rage right now, ever since in 2009 Craig Gentry used it in a theoretical scheme that allows for a wide range of computations on the encrypted text. It's still beyond the capabilities of today's computers, but the theoretical research is in full swing. It has an interesting computability aspects, which I will emphasize, and the theoretical argument is beautiful. It is not exactly the usual logic seminar fare.

Posted in Seminar | Leave a comment

Spring 2015 Organizational Meeting

There will be an organizational meeting on Tuesday, March 31, at 2:00 PM in Kemeny 120.  During this meeting we will determine the regular seminar time, as well as speakers, for the quarter.

If you cannot make this meeting but wish to regularly attend the seminar, please email Seth Harris and we will accommodate your schedule in determining the best regular meeting time.

Posted in Seminar | Leave a comment

Seminar: Small Ultrapowers

François Dorais of Dartmouth College will be speaking this Tuesday, March 3rd.  The seminar will be held at 3:00 PM in Kemeny 120.

Title:  Small Ultrapowers

Abstract: We will discuss how to make sense of ultrapowers using nonprincipal ultrafilters over finite sets in nonstandard models of second-order arithmetic.

Posted in Seminar | Leave a comment

Seminar: How hard is it to show that a sentence is unprovable?

Mingzhong Cai of Dartmouth College will be speaking this Tuesday, February 3rd.  The seminar will be held at 3:00 PM in Kemeny 120.

Title:  How hard is it to show that a sentence is unprovable?

Abstract: A large number of open conjectures in mathematics are either
arithmetic or equivalent to arithmetic sentences. Let P be such a
conjecture and fix a base theory T (e.g., ZFC). If it is the case that P
is not provable from the theory T, how hard is it to show such
unprovability fact? We show that every Pi^0_1 sentence which proves
Con(T), the consistency of the base theory T, is the unprovability of a
Pi^0_1 sentence over T. This says, even at the lowest level of
complexity (Pi^0_1, e.g., Riemann Hypothesis, or Goldbach Conjecture, or
nonexistence of an odd perfect number), such unprovability fact could be
arbitrarily hard to prove.

Posted in Seminar | Leave a comment

Seminar: Bushy-Tree Forcing and Friedberg's Lemma

Seth Harris will be speaking on Tuesday, January 20, about Bushy-Tree Forcing and Friedberg's Lemma.  The talk will be held in Kemeny 120 from 3-4 PM.

Posted in Seminar | Leave a comment

Winter 2015 Organizational Meeting

There will be an organizational meeting on Tuesday, January 6, at 3:00 PM in Kemeny 120.  During this meeting we will determine the regular seminar time, as well as speakers, for the quarter.

If you cannot make this meeting but wish to regularly attend the seminar, please email Seth Harris and we will accommodate your schedule in determining the best regular meeting time.

Posted in Seminar | Leave a comment

Seminar: Nonstandard Models and Computability Theory

François Dorais of Dartmouth College will be speaking on Tuesday, November 11, about Nonstandard Models and Computability Theory.

2:00 PM, Kemeny 120.

Posted in Seminar | Leave a comment