# Lew Gordeew, WSI f. Informatik, Tuebingen University

## Talk on Wednesday (10/01/2007)

This is a joint paper with A. Weiermann.

**Title**: Strong WQO phase transitions.**Local**: 511 (RDC)**Time**: 14 horas**Slides**: LabNestedPres.pdf

**Abstract**:

We investigate phase transitions for well-quasi-ordering (wqo) results with respect to nested finite sequences and nested finite trees under the homeomorphic embedding with symmetrical gap condition. With every wqo W in question we correlate a natural "strong" PA-extension T that proves the corresponding 2-order sentence WQO(W) stating that W is a wqo. Furthermore, we consider a parametrized 1-order "slow" wqo sentence SWQO(W,...,x) with x ranging over computable reals, and actually compute a real number r such that the following hold:

If x < r, then SWQO(W,...,x) is provable in PA.

If x > r, then SWQO(W,...,x) is not provable in T.

Such (uniquely determined) real r is called phase transition for T and SWQO(W,...,x). These results strengthen Kruskal-Friedman-Gordeew-Kriz wqo theorems and Weiermann's phase transitions concerning Kruskal-Friedman-Schuette-Simpson cases.

## Talk on Thursday (11/01/2007)

**Title**: A note on Da Costa - Doria result.**Local**: 511 (RDC)**Time**: 14 horas**Slides:**Costa-Doria.pdf

**Abstract**:

We present a simple, purely logical interpretation of "Computing the future" by N.C.A da Costa and F.A, Doria concerning (un)provability of P vs. NP.