2 citations · 4 across the 10 of their papers we have counts for
10 papers
Numerical choice, Riemann integration, and Reverse Mathematics
Sam Sanders, Dmytro Taranovsky
Riemann integration remains a well-known part of mathematics for both historical and conceptual reasons. We study basic properties like boundedness of Riemann integrable functions…
Finitistic Properties of High Complexity
Dmytro Taranovsky
We use fast-growing finite and infinite sequences of natural numbers and more complicated constructs to define models of hypercomputation and interpret non-arithmetic predicates, w…
Arithmetic with Limited Exponentiation
Dmytro Taranovsky
We present and analyze a natural hierarchy of weak theories, develop analysis in them, and show that they are interpretable in bounded quantifier arithmetic (and henc…
Determinacy and Fast-growing Sequences of Turing Degrees
Dmytro Taranovsky
We discuss sufficiently fast-growing sequences of Turing degrees. The key result is that, assuming sufficient determinacy, if is a formula with one free variable, and S and T a…
Ordinal Notation
Dmytro Taranovsky
We introduce a framework for ordinal notation systems, present a family of strong yet simple systems, and give many examples of ordinals in these systems. While much of the materia…
Space-Efficient Circuit Evaluation
Dmytro Taranovsky
We prove that uniform circuits of size n can be evaluated in space O(n/log n). Thus, Space(O(n)) is not in uniform Size(o(n*log n)). For uniformity, we only require that the circui…
Reflective Cardinals
Dmytro Taranovsky
We introduce and axiomatize the notion of a reflective cardinal, use it to give semantics to higher order set theory, and explore connections between the notion of reflective cardi…
Constructive Mathematical Truth
Dmytro Taranovsky
We define constructive truth for arithmetic and for intuitionistic analysis, and investigate its properties. We also prove that the set of constructively true (first order) arithme…
Extending the Language of Set Theory
Dmytro Taranovsky
We discuss the problems of incompleteness and inexpressibility. We introduce almost self-referential formulas, use them to extend set theory, and relate their expressive power to t…
Determinacy Maximum
Dmytro Taranovsky
We propose a new determinacy hypothesis for transfinite games, use the hypothesis to extend the perfect set theorem, prove relationships between various determinacy hypotheses, exp…