☆ 4.1 Article

Primitive recursive reverse mathematics

ANNALS OF PURE AND APPLIED LOGIC (2024)

相关参考文献

注意：仅列出部分参考文献，下载原文获取全部文献信息。

Article Mathematics

HOW STRONG IS RAMSEY'S THEOREM IF INFINITY CAN BE WEAK?

Leszek Aleksander Kolodziejczyk et al.

Summary: We study the first-order consequences of Ramsey's Theorem for k-colourings of n-tuples, for fixed n, k >= 2, over the relatively weak second-order arithmetic theory RCA(0)(*). Using the Chong-Mourad coding lemma, we show that in a model of RCA(0)(*) that does not satisfy Sigma(0)(1) induction, RTkn is equivalent to its relativization to any proper Sigma(0)(1) -definable cut, so its truth value remains unchanged in all extensions of the model with the same first-order universe.

JOURNAL OF SYMBOLIC LOGIC (2023)

添加到收藏夹

Article Mathematics

AN INSIDE/OUTSIDE RAMSEY THEOREM AND RECURSION THEORY

Marta Fiori-Carones et al.

Summary: Inspired by Ramsey's theorem, Rival and Sands proved the inside/outside Ramsey theorem which has strong computational strength and is equivalent to arithmetical comprehension. They also identified a weaker form that is equivalent to Ramsey's theorem for pairs. Combining their result with previous research, they showed that solving one instance of the Rival-Sands theorem corresponds to solving countably many instances of Ramsey's theorem for pairs simultaneously. They also analyzed the Weihrauch degrees and found that the Rival-Sands theorem has the same computational strength as the double jump of weak Konig's lemma.

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY (2022)

添加到收藏夹

Article Mathematics, Applied

To reorient is easier than to orient: An on-line algorithm for reorientation of graphs

Marta Fiori-Carones et al.

Summary: An online algorithm is defined to produce a transitive reorientation of a pseudo-transitive oriented graph, making Ghouila-Houri's theorem provable in RCA(0) and computably true.

COMPUTABILITY-THE JOURNAL OF THE ASSOCIATION CIE (2021)

添加到收藏夹

Article Mathematics, Applied

Weaker cousins of Ramsey's theorem over a weak base theory

Marta Fiori-Carones et al.

Summary: This paper focuses on a reverse-mathematical study of well-known consequences of Ramsey's theorem for pairs, particularly the CAC, ADS, and CRT22 principles. The study is conducted over the base theory RCA(0)*, identifying different variants of Ramsey-theoretic principles and their conservation properties in relation to Sigma(0)(1)-definable cuts. Results indicate that normal versions of the principles are equivalent to their relativizations, while long versions either imply RCA(0) or are conservative over RCA(0)*, with conservation results obtained using a variant of the grouping principle. Additionally, it is shown that the COH principle is never computably true in a model of RCA(0)* and does not follow from RT22 over RCA(0)*.

ANNALS OF PURE AND APPLIED LOGIC (2021)

添加到收藏夹

Article Mathematics, Applied

Punctual definability on structures

Iskander Kalimullin et al.

Summary: The study focuses on punctual categoricity on a cone and intrinsically punctual functions, providing complete structural characterizations using model-theoretic notions. It also answers a question regarding relational structures not being punctually universal, and applies this characterization to derive an algebraic characterization of relatively punctually categorical mono-unary structures.

ANNALS OF PURE AND APPLIED LOGIC (2021)

添加到收藏夹

Article Mathematics

PUNCTUAL CATEGORICITY SPECTRA OF COMPUTABLY CATEGORICAL STRUCTURES

N. A. Bazhenov et al.

ALGEBRA AND LOGIC (2021)

添加到收藏夹

Article Mathematics

FOUNDATIONS OF ONLINE STRUCTURE THEORY

Nikolay Bazhenov et al.

BULLETIN OF SYMBOLIC LOGIC (2019)

添加到收藏夹

Article Mathematics

The back-and-forth method and computability without delay

Alexander G. Melnikov et al.

ISRAEL JOURNAL OF MATHEMATICS (2019)

添加到收藏夹

Article Mathematics

The computability, definability, and proof theory of Artinian rings

Chris J. Conidis

ADVANCES IN MATHEMATICS (2019)

添加到收藏夹

Article Mathematics

Proper divisibility in computable rings

Noam Greenberg et al.

JOURNAL OF ALGEBRA (2017)

添加到收藏夹

Article Mathematics

REVERSE MATHEMATICS, YOUNG DIAGRAMS, AND THE ASCENDING CHAIN CONDITION

Kostas Hatzikiriakou et al.

JOURNAL OF SYMBOLIC LOGIC (2017)

添加到收藏夹

Article Computer Science, Theory & Methods

Algebraic structures computable without delay

Iskander Kalimullin et al.

THEORETICAL COMPUTER SCIENCE (2017)

添加到收藏夹

Article Mathematics, Applied

Categorical characterizations of the natural numbers require primitive recursion

Leszek Aleksander Kolodziejczyk et al.

ANNALS OF PURE AND APPLIED LOGIC (2015)

添加到收藏夹

Article Mathematics, Applied

WKL0 and induction principles in model theory

David R. Belanger

ANNALS OF PURE AND APPLIED LOGIC (2015)

添加到收藏夹

Article Mathematics, Applied

On the existence of a connected component of a graph

Kirill Gura et al.

COMPUTABILITY-THE JOURNAL OF THE ASSOCIATION CIE (2015)

添加到收藏夹

Article Mathematics

COMPUTABLE ABELIAN GROUPS

Alexander G. Melnikov

BULLETIN OF SYMBOLIC LOGIC (2014)

添加到收藏夹

Article Mathematics

Infinite dimensional proper subspaces of computable vector spaces

Chris J. Conidis

JOURNAL OF ALGEBRA (2014)

添加到收藏夹

Article Mathematics

REVERSE MATHEMATICS OF FIRST-ORDER THEORIES WITH FINITELY MANY MODELS

David R. Belanger

JOURNAL OF SYMBOLIC LOGIC (2014)

添加到收藏夹

Article Mathematics

Baire Categoricity and Σ10-Induction

Stephen G. Simpson

NOTRE DAME JOURNAL OF FORMAL LOGIC (2014)

添加到收藏夹

Article Mathematics, Applied

Reverse mathematics and Peano categoricity

Stephen G. Simpson et al.

ANNALS OF PURE AND APPLIED LOGIC (2013)

添加到收藏夹

Article Mathematics

On the strength of Ramsey's theorem without σ1-induction

Keita Yokoyama

MATHEMATICAL LOGIC QUARTERLY (2013)

添加到收藏夹

Article Mathematics

REVERSE MATHEMATICS AND A RAMSEY-TYPE KONIG'S LEMMA

Stephen Flood

JOURNAL OF SYMBOLIC LOGIC (2012)

添加到收藏夹

Article Mathematics

WEIHRAUCH DEGREES, OMNISCIENCE PRINCIPLES AND WEAK COMPUTABILITY

Vasco Brattka et al.

JOURNAL OF SYMBOLIC LOGIC (2011)

添加到收藏夹

Article Mathematics

THE ATOMIC MODEL THEOREM AND TYPE OMITTING

Denis R. Hirschfeldt et al.

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY (2009)

添加到收藏夹

Article Mathematics

How Incomputable Is the Separable Hahn-Banach Theorem?

Guido Gherardi et al.

NOTRE DAME JOURNAL OF FORMAL LOGIC (2009)

添加到收藏夹

Article Mathematics

Subspaces of computable vector spaces

Rodney G. Downey et al.

JOURNAL OF ALGEBRA (2007)

添加到收藏夹

Article Mathematics

The jump of a Σn-cut

C. T. Chong et al.

JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES (2007)

添加到收藏夹

Article Mathematics

Spectra of structures and relations

Valentina S. Harizanov et al.

JOURNAL OF SYMBOLIC LOGIC (2007)

添加到收藏夹

Article Mathematics

Effective Borel measurability and reducibility of functions

V Brattka

MATHEMATICAL LOGIC QUARTERLY (2005)

添加到收藏夹

Article Mathematics, Applied

Sigma(n)-bounding and Delta(n)-induction

TA Slaman

PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY (2004)

添加到收藏夹

Article Mathematics

On the strength of Ramsey's theorem for pairs

PA Cholak et al.

JOURNAL OF SYMBOLIC LOGIC (2001)

添加到收藏夹

Article Mathematics, Applied

Things that can and things that cannot be done in PRA

U Kohlenbach

ANNALS OF PURE AND APPLIED LOGIC (2000)

添加到收藏夹

© Peeref 2019-2024. All rights reserved.