| Logic Seminar
Faculty
Students
Former Students
|
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 to the left to visit individual faculty and the logic seminar web site.
Algorithmic RandomnessThe 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 Computable algebra and model theoryThis 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 analysisThe 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, including Combinatorial set theoryAs 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 theoryDescriptive 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 setsEffectively 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 idealsShelah’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. Inner model theoryInner models, large cardinals, the constructible universe, notions of forcing, descriptive set theory. Logic ProgrammingLogic 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. |