Fall2004 GPSLogic Schedule

Fall 2004 Schedule
Slides, if available, can be accessed by clicking on the talk title.

16 September 2004: Asher Kach on " Finitary Boolean Algebras "
23 September 2004: Chris Alfeld on " The Forest and the Trees "
30 September 2004: David Milovich on "Model Theory for Reduced Products"
7 October 2004: Trevor Irwin on "Borel Equivalence Relations and Classification Problems"
14 October 2004: Rob Owen on "Outer Model Theory"
21 October 2004: Erik Andrejko on "The Relative Consistency of NOT AC"
28 October 2004: Alex Raichev on "An Introduction to Randomness" at 4:30PM
4 November 2004: Asher Kach on "Voting Systems and Arrow's Impossibility Theorem"
11 November 2004: Tom Kent on "Undecidability in Computable Structures: the Good, the Bad, and the Undecidable"
18 November 2004: Ramiro de la Vega on "Is 210 Enough for 5?"
25 November 2004: Thanksgiving - Will not meet.
2 December 2004: Elisa Vasquez on "Criteria for the Existence of Bi-Invariant Top Forms on a Lie Group"
9 December 2004: Dilip Raghavan on "The GCH at Measurable Cardinals"

Fall 2004 Abstracts (In presentation order)
Slides, if available, can be accessed by clicking on the talk title.

Finitary Boolean Algebras (Asher Kach): Finitary Boolean algebras are the class of countable Boolean algebras that are primitive and have finite diagrams. These various concepts will be explained from the ground up with copious examples. As time permits, the relationship between the finitary Boolean algebras and their Ketonen Invariants (results of Heindorff) will be stated and explained.
The Forest and the Trees - An Introduction to $\Pi^0_1$ Classes (Chris Alfeld): A $\Pi^0_1$ class is the set of infinite paths through a computable tree. I will present basic definitions, concepts, and results about both the classes themselves (the Trees) and various ways they relate to each other (the Forest). A basic understanding of computable and computably enumerable sets will be very helpful but is not a requirement.
Model Theory for Reduced Products (David Milovich): In model theory, the ultraproduct is by far the most commonly studied type of reduced product. However, many times in mathematics one is interested in direct products or products reduced by filters that are not ultrafilters. After the prerequisite definitions are explained and some motivating examples given, the main model-theoretic result on general reduced products will be presented. Time permitting, a few other results will be included.
Borel Equivalence Relations and Classification Problems (Trevor Irwin): We will introduce the theory of Borel equivalence relations and see how this theory can be used to tell us something about the difficulty of some kinds of classification problems.
Outer Model Theory (Rob Owen): Inner model theory, the study of models one can construct inside a given universe of ZFC, is a rich and well-understood branch of set theory. Outer model theory is not; in fact, it barely even exists as a concept. In this talk we explore what (little) is known about outer model theory, namely a theorem of MC Stanley, interpreted in the paradigm of "oracle forcing". Along the way, I hope to introduce various nooks and crannies of both set theory and model theory that aren't usually covered here at UW-Madison, like class forcing, 0^#, admissible set theory and the logic L_{\infty \omega}.
The Relative Consistency of NOT AC (Erik Andrejko): There are some compelling reasons to deny the Axiom of Choice in favor of several strictly weaker versions. These weaker forms are presented along with the construction of classes showing the consistency of ZFA + NOT AC and ZF- + NOT AC. Finally, time permitting, some pathologies are shown to be consistent with NOT AC.
An Introduction to Randomness (Alex Raichev): What does it mean from an infinite sequence of zeros and ones to be random? Intuitively, the sequence should be unpredictable, typical, incompressible. With the help of computability theory, I will present one way of making mathematically rigorous and robust these intuitions and, in doing so, provide an introduction to the fairly new (mid 1960s) and vibrant field of randomness.
Voting Systems and Arrow's Impossibility Theorem (Asher Kach): As a consequence of the ongoing Presidential election, there has been renewed publicity about the failures of the American voting system. Unfortunately the American voting system, and more generally any voting system, cannot be "fair" as a consequence of Arrow's Impossibility Theorem. In this talk the necessary background to understand the statement of Arrow's Theorem and one of its many proofs will be given. Before doing so, a survey of voting over the centuries and across the world will be discussed, highlighting some of the many voting systems used in sports, politics, and business. As time permits, recent research and other results in voting theory will be explored.
Undecidability in Computable Structures: the Good, the Bad, and the Undecidable (Tom Kent): In 1997, Slaman and Woodin [Arch. Math. Logic, 1997] proved the undecidability of the first-order theory of the enumeration degrees of the $\Sigma^0_2$-sets. A closer analysis of their proof shows that they actually established the undecidability of the $\Pi_5$ theory.
We introduce enumeration reducibility and demonstrate how to use the Nies transfer Lemma [Alg. Universalis, 1996] to show that the first order theory of a given structure is undecidable. We then establish the undecidability of the $\Pi_3$ theory of the $\Sigma^0_2$ enumeration degrees by extending a result of Ahmad and Lachlan [Math. Log. Q. 1998].
Is 210 Enough for 5? (Ramiro de la Vega): We consider two weakenings of the axiom of choice for collections of finite sets. The first $C^\diamondsuit_n$ states that every infinite set X has an infinite subset Y such that the collection of n-subsets (subsets of size n) of Y has a choice function. The second $C^{-}_n$ states that every infinite collection P of n-sets has an infinite subcollection Q with a choice function. It is easy to see (and we will) that $C^\diamondsuit_n$ implies $C^{-}_n$ for n=2,3. We will also prove Montenegro's result that the implication holds for n=4. Finally I will give some hints to decide the implication for n=5 (which as far as I know is still an open problem).
Criteria for the Existence of Bi-Invariant Top Forms on a Lie Group (Elisa Vasquez): A criteria for the existence of such forms, in terms of the adjoint representation, will be presented.
The GCH at Measurable Cardinals (Dilip Raghavan): My aim will be to introduce the technique of taking ultrapowers of the universe to prove theorems about Measurable Cardinals. As an illustration of the technique I will prove the following result of Scott: "If GCH holds below a Measurable, then it holds at that Measurable". The talk is meant to be accessible to all, so I will try to give as many details as possible. Also, if there is time at the end I will survey some other results regarding the GCH at Measurable Cardinals.

Links