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 uses well-written concise code. (A competitor (its code remains available on the Internet Archive) 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 solve (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. The definition used is the most natural one if we want only classically true arithmetical statements to be constructively true, and use continuity for second order quantifiers. 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, and MathOverflow contributions):
• 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.
• Elementarily self-embeddable models of ZFC — gives striking conservation results where adding a nontrivial elementary self-embedding j of the universe (avoiding Kunen inconsistency by using only some of the ZFC axioms for j-formulas) corresponds to various traditional large cardinal axioms.
• Asymptotic optimal sphericity — asymptotic behavior of polyhedra that have maximum sphericity for their number of faces, and related problems, plus a series of conjectures on the hypothetical fractal that is the limit of (the distribution of nonhexagonal faces in) highest sphericity polyhedra as the number of faces approaches infinity.
• 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).
8. A selection of contributions published on MathOverflow (for more, see my user page):
Logic and related fields:
Addressing the incompleteness in set theory:
• Periodicity in the cumulative hierarchy suggests how higher types should behave in the universe of hereditarily natural sets. For the usual universe satisfying the axiom of choice, see Independence through forcing vs generic collapses.
• Determinacy of symmetric games presents and explores a conjecture for determinacy of a large class of games involving the uncountable.
Inner models and large cardinals:
• Suggested an alternative development of fine-structural inner models (in set theory) that uses indiscernibles rather than ultrafilters (link).
• Inner models with all sets generic (explored natural inner models over which every is set is generic).
• 0# in weak theories vs large cardinals in L connects some of the strongest natural axioms for the constructible universe L with the weakest theories transcending L.
• Complexity of L[cf] — analyzed expressibility of the contructible universe L augmented with the cofinality quantifier.
Infinite computation:
• ITTMs with higher types extends infinite time Turing machines to tapes of higher types, and analyzed their expressiveness.
• Cardinal register machines gives a simple-looking extension of register machines to infinite cardinalities and analyzes its surprising power.
Axiomatization of decidable theories:
• Proved that the axiomatization of the real numbers (real closed field) cannot be weakened to that of an ordered field with least upper bounds for parameter-free definable bounded sets (link).
• Axiomatization of S2S gives a reasonable axiomatization of S2S, and its general extension to MSO theories of trees. S2S is the MSO (monadic second-order) theory of the infinite binary tree, and is one of the most expressive decidable theories known, with many other theories interpretable in S2S, but a reasonable axiomatization has been lacking. I also wrote the S2S wikipedia article.
Proof theory (other):
• Π01 Proof Ordinals connects the hierarchy of natural Π01 statements to existence of lage numbers.
• Gave additional examples of infinite descending consistency chains (link).
Other (logic):
• Complexity of transfinite 5-in-a-row and other games analyzes complexity of various transfinite board games.
• Came up with the theories extending ZFC\P + V≠L that have arbitrarily large transitive models, but at most one model of each ordinal height (link, extending this).
• Determinacy and polynomial time degrees — showed that all sufficiently closed computational complexity classes (including EA and EB for arbitrary sufficiently powerful oracles A and B) are in a sense indistinguishable.
Other:
• Conjectures on optimal asymptotic solution lengths in various permutation puzzles (here and here).
• Conjectures on existence of Hamilton cycles in random graphs without local obstructions (link) and finding such cycles in linear
time (link).
• Pursuit evasion: Conditions for successfully escaping from infinitely many dumb slow pursuers (link). See also my article Pursuit-evasion with many slow pursuers and here.
• Attemps at defining natural fractional exponential growth rates (Analytic Tetration and Natural Rates of Growth and Fractional exponentiation with different bases).
• Computed asymptotic probability that two random maps commute (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), even in the worst case. Relative to the lower bound, this wastes an average of o(1) comparisons per element. For the average case, I proved lg(n!) + O(n1-ε) comparisons and gave a potential construction for lg(n!) + O(log n) comparisons.
3. A number of smaller (in length) contributions are on the Theoretical Computer Science Stack Exchange (my user page is here):
• Showed undecidability of single-player games with randomness and 3 bits of hidden state (link).
• Explored complexity of reachability in fractal mazes (link), with various modications leading to a variety of complexity classes.
• Showed that linear time in-place stable sort is possible when the keys are O(log n) bit size integers (link). A previous paper almost showed this, but explicitly left out the hardest case.
• Proposed an algrebra with various operations on complexity classes (link).
• Came up with a computational model, resembling Turing machines, with a very tight time hierarchy theorem (link), essentially with only an additive logarithmic overhead.
• Made conjectures on fine-grained speed-ups from using randomness (Fine-grained complexity of BPP).
• Combining previous results, showed that a sliding blocks puzzle is complete for linear space (link).
• Collected some open problems where a seemingly much larger complexity class has not been proved to exceed the smaller class (link).