{\Pi^1_2} -comprehension and the property of Ramsey

We show that a theory of autonomous iterated Ramseyness based on second order arithmetic (SOA) is proof-theoretically equivalent to ${\Pi^1_2}$ -comprehension. The property of Ramsey is defined as follows. Let X be a set of real numbers, i.e. a set of infinite sets of natural numbers. We call a set H of natural numbers homogeneous for X if either all infinite subsets of H are in X or all infinite subsets of H are not in X. X has the property of Ramsey if there exists a set which is homogeneous for X. The property of Ramsey is considered in reverse mathematics to compare the strength of subsystems of SOA. To characterize the system of ${\Pi^1_2}$ -comprehension in terms of Ramseyness we introduce a system of autonomous iterated Ramseyness, called R-calculus. We augment the language of SOA with additional set terms (called R-terms) ${R\vec{x}X\phi(\vec{x},X)}$ for each first order formula ${\phi(\vec{x},X)}$ (where φ may contain further R-terms). The R-calculus is a system which comprises comprehension for all first order formulas (which may contain R-terms or other set parameters) and defining axioms for the R-terms which claim that for each ${\vec{x}}$ , we can remove finitely many elements from the set ${R\vec{x}X\phi(\vec{x},X)}$ such that the remaining set is homogeneous for ${\{{X}{\phi(\vec{x},X)\}}}$ . We show that the R-calculus proves the same ${\Pi^1_1}$ -sentences as the system of ${\Pi^1_2}$ -comprehension.     

Decidability of the AE-theory of the lattice of $${\varPi }_1^0$$ classes

An AE-sentence is a sentence in prenex normal form with all universal quantifiers preceding all existential quantifiers, and the AE-theory of a structure is the set of all AE-sentences true in the structure. We show that the AE-theory of \((\mathscr {L}({\varPi }_1^0), \cap , \cup , 0, 1)\) is decidable by giving a procedure which, for any AE-sentence in the language, determines the truth or falsity of the sentence in our structure.     

\Pi^0_1-Presentations of Algebras

In this paper we study the question as to which computable algebras are isomorphic to non-computable -algebras. We show that many known algebras such as the standard model of arithmetic, term algebras, fields, vector spaces and torsion-free abelian groups have non-computable-presentations. On the other hand, many of this structures fail to have non-computable -presentation.This research was partially supported by the Marsden Fund of New Zealand. The third author’s research was partially supported by RFFR grant No. 02-01-00593 and Council for Grants under RF President, project NSh-2112.2003.1.     

Strict {Pi^1_1}-reflection in bounded arithmetic

We prove two conservation results involving a generalization of the principle of strict P¹₁{Pi^1_1}-reflection, in the context of bounded arithmetic. In this context a separation between the concepts of bounded set and binary sequence seems to emerge as fundamental.     

A high noncuppable {\Sigma^0_2} e-degree

We construct a e-degree which is both high and noncuppable. Thus demonstrating the existence of a high e-degree whose predecessors are all properly .     

On diophantine equations of the form {({\boldsymbol x}-{\boldsymbol a}_{\bf 1})({\boldsymbol x}-{\boldsymbol a}_{\bf 2}) \ldots ({\boldsymbol x}-{\boldsymbol a}_{\boldsymbol k}) + {\boldsymbol r} = {\boldsymbol y}^{ \boldsymbol n}}

Erd?s and Selfridge [3] proved that a product of consecutive integers can never be a perfect power. That is, the equation x(x?+?1)(x?+?2)...(x?+?(m???1))?=?y ⁿ has no solutions in positive integers x,m,n where m, n?>?1 and y?∈?Q. We consider the equation $$ (x-a_1)(x-a_2) \ldots (x-a_k) + r = y^n $$ where 0?≤?a ₁?<?a ₂?<???<?a _k are integers and, with r?∈?Q, n?≥?3 and we prove a finiteness theorem for the number of solutions x in Z, y in Q. Following that, we show that, more interestingly, for every nonzero integer n?>?2 and for any nonzero integer r which is not a perfect n-th power for which the equation admits solutions, k is bounded by an effective bound.     

A variant of Mathias forcing that preserves {\mathsf{ACA}_0}

We present and analyze ${F_\sigma}$ -Mathias forcing, which is similar but tamer than Mathias forcing. In particular, we show that this forcing preserves certain weak subsystems of second-order arithmetic such as ${\mathsf{ACA}_0}$ and ${\mathsf{WKL}_0 + \mathsf{I}\Sigma^0_2}$ , whereas Mathias forcing does not. We also show that the needed reals for ${F_\sigma}$ -Mathias forcing (in the sense of Blass in Ann Pure Appl Logic 109(1–2):77–88, 2001) are just the computable reals, as opposed to the hyperarithmetic reals for Mathias forcing.     

Torified varieties and their geometries over {\mathbb{F}_1}

This paper invents the notion of torified varieties: A torification of a scheme is a decomposition of the scheme into split tori. A torified variety is a reduced scheme of finite type over ${\mathbb Z}$ that admits a torification. Toric varieties, split Chevalley schemes and flag varieties are examples of this type of scheme. Given a torified variety whose torification is compatible with an affine open covering, we construct a gadget in the sense of Connes?CConsani and an object in the sense of Soulé and show that both are varieties over ${\mathbb{F}_1}$ in the corresponding notion. Since toric varieties and split Chevalley schemes satisfy the compatibility condition, we shed new light on all examples of varieties over ${\mathbb{F}_1}$ in the literature so far. Furthermore, we compare Connes?CConsani??s geometry, Soulé??s geometry and Deitmar??s geometry, and we discuss to what extent Chevalley groups can be realized as group objects over ${\mathbb{F}_1}$ in the given categories.     

Classification of multiple unilateral weighted shifts by $$\mathbb{A}_{\aleph _0 }$$

In this paper, it is characterized when a multiple unilateral weighted shift belongs to the classes \mathbbA_n ( 1 \leqslant n \leqslant à₀ )\mathbb{A}_n \left( {1 \leqslant n \leqslant \aleph _0 } \right). As a result, we perfect and generalize the previous conclusions given by H. Bercovici, C. Foias, and C. Pearcy. Moreover, we remark that Question 21 posed by Shields has been negatively answered.     

Maximum distance separable codes over {\mathbb{Z}_4} and {\mathbb{Z}_2 \times \mathbb{Z}_4}

Known upper bounds on the minimum distance of codes over rings are applied to the case of ${\mathbb Z_{2}\mathbb Z_{4}}$ -additive codes, that is subgroups of ${\mathbb Z_{2}^{\alpha}\mathbb Z_{4}^{\beta}}$ . Two kinds of maximum distance separable codes are studied. We determine all possible parameters of these codes and characterize the codes in certain cases. The main results are also valid when ?? = 0, namely for quaternary linear codes.     

Local solvability on {\mathbb{H}_1}: non-homogeneous operators

Local solvability and non-solvability are classified for left-invariant differential operators on the Heisenberg group ${\mathbb{H}_1}$ of the form L?=?P _n (X, Y)?+?Q(X, Y) where the P _n are certain homogeneous polynomials of order n?≥ 2 and Q is of lower order with ${X=\partial_x,\,Y=\partial_y+x\partial_w}$ on ${\mathbb{R}^3}$ . We extend previous studies of operators of the form P _n (X, Y) via representations involving ordinary differential operators with a parameter.     

Period functions for $ {\mathcal{C}^0} $- and $ {\mathcal{C}^1} $-flows

Let F:M ×\mathbbR ? M {\mathbf{F}}:M \times \mathbb{R} \to M be a continuous flow on a manifold M, let V ⊂ M be an open subset, and let x:V ? \mathbbR \xi :V \to \mathbb{R} be a continuous function. We say that ξ is a period function if F(x, ξ(x)) = x for all x ∈ V. Recently, for any open connected subset V ⊂ M; the author has described the structure of the set P(V) of all period functions on V. Assume that F is topologically conjugate to some C¹ {\mathcal{C}^1} -flow. It is shown in this paper that, in this case, the period functions of F satisfy some additional conditions that, generally speaking, are not satisfied for general continuous flows.     

Dimension Reduction for Finite Trees in \varvec{\ell _1}

We show that every $n$ -point tree metric admits a $(1+\varepsilon )$ -embedding into $\ell _1^{C(\varepsilon ) \log n}$ , for every $\varepsilon > 0$ , where $C(\varepsilon ) \le O\big ((\frac{1}{\varepsilon })^4 \log \frac{1}{\varepsilon })\big )$ . This matches the natural volume lower bound up to a factor depending only on $\varepsilon $ . Previously, it was unknown whether even complete binary trees on $n$ nodes could be embedded in $\ell _1^{O(\log n)}$ with $O(1)$ distortion. For complete $d$ -ary trees, our construction achieves $C(\varepsilon ) \le O\big (\frac{1}{\varepsilon ^2}\big )$ .     

Branching in the {\Sigma^0_2} -enumeration degrees: a new perspective

We give an alternative and more informative proof that every incomplete -enumeration degree is the meet of two incomparable -degrees, which allows us to show the stronger result that for every incomplete -enumeration degree a, there exist enumeration degrees x ₁ and x ₂ such that a, x ₁, x ₂ are incomparable, and for all b  ≤  a, b  =  (b ∨ x ₁ ) ∧ (b ∨ x ₂ ). The first author would like to thank her advisor, Andrea Sorbi, whose guidance made this paper possible. The second author has been supported by a Marie Curie Incoming International Fellowship of the European Community FP6 Program under contract number MIFI-CT-2006-021702.     

The intersection map of subgroups and the classes {\mathcal {PST}_c}, {\mathcal {PT}_c} and {\mathcal {T}_c}

A group G is called a ${\mathcal {T}_{c}}$ -group if every cyclic subnormal subgroup of G is normal in G. Similarly, classes ${\mathcal {PT}_{c}}$ and ${\mathcal {PST}_{c}}$ are defined, by requiring cyclic subnormal subgroups to be permutable or S-permutable, respectively. A subgroup H of a group G is called normal (permutable or S-permutable) cyclic sensitive if whenever X is a normal (permutable or S-permutable) cyclic subgroup of H there is a normal (permutable or S-permutable) cyclic subgroup Y of G such that ${X=Y \cap H}$ . We analyze the behavior of a collection of cyclic normal, permutable and S-permutable subgroups under the intersection map into a fixed subgroup of a group. In particular, we tie the concept of normal, permutable and S-permutable cyclic sensitivity with that of ${\mathcal {T}_c}$ , ${\mathcal {PT}_c}$ and ${\mathcal {PST}_c}$ groups. In the process we provide another way of looking at Dedekind, Iwasawa and nilpotent groups.