North Texas Logic Conference

October 8^th - 10^th 2004

Schedule

All talks will be held in GAB 105.

The official program can be found here

Abstracts

Abstract: This talk is a contribution to the descriptive set theory of Polish group actions. Like much of the recent research in this field, it is concerned with a known theorem about locally compact groups and with the question of whether -- or to what extent -- the result generalizes to arbitrary Polish groups. The theorem in question is Mackey's Cocycle Theorem: Every almost cocycle is equivalent to a strict cocycle. This question is relevant to the foundations of quantum mechanics.

Abstract: Choiceless polynomial time is a complexity class of decision problems whose instances are finite structures. The polynomial-time computations here are not permitted to use an ordering of the input structure (or, what amounts to the same thing, arbitrary choices), but parallelism and rich data structures are allowed. The underlying computational framework is given by Gurevich's abstract state machines, to which I'll provide a brief introduction. Then I'll discuss what can (and what cannot) be computed in choiceless polynomial time, particularly when it is augmented by an oracle for cardinality. My work in this area is joint with Yuri Gurevich and Saharon Shelah.

Abstract: Jackson proved that under large cardinal hypotheses and assuming the nonstationary ideal on ω₁ is ω₂-saturated that there is a regular cardinal in L(R) that is not a cardinal in V. I will report on recent progress toward extending this result.

Abstract: A number of years ago, Cholak, Downey, and Harrington showed that the Slaman-Woodin conjecture is true. That is, they showed the set of ordered pairs < i, j > such that there is an automorphism of the computably enumerable sets Φ with Φ(W_i)=W_j (in this case we say W_i ~ W_j) is Σ₁¹-complete. Recently, Cholak and Harrington improved this to prove that there is A such that { \hat{A} : A ~ \hat{A} } is Σ₁¹-complete. In this talk we will discuss the proof of this result and several of the corollaries which result from the proof.

Abstract: I will discuss ways of generating the equivalence relation E₀. First, I will give an example of a homeomorphism of Cantor space which generates E₀. I will then consider various nice properties we might desire of such a homeomorphism, and show that some of them are not possible.

Abstract: Some results on forcing and subcompact cardinals, motivated by questions about L[E]-models and square sequences.

Abstract: There are two natural ways to define `Fubini property' for a sigma-ideal of Borel subsets of [0,1]. The only two ideals that satisfy the stronger form of the Fubini property are meager and null. This is a joint work with Jindra Zapletal.

Abstract: A set is K-trivial if it has the lowest possible initial-segment prefix-free Kolmogorov complexity (up to an additive constant). A number of recent results have shown that the K-trivial sets are a natural class of "far from random" sets. I will discuss a recent characterization of the K-trivial sets obtained in joint work with Andre Nies: Say that B is a basis for 1-randomness if B is computable in a set that is 1-random relative to B. We have shown that A is a basis for 1-randomness iff A is K-trivial. Sacks showed that if A is not computable then the collection of all sets that compute A has measure zero. Our new characterization of K-triviality shows that A is not K-trivial iff the collection of all sets that compute A is contained in an A-effective set of measure zero, in the sense of Martin-Löf. This result can be thought of as saying that the K-trivial sets are exactly those relative to which Sacks's Theorem cannot be effectivized.

Abstract: I will survey what is known about the position of isomorphism of rank two torsion free abelian groups in the partial order of Borel equivalence relations considered up to Borel reducibility. In particular some new information is given by a recent joint result with Simon Thomas.

Abstract: n 1997, Slaman and Woodin [Arch. Math. Logic, 1997] proved the undecidability of the first-order theory of the enumeration degrees of the Σ⁰₂-sets. A closer analysis of their proof shows that they actually established the undecidability of the Π₅-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 Π₄-theory of the Σ⁰₂ enumeration degrees by extending a result of Ahmad and Lachlan [Math. Log. Q. 1998].

Abstract: The Scott Isomorphism Theorem says that for any countable structure A (for a countable language L), there is an L_ω1,ω sentence whose countable models are just the copies of A. In the proof, Scott assigned countable ordinals to tuples in A, and to the structure itself. This ordinal, the Scott rank, is a measure of model theoretic complexity. For a computable structure A, the Scott rank is at most ω₁^CK+1. There are familiar examples of computable structures of various computable ordinal ranks. Harrison showed that there is a computable ordering of type ω₁^CK(1+η). The Harrison ordering has rank ω₁^CK+1. Makkai gave an example of an arithmetical structure of rank ω₁^CK. Jessica Young and I showed that this example can be made computable. The original examples were quite complicated ``group trees''. Recently, Wesley Calvert, Young, and I found a much simpler example, which is just a tree. Moreover, the example can be shown to share with the Harrison ordering a strong approximation property.

Abstract: P. Erdos conjectured that if f:ω→ω is a function converging to infinity, then there is an uncountably chromatic graph G such that every subgraph of G on n vertices has chromatic number at most f(n). Shelah proved the consistency of this. From this we deduce the consistency of the negation of Taylor's conjecture: it is consistent that there is a graph X with size and chromatic number ℵ₁ such that if Y is a graph with the same finite subgraphs then the chromatic number of Y is at most ℵ₂.

Abstract: Woodin's forcing Pmax produces a a model of ZFC which has many of the same consequences as forcing axioms such as Martin's Maximum for statements about the first uncountable cardinal. We investigate several questions about the nonstationary ideal on the first uncountable cardinal which have not been resolved by forcing axioms, and show that they can be resolved in the Pmax extension. One still open project is to characterize the Boolean algebra induced by this ideal, or to show that such a characterization is in some sense impossible.

Abstract: Working at the interface of computability theory and model theory, we classify the computability-theoretic complexity of two index sets of classes of first-order theories: We show that the property of being an ℵ₀-categorical theory is Π⁰₃-complete, whereas the property of being an Ehrenfeucht theory Π¹₁-complete. We also show that the property of having continuum many models is Σ¹₁-hard.

The proof for the latter two results is ased on previous work by Millar and Reed on Ehrenfeucht theories, and by Sacks on bounding the Scott rank.

Abstract: There are two types of partition cardinals, those violating the Axiom of Choice (e.g., strong partition cardinals) and those consistent with the Axiom of Choice (e.g., Jonsson cardinals). The theory of infinitary combinatorics under the Axiom of Determinacy has results for both types -- existence theorems for strong partition cardinals due to Martin, Jackson and others, and existence theorems for other combinatorial large cardinals due to Kleinberg. The proofs for strong partition cardinals use a structural analysis that is connected to Kleinberg's analysis of the aleph_n, and the measure theoretic representations of cardinals under AD gave rise to more partition proofs. In this talk, we shall give a survey of techniques and results and present a general approach that should lead to a complete analysis of all cardinals below the supremum of the projective ordinals in terms of iterated ultrapowers. This is work in progress and joint with S. Bold and S. Jackson.

Abstract: We discuss the existence of Borel sets in the plane such that each section is countable and each countable set occurs as a section exactly once. We also discuss the existence of Borel sets of a particular Borel class which uniquely represent other families of sets, e.g. the σ-compact sets.

Abstract: I'll define rank games, use them to unravel Π¹₁ sets (in the presence of appropriate large cardinals), and comment on another use, in a determinacy proofs for games ending at the first admissible relative to the play.

Abstract: I will present some recent results in relative randomness as captured by rK-reducibility, a refinement of Turing reducibility.

Abstract:I will present a theorem on the existence of local continuous homomorphic inverses of surjective Borel homomorphisms with countable kernels from Borel groups onto Polish groups. I will show how to associate in a canonical way subgroups of $\mathbb R$ with certain analytic P-ideals of subsets of $\mathbb N$. These groups, with appropriate topologies, provide examples of Polish, non-locally compact, totally disconnected groups for which global continuous homomorphic inverses exist in the situation described above. The method of producing these groups generalizes constructions of Stevens and Hjorth and, just as those constructions, yields examples of Polish groups which are totally disconnected and yet are generated by each neighborhood of the identity.

Abstract: I will study several ways of obtaining capacities on the cantor space such that the poset of positive Borel sets ordered by inclusion is proper in the forcing sense.

Future Directions

Funding Opportunities

Limited funding is available to participants and graduate students. To request funding please send an email to logic@unt.edu.

Travel receipts are necessary to receive funding so if you use electronic ticketing, please make sure to request a receipt when you get your boarding pass.

Accomodations

Denton has a few hotels that are less a mile and a half from the campus: The Radisson Hotel, Comfort Suites, and the Royal Inn (phone 940.383.2007). A walk to campus from these hotels is about 10-20 minutes. Local weather conditions can be found here.

Hotels that are a short drive from the campus include: La Quinta, Days Inn, Best Western Inn, and Hampton Inn and Suites. A more complete list of accomodations can be found at Discover Denton.

Dining

There will be a special event dinner Saturday night. Dress is casual.

Airports

Denton has two choices for airport: Dallas/Fort Worth (DFW) and Dallas Love Field (DAL). DFW is preferred and it is strongly recommended that you rent a car.

DFW is an American Airlines hub with flights from there to practically everywhere. Every other major airline has flights to DFW from their hub. DFW is approximately 35 minutes from Denton. Southwest Airlines does not operate out of DFW. Driving directions from DFW to UNT can be found here.

DAL is 45 minutes to over an hour from Denton, depending on traffic. Southwest Airlines operates out of DAL. Driving directions from DAL to UNT can be found here.

Transportation

We strongly recommend renting a car from the airport. Taxis and shuttles from the airport to Denton are expensive, in excess of $50 one way. Parking on campus will be free on Saturday and Sunday with no pass required. For Friday, a pass will be required. The conference will prepay for these. You may pick up the visitor pass anytime on Friday at the visitor parking information booth off of avenue C (which is very close to the GAB where the conference is being held).