The maximal linear extension theorem in second order arithmetic

We show that the maximal linear extension theorem for well partial orders is equivalent over RCA ₀ to ATR ₀. Analogously, the maximal chain theorem for well partial orders is equivalent to ATR ₀ over RCA ₀.     

Complex analysis in subsystems of second order arithmetic

This research is motivated by the program of Reverse Mathematics. We investigate basic part of complex analysis within some weak subsystems of second order arithmetic, in order to determine what kind of set existence axioms are needed to prove theorems of basic analysis. We are especially concerned with Cauchy’s integral theorem. We show that a weak version of Cauchy’s integral theorem is proved in RCAo. Using this, we can prove that holomorphic functions are analytic in RCAo. On the other hand, we show that a full version of Cauchy’s integral theorem cannot be proved in RCAo but is equivalent to weak König’s lemma over RCAo.     

Representability in some systems of second order arithmetic

We answer two questions posed in a recent paper by H. B. Enderton by giving characterizations of the sets of integers weakly and strongly representable in a system of second order arithmetic with an infinity rule of inference. The results generalize to each of a family of such systems. This paper was written while the author held a Science Research Council fellowship.     

Separations of first and second order theories in bounded arithmetic

We prove that PTC_N(n) (the polynomial time closure of the nonstandard natural number n in the model N of S₂.) cannot be a model of U¹₂. This implies that there exists a first order sentence of bounded arithmetic which is provable in U¹₂ but does not hold in PTC_N(n).     

Determinacy of Wadge classes and subsystems of second order arithmetic

In this paper we study the logical strength of the determinacy of infinite binary games in terms of second order arithmetic. We define new determinacy schemata inspired by the Wadge classes of Polish spaces and show the following equivalences over the system RCA₀*, which consists of the axioms of discrete ordered semi‐rings with exponentiation, Δ₁⁰ comprehension and Π₀⁰ induction, and which is known as a weaker system than the popularbase theory RCA₀: 1. Bisep(Δ₁⁰, Σ₁⁰)‐Det* ? WKL₀, (1) 2. Bisep(Δ₁⁰, Σ₂⁰)‐Det* ? ATR₀ + Σ₁¹ induction, (2) 3. Bisep(Σ₁⁰, Σ₂⁰)‐Det* ? Sep(Σ₁⁰, Σ₂⁰)‐Det* ? Π₁¹‐CA₀, (3) 4. Bisep(Δ₂⁰, Σ₂⁰)‐Det* ? Π₁¹‐TR₀, (4) where Det* stands for the determinacy of infinite games in the Cantor space (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Infinite games in the Cantor space and subsystems of second order arithmetic

In this paper we study the determinacy strength of infinite games in the Cantor space and compare them with their counterparts in the Baire space. We show the following theorems: 1. RCA₀ ? ‐Det* ? ‐Det* ? WKL₀. 2. RCA₀ ? ( )2‐Det* ? ACA₀. 3. RCA₀ ? ‐Det* ? ‐Det* ? ‐Det ? ‐Det ? ATR₀. 4. For 1 < k < ω, RCA₀ ? ( )_k ‐Det* ? ( )_{k –1}‐Det. 5. RCA₀ ? ‐Det* ? ‐Det. Here, Det* (respectively Det) stands for the determinacy of infinite games in the Cantor space (respectively the Baire space), and ( )_k is the collection of formulas built from formulas by applying the difference operator k – 1 times. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On Herbrand consistency in weak arithmetic

We prove that the G?del incompleteness theorem holds for a weak arithmetic T = IΔ₀ + Ω₂ in the form

Parametric Presburger arithmetic: complexity of counting and quantifier elimination

We consider an expansion of Presburger arithmetic which allows multiplication by k parameters $t_1,\dots ,t_k$. A formula in this language defines a parametric set $S_{\mathbf{t}}?{\mathbb{Z}}^d$ as $\mathbf{t}$ varies in ${\mathbb{Z}}^k$, and we examine the counting function $|S_{\mathbf{t}}|$ as a function of t . For a single parameter, it is known that $|S_t|$ can be expressed as an eventual quasi‐polynomial (there is a period m such that, for sufficiently large t, the function is polynomial on each of the residue classes mod m). We show that such a nice expression is impossible with 2 or more parameters. Indeed (assuming $\mathbf{P}\ne \mathbf{NP}$) we construct a parametric set $S_{t_1,t_2}$ such that $|S_{t_1,t_2}|$ is not even polynomial‐time computable on input $(t_1,t_2)$. In contrast, for parametric sets $S_{\mathbf{t}}?{\mathbb{Z}}^d$ with arbitrarily many parameters, defined in a similar language without the ordering relation, we show that $|S_{\mathbf{t}}|$ is always polynomial‐time computable in the size of t , and in fact can be represented using the gcd and similar functions.     

A fuzzy-set approach to treat determinacy and consistency of linguistic terms in multi-criteria decision making

A fuzzy-set-based approach is presented to describe linguistic information in multi-criteria decision making. After having introduced concepts of determinacy and consistency of linguistic terms, the understandable degree and consistence degree of linguistic terms are illustrated by these two concepts. A case study is demonstrated for the proposed decision-making model with an analytical conclusion of both advantages and disadvantages.     

The second order pullback equation

Let $f,g$ be two closed $k$ -forms over $\mathbb{R }^{n}.$ The pullback equation studies the existence of a diffeomorphism $\varphi :\mathbb{R }^{n} \rightarrow \mathbb{R }^{n}$ such that $$\begin{aligned} \varphi ^{*}(g)=f. \end{aligned}$$ We prove two types of results. The first one sharpens some of the existing regularity results. The second one discusses the possibility of choosing the map $\varphi $ as the gradient of a function $\Phi :\mathbb{R }^{n} \rightarrow \mathbb R .$ We show that this is a very rare event unless the two forms are constant.     

On arithmetic complexity of certain constructive logics

A constructive arithmetical theory is an arbitrary set of closed arithmetical formulas that is closed with respect to derivability in an intuitionsitic arithmetic with the Markov principle and the formal Church thesis. For each arithmetical theory T there is a corresponding logic L(T) consisting of closed predicate formulas in which all arithmetic instances belong to T. For so-called internally enumerable constructive arithmetical theories with the property of existentiality, it is proved that the logic L(T) is II₁ ^T -@#@ complete. This implies, for example, that the logic of traditional constructivism is II₂ ⁰-complete.Translated from Matematicheskie Zametki, Vol. 52, No. 1, pp. 94–104, July, 1992.     

Hurwitz quaternion order and arithmetic Riemann surfaces

We clarify the explicit structure of the Hurwitz quaternion order, which is of fundamental importance in Riemann surface theory and systolic geometry.