Dmytro Taranovsky
(draft)
My mathematical research spans diverse areas, but most important are my contributions to our understanding of infinity.
1. Extending the Language of Set Theory and Reflective Cardinals. The language of set theory is the de facto formal language of mathematics, but it has a key limitation: While a set is an arbitrary collection of objects, there is no such thing as the set of all sets (as informally, it would be bigger than itself), and one cannot quantify over properties for which there is no set of all objects satisfying the property. My research addresses this issue by introducing reflective cardinals, which are sets that in a certain sense approximate the set theoretical universe V. I give an intuitive definition, interpretation of higher order set theory, and formal axiomatizations. I explore the relations between different axioms and extend the notion to even higher levels of expressiveness.
2. Ordinal Notation. Key to infinitary set theory is the notion of ordinals. Ordinals include natural numbers, and also intuitively numbers you get when you keep counting past infinity (denoted ω): 0,1,2,3,...,ω,ω+1,ω+2,...,ω2,ω2+1, ω2+2,...,ω3,...,ω2,...,ω3,...,ωω,... . Stronger theories generally prove existence of more ordinals. Having a reasonable description of the canonical ordinals in a theory qualitatively enhances our understanding of the theory; it is like having a precise map instead of just partial descriptions. The obstacle is that as the strength increases, the complexity can quickly become intractable, and to a large extent, progress in ordinal analysis is about managing complexity and makes things simpler. My contribution is to create a framework that reduces complexity for ordinal representations and to create ordinal notation/representation systems that are conjectured to reach much stronger theories, including plausibly ZFC (the standard axioms for set theory) and beyond. I also give detailed a analysis of the representation systems, though key parts remain conjectural.
I also created OrdinalArithmetic.py implementing arithmetic and other operations for the main ordinal notation system. Besides its functional value, the module is written with high quality concise code. A competitor using a much weaker ordinal notation system and otherwise comparable functionality used over 10 times as many lines of code.
3. Finitistic Properties of High Complexity. In this paper, I prove connections between infinite and finite but sufficientlty large. I formalize and answer which undecidable problems we can we (in unlimited time) if we have access to a sufficiently fast-growing sequence, or to multiple sequences each sufficiently fast-growing relative to the previous ones. Perhaps most strikingly, I give an interpretation of second order arithmetic that arguably uses only finite numbers, though the intricate use of largeness can be arguably be regarded as infinity in disguise.
4. Constructive Mathematical Truth. As a believer in objective mathematical truth, I reject the intuitionistic philosophy, but that has not stopped me from appropriating intuitionistic logic to define and explore constructive truth in arithmetic and intuitionistic analysis — in an intertwining of classical and constructive mathematics. A key interesting result (among others) is that constructive arithmetical truth is highly nonarithmetical, and I conjecture has the same complexity as second order arithmetic. The complexity stems from requiring constructively true arithmetical statements to be classically true and from the handling of constructive implication.
5. Arithmetic with Limited Exponentiation. Weak mathematical theories can be surprisingly powerful, and my paper explores just how much can be done in theories so weak that they are interpretable in Robinson arithmetic Q and thus fail to prove that exponentiation is total. I successfully capture a number of principles about integers, real numbers (including nonrecursive real numbers), and functions of any finite number of higher types.
6. Incompleteness in set theory. Many basic questions (such as the Continuum Hypothesis) are undecidable in the standard axiomation of set theory (ZFC). In a number of FOM (Foundations of Mathematics mailing list) postings, I explore these issues and give a vision for addressing the incompleteness. Here are some (excluding those that discuss the above papers or are more about philosophy of mathematics):
"On the Continuum Hypothesis" (part 1 and part 2; gives a strong argument that GCH is true), Strength of Logical Principles, Definability and Natural Sets of Real Numbers, On the Nature of Reals, Re: the notion of "effectively complete".
7. Miscellaneous contributions (excluding philosophy of mathematics):
• Determinacy Maximum — introduces, analyzes, and defends a strong determinacy hypothesis for infinite games.
• Determinacy and Fast-growing Sequences of Turing Degrees — shows that under appropriate assumptions, all sufficiently fast-growing sequences of Turing degrees (even sequences of length ω1) are indistinguishable, and explores related results.
• Defined a finite analogue of infinite models (link).
• Coins and Infinite Ordinals gives a formally valid intuitive visualization for some ordinal notation systems.
• Used probability to make conjectures in number theory about representability of numbers as sums of powers and primes (link). Among other things, I conjecture that every sufficiently large odd natural number is representable as p2+q3+r5 for prime p,q,r.
• Proved an equivalence between WKL0 and a determinacy hypothesis (link).
1. "Space-Efficient Circuit Evaluation" (link) proves that uniform circuits of size n can be evaluated in space O(n / log n), and showed that for a large class of computational models, Time(O(n)) is in Space(O(n log log n / log n)). However, the reductions are not practical as they use exponential time.
2. Proved that comparison-based sorting is possible with lg(n!) + o(n) comparisons (link). Relative to the lower bound, this wastes an average of o(1) comparisons per element.
3. A number of smaller (in length) contributions are on the Theoretical Computer Science Stack Exchange; my user page is here.