UF Logic and Set Theory

group
Logic Group with Speaker Natasha Dobrinen

Logic Seminar

FACULTY

Dana Bartosova
Douglas Cenzer
Jean Larson (Emeritus)
Robin Tucker-Drob (Associate Professor)
William Mitchell (Emeritus)
Jindrich Zapletal

STUDENTS

Caleb Davis
Cameron Fraize 
Shravan Sadashiva
Richard Krogman
Lauren Wickman
Yuxin Zhou

FORMER STUDENTS

Francis Adams
Hector Andrade
Katie Brodhead
Omar De la Cruz Cabrera
Ali Dashti
Michal Douche
John Hester
Mike Jamieson
Jeffrey Leaning
Bill Moser
John People
Diego Rojas Rebolledo
Farzan Riazati
Yuan-Chuan Sheu
Ferit Toska
Zia Uddin
Amy Vanderbilt
Thomas Winckler
Sebastian Wyman

RESEARCH

The logic and set theory group at UF focuses on contemporary research in a broad range of mathematics with important inter and intra-discipline connections. Below is a brief synopsis of the activities. For more information, follow the links above to visit individual faculty and the logic seminar web site.

Algorithmic Randomness

The basic problem of algorithmic randomness has been to quantify the randomness of a single real number. The notion of randomness was defined by Kolmogorov in terms of information content and by Martin-Lof in terms of probability. Cenzer and his collaborators have developed notions of Algorithmic Randomness of Closed Sets and of continuous functions. Every random closed set is perfect, has measure zero and has Hausdorff dimension log (4/3). Random continuous functions map computable reals to random reals and the set of zeroes of a random function is a random closed set. We are currently working on complexity versions of randomness and applications to analysis. McCarthy has studied alternative notions of randomness and connections between them, as well as to what extent randomness assumptions can be replaced by genericity or combinatorial assumptions.

Computable algebra and model theory

This area examines the effective content of results from algebra and model theory. One new result is a complexity-theoretic version of the classic result that every decidable theory has a computable model. A model A is computably categorical if any other model isomorphic to A is in fact computably isomorphic to A. Recent work extends this notion to arithmetically definable models and isomorphism and in particular to definability in the difference hierarchy over the computably enumerable sets. Structures studied include equivalence relations and Abelian groups. Complexity Theoretic Model Theory and Algebra examines structures with functions and relations computable in, say, polynomial time. Current work examines so-called automatic structures, where the relations are recognizable by finite automata and the functions are computable by finite transducers.

Computable analysis

The main theme of computable analysis is the study of effective aspects of real and complex numbers and functions. Index sets for effectively closed sets of reals and for computable real functions are developed and used to analyze the computability of cardinality and measure and also the complexity of certain differential equations in Index Sets for Computable Differential Equations . Complexity theory for analysis leads to the result that the famous P=NP problem is equivalent to whether every NP closed set of reals is also polynomial time closed. Recent papers have investigated computable subshifts and the connection with effective symbolic dynamics.

Choiceless set theory

Choiceless set theory studies various consequences of the axiom of choice in the areas of analysis, algebra etc. and asks whether they imply one another on the basis of ZF set theory without the axiom of choice. The result is a deep stratification of the areas concerned. We discovered a new and productive methodology for obtaining independence results in ZF set theory parallel to the amalgamation techniques in model theory and combinatorics. The forthcoming book “Geometric set theory” exploits the methodology in depth.

Combinatorial set theory

As Walter Deuber said, “complete disorder is impossible”. Combinatorial set theory searches out swaths of uniform behavior, especially in various types of partition relations, of the cardinals, ordinals, linear orders, and partial orders that underpin many transfinite arguments.

Descriptive set theory

Descriptive set theory is the study of definability of various sets of real numbers. It turns out that we can infer many properties of such a set just from the syntax of its definition. One famous tool of this theory is the determinacy of infinite games, stating that one player must necessarily have a winning strategy in a certain type of two-player game of infinite duration. One popular application of this theory is the rating of many key problems in pure mathematics according to their complexity.

Effectively closed sets

Effectively closed sets, or Pi-0-1 classes, are a unifying theme in the study of computability and its applications and are also central to the study of algorithmic randomness. The basic idea here is to view the solution of a problem, such as coloring a graph, as a sequence of choices, or branches, so that the solution set corresponds to a tree. We are interested in how to represent mathematical problems in terms of these trees and in how the complexity of the tree relates to the complexity of the problem. The set of paths through a computable tree is an effectively closed set. Other examples include the set of fixed points of a computable real function and the set of stable models of a logic program. This enables one to construct, for example, a computable graph which has a 3-coloring but has no computable 3-coloring. The complexity of solving a problem may be specified by means of index sets. For example, the problem of determining whether a computable tree has a computable path is Sigma_3 complete, that is, it requires three quantifiers to define.

Forcing with ideals

Shelah’s powerful method of proper forcing, used for decades for independence results regarding the structure of the real line can be sharpened quite a bit under the assumption that the forcing is in a certain sense definable. This leads to the study of various σ-ideals on Polish spaces and the quotient algebras of Borel sets modulo the ideal. The forcing properties of the quotient are closely connected with the analytic and descriptive properties of the ideal, providing a strong link between proper forcing and such fields as descriptive set theory, measure theory, dynamical systems and Ramsey theory.

Logic Programmng

Logic programming is a paradigm for automated deduction. It is part of artificial intelligence since it provides a tool for machine learning and reasoning. Logic programming is applied to databases in medical diagnosis, air traffic analysis and other areas. Cenzer is working on complexity of models for logic programs.