Neil Thapen (2005)
Fundamenta Mathematicae
Similarity:
Slaman recently proved that Σₙ collection is provable from Δₙ induction plus exponentiation, partially answering a question of Paris. We give a new version of this proof for the case n = 1, which only requires the following very weak form of exponentiation: " exists for some y sufficiently large that x is smaller than some primitive recursive function of y".
Zofia Adamowicz (2002)
Fundamenta Mathematicae
Similarity:
We prove that the Gödel incompleteness theorem holds for a weak arithmetic Tₘ = IΔ₀ + Ωₘ, for m ≥ 2, in the form Tₘ ⊬ HCons(Tₘ), where HCons(Tₘ) is an arithmetic formula expressing the consistency of Tₘ with respect to the Herbrand notion of provability. Moreover, we prove , where is HCons relativised to the definable cut Iₘ of (m-2)-times iterated logarithms. The proof is model-theoretic. We also prove a certain non-conservation result for Tₘ.
Dmitrii Zhelezov (2014)
Acta Arithmetica
Similarity:
Let B be a set of complex numbers of size n. We prove that the length of the longest arithmetic progression contained in the product set B.B = bb’ | b,b’ ∈ B cannot be greater than O((nlog²n)/(loglogn)) and present an example of a product set containing an arithmetic progression of length Ω(nlogn). For sets of complex numbers we obtain the upper bound .
Vítězslav Švejdar (1999)
Commentationes Mathematicae Universitatis Carolinae
Similarity:
The set of all indices of all functions provably recursive in any reasonable theory is shown to be recursively isomorphic to , where is -complete set.
Ali Enayat (2006)
Fundamenta Mathematicae
Similarity:
We establish the following model-theoretic characterization of the fragment IΔ₀ + Exp + BΣ₁ of Peano arithmetic in terms of fixed points of automorphisms of models of bounded arithmetic (the fragment IΔ₀ of Peano arithmetic with induction limited to Δ₀-formulae). Theorem A. The following two conditions are equivalent for a countable model of the language of arithmetic: (a) satisfies IΔ₀ + BΣ₁ + Exp; (b) for some nontrivial automorphism j of an end extension of that satisfies IΔ₀. Here...
Aldo Ursini (1977)
Rendiconti del Seminario Matematico della Università di Padova
Similarity:
В.Л. Михеев (1991)
Algebra i Logika
Similarity:
Ferreira, Fernando (1995)
Portugaliae Mathematica
Similarity:
Gurusamy Rengasamy Vijayakumar (2010)
Discussiones Mathematicae Graph Theory
Similarity:
An injective map from the vertex set of a graph G-its order may not be finite-to the set of all natural numbers is called an arithmetic (a geometric) labeling of G if the map from the edge set which assigns to each edge the sum (product) of the numbers assigned to its ends by the former map, is injective and the range of the latter map forms an arithmetic (a geometric) progression. A graph is called arithmetic (geometric) if it admits an arithmetic (a geometric) labeling. In this article,...
Saad I. El-Zanati, C. Vanden Eynden (2006)
Discussiones Mathematicae Graph Theory
Similarity:
This paper concerns when the complete graph on n vertices can be decomposed into d-dimensional cubes, where d is odd and n is even. (All other cases have been settled.) Necessary conditions are that n be congruent to 1 modulo d and 0 modulo . These are known to be sufficient for d equal to 3 or 5. For larger values of d, the necessary conditions are asymptotically sufficient by Wilson’s results. We prove that for each odd d there is an infinite arithmetic progression of even integers...