Month: October 2017

Programme and Abstracts for SOTFOM 4: Reverse Mathematics

SOTFOM 4: Reverse Mathematics is now just a few days away! Anyone wishing to attend should register by sending an e-mail with name and affiliation to sotfom@gmail.com.  There will be a conference dinner on Monday, October 9, 2017. When registering, please indicate if you plan to attend the dinner.

Below you can find a conference programme. There’s also the short abstracts to whet your appetite! We look forward to seeing you in Munich!

Programme:

Day 1 – Monday, October 9, 2017, LMU Main Building, room A 022

10:00-10:15 Welcome
10:15-11:45 Stephen G. Simpson `Foundations of mathematics: an optimistic message’
11:45-12:15 Coffee break
12:15-13:15 Sam Sanders `Two is enough for chaos in reverse mathematics’
13:15-15:00 Lunch break
15:00-16:00 Michał Tomasz Godziszewski `What do we need to prove that satisfaction is not absolute? Generalization of the Nonabsoluteness of Satisfaction Theorem’
16:00-16:30 Coffee break
16:30-18:00 Walter Dean `Basis theorems and mathematical knowledge de re and de dicto’
19:00 Conference dinner

Day 2 – Tuesday, October 10, 2017, Main Building, room E 006

10:15-11:45 Benedict Eastaugh `On the significance of reverse mathematics’
11:45-12:15 Coffee break
12:15-13:15 Marta Fiori Carones `Interval graphs and reverse mathematics’
13:15-15:00 Lunch break
15:00-16:00 Eric P. Astor `Divisions in the reverse math zoo, and the weakness of typicality’
16:00-16:30 Coffee break
16:30-18:00 Marianna Antonutti Marfori `De re and de dicto knowledge in mathematics: some case studies from reverse mathematics’

Day 3 – Wednesday, October 11, 2017, LMU Main Building, room A 022

10:15-11:45 Takako Nemoto `Finite sets and infinite sets in constructive reverse mathematics’
11:45-12:15 Coffee break
12:15-13:15 Vasco Brattka `Weihrauch complexity: Choice as a unifying principle’
13:15-15:00 Lunch break
15:00-16:00 Alberto Marcone `Around ATR_0 in the Weihrauch lattice’
16:00-16:30 Coffee break
16:30-18:00 Marcia Groszek `Reverse recursion theory’

Abstracts:

Stephen G. Simpson `Foundations of mathematics: an optimistic message’

Historically, mathematics has often been regarded as a role model
for all of science — a paragon of abstraction, logical precision,
and objectivity. The 19th and early 20th centuries saw tremendous
progress. The great mathematician David Hilbert proposed a sweeping
program whereby the entire panorama of higher mathematical
abstractions would be justified objectively and logically, in terms
of finite processes. But then in 1931 the great logician Kurt
Gödel published his famous incompleteness theorems, leading to an
era of confusion and skepticism. In this talk I show how modern
foundational research has opened a new path toward objectivity and
optimism in mathematics.

Sam Sanders `Two is enough for chaos in reverse mathematics’

Reverse Mathematics studies mathematics via countable approximations, also called codes. Indeed, subsystems of second-order arithmetic are used, although the original Hilbert-Bernays system H includes higher-order objects. It is then a natural question if anything is lost by the restriction to the countable imposed by second-order arithmetic. We show that this restriction fundamentally distorts mathematics. To this end, we exhibit ten theorems from ordinary mathematics which involve type two objects and cannot be proved in any (higher-type version) of Pi_k^1-comprehension, for any k. Said theorems are however provable in full (higher-order) second-order arithmetic and intuitionism, as well as often in (constructive) recursive mathematics.

Michał Tomasz Godziszewski `What do we need to prove that satisfaction is not absolute? Generalization of the Nonabsoluteness of Satisfaction Theorem’

We prove the following strengthening of the Hamkins-Yang theorem on the nonabsoluteness of satisfaction:

For any theory T  interpreting PA and defining the arithmetical truth and for any countable \omega-nonstandard model M \models T there is an isomorphic model M' such that \mathbb{N}^M = \mathbb{N}^{M'} (the natural numbers of the models agree), but Th(\mathbb{N})^M \neq Th(\mathbb{N})^{M'} i.e. the true arithemetics of the models are incompatible

We will provide a philosophical discussion of the theorem in the context of the debate on the so-called multiverse perspective in foundations of mathematics.

There is yet a question of reverse-mathematical strength of the presented results. If one assumes that \mathcal{N}^M, Tr(\mathcal{N})^{M} is recursively saturated, then even RCA_0 is enough. Without this assumption, however, we need to use the result saying that in the countable recursive saturation implies chronic resplendency, and the reverse-mathematical status of this implication is (according to our knowledge) an open question. Further, if we phrase the assumptions of the result in a way that instead of postulating recursive saturation we require that an arithmetical truth predicate in the model satisfies the theory CT^- axiomatizing the concept of full satisfaction class, then to get some of our corollaries we need to appeal to Lachlan’s theorem saying that admitting a satisfaction class implies recursive saturation. As above, the reverse-mathematical status of this implication is an open problem. We therefore leave some questions concerning strength not only of the theory T from above, but reverse-mathematical status of the results on the nonabsoluteness of satisfaction themselves.

Walter Dean `Basis theorems and mathematical knowledge de re and de dicto’

TBA

Marta Fiori Carones `Interval graphs and reverse mathematics’

This paper deals with the characterization of interval graphs from the point of view of reverse mathematics, in particular we try to understand which axioms are needed in the context of subsystems of second order arithmetic to prove various characterizations of these graphs. Furthermore, we attempt to analyze the interplay between interval orders and interval graphs. Alberto Marcone (2007) already settled the former question for interval orders and this paper follows his path. An interval graph is a graph (V,E) whose vertices can be mapped in intervals of a linear order L such that if two vertices are related, then the intervals associated to them overlap. Different notions of intervals give raise to different notions of interval graphs (and orders), which collapse to one in WKL0. On this respect, interval graphs show the same behavior of interval orders. On the other hand, interval graphs and interval orders have different strength with respect to their characterizations in terms of structural properties. While RCA0 suffices to prove the combinatorial characterization of interval orders, WKL0 is required for interval graph s. Moreover, given an interval graph it is possible to define an associated interval order and vice versa. Even in this respect, the different definitions of interval graphs and orders mentioned before play a role in analysing the strength of this theorems.

Eric P. Astor `Divisions in the reverse math zoo, and the weakness of typicality’

In modern reverse math, we have begun to discover some exceptional subsystems that do not fall into the linearly-ordered Big Five, particularly concentrated between ACA0 and RCA0. These exceptional systems form a structure that is sometimes called the reverse-mathematics Zoo. Between ACA0 and RCA0, the Zoo can be seen to divide into three branches: roughly, combinatorics, randomness, and genericity. (Prominent examples on each branch include RT22, WWKL, and Pi^0_1G respectively.) We raise questions about the significance of this division in the Zoo, and obtain the first theorem describing this large-scale structurer. Noting that both randomness and genericity are notions of typicality, we find a strict limitation on the strength of principles stating that sufficiently typical sets exist; using this, for nearly all known principles P in the Zoo, we determine whether P follows from any randomness- or genericity-existence principle.

Marianna Antonutti Marfori `De re and de dicto knowledge in mathematics: some case studies from reverse mathematics’

TBA

Takako Nemoto `Finite sets and infinite sets in constructive reverse mathematics’

We consider, for a set A of natural numbers, the following notions of finiteness

FIN1: There are k and m_0,,,,m_{k-1} such that A={m_0,…,m_{k-1}};
FIN2: There is an upper bound for A;
FIN3: There is m such that for all B\subseteq A(|B|<m);
FIN4: It is not the case that, for all x, there is y such that y\in A;
FIN5: It is not the case that, forall m, there is B\subseteq A such
that |B|=m,

and infiniteness

INF1: There are no k and m_0,…,m_{k-1} such that A={m_0,…,m_{k-1}};
INF2: There is no upper bound for A;
INF3: There is no m such that for all B\subseteq A(|B|<m);
INF4: For all y, there is x>y such that x\in A;
INF5: Forall m, there is B\subseteq A such that (|B|=m).

We systematically compare them in the method of constructive reverse mathematics.
We show that the equivalence among them can be characterized by various combinations of induction axioms and non-constructive principles, including the axiom called bounded comprehension.
Vasco Brattka `Weihrauch complexity: Choice as a unifying principle’

TBA

Alberto Marcone `Around ATR_0 in the Weihrauch lattice’

The classification of mathematical problems in the Weihrauch lattice is a line of research that blossomed in the last few years. So far this approach has mainly dealt with statements which are provable in ACA0 and below. On the other hand the study of multi-valued functions arising from statements laying at higher levels (such as ATR0) of the reverse mathematics spectrum is still in its infancy. We pursue this study by looking at multi-valued functions arising from statements such as the perfect tree theorem, comparability of well-orders, \Delta^0_1 and \Sigma^0_1-determinacy, \Sigma^1_1-separation, weak \Sigma^1_1-comprehension, \Delta^1_1 and \Sigma^1_1-comprehension. As usual, choice functions provide significant milestones to locate these multi-valued functions in the Weihrauch lattice.

Marcia Groszek `Reverse recursion theory’

TBA

 

 

Advertisements