Fri Nov 18, 2011
60 Evans Hall, 4:10–6 PM
Theodore A. Slaman (University of California, Berkeley)
The First-Order Consequences of the Existence of an Infinite Random Sequence
We will discuss the question, “What first-order statements follow from the existence of an infinite random sequence by effective means?” The answer depends on the degree of randomness in the infinite source. In one case, it isolates a mysterious subtheory of arithmetic strictly between ∑1-Induction and ∑2-Bounding.
The biweekly LOGIC TEA will be held in the Alfred Tarski Room (727 Evans Hall) immediately following the Colloquium (with support from the Graduate Assembly).