Yong Cheng

Let Z2, Z3, and Z4 denote 2nd, 3rd, and 4thorder arithmetic, respectively. We let Harrington’s Principle, HP, denote the statement that there is a realxsuch that everyx-admissible ordinal is a cardinal in L. The known proofs of Harrington’s theorem are done in two steps. The first step is provable in Z2. In this paper we show that Z2+ HP is equiconsistent with ZFC and that Z3+ HP is equiconsistent with ZFC + there exists a remarkable cardinal. As a corollary, Z3+ HP does not imply 0♯ exists, whereas Z4+ HP does. We also study strengthenings of Harrington’s Principle over 2ndand 3rdorder arithmetic.

Gödel's true-but-unprovable sentence from the first incompleteness theorem is purely logical in nature, i.e. not mathematically natural or interesting. An interesting problem is to find mathematically natural and interesting statements that are similarly unprovable. A lot of research has since been done in this direction, most notably by Harvey Friedman. A lot of examples of concrete incompleteness with real mathematical content have been found to date. This brief contributes to Harvey Friedman's research program on concrete incompleteness for higher-order arithmetic and gives a specific example of concrete mathematical theorems which is expressible in second-order arithmetic but the minimal system in higher-order arithmetic to prove it is fourth-order arithmetic. This book first examines the following foundational question: are all theorems in classic mathematics expressible in second-order arithmetic provable in second-order arithmetic? The author gives a counterexample for this question and isolates this counterexample from the Martin-Harrington Theorem in set theory. It shows that the statement “Harrington's principle implies zero sharp" is not provable in second-order arithmetic. This book further examines what is the minimal system in higher-order arithmetic to prove the theorem “Harrington's principle implies zero sharp" and shows that it is neither provable in second-order arithmetic or third-order arithmetic, but provable in fourth-order arithmetic. The book also examines the large cardinal strength of Harrington's principle and its strengthening over second-order arithmetic and third-order arithmetic.

Gödelʼs incompleteness theorems, published in 1931, are important and profound results in the foundations and philosophy of mathematics. On the basis of new advances in research on incompleteness in the literature, we discuss the correct interpretations of Gödelʼs incompleteness theorems, their inffuence on various ffelds, and the limit of their applicability. The motivation of this paper is threefold: to explore the foundational and philosophical signiffcance of new advances in research on incompleteness since Gödel, to introduce new advances in research on incompleteness to the general philosophy community, and to commemorate the 90th anniversary of the publication of Gödelʼs incompleteness theorems.

Rosser theories play an important role in the study of the incompleteness phenomenon and meta-mathematics of arithmetic. In this paper, we first define the notions of n-Rosser theories, exact n-Rosser theories, effectively n-Rosser theories and effectively exact n-Rosser theories. Our definitions are not restricted to arithmetic languages. Then we systematically examine properties of n-Rosser theories and relationships among them. Especially, we generalize some important theorems about Rosser theories for recursively enumerable sets in the literature to n-Rosser theories in a general setting.

This paper belongs to the research on the limit of the first incompleteness theorem. Effectively inseparable (EI) theories can be viewed as an effective version of essentially undecidable (EU) theories, and EI is stronger than EU. We examine this question: Are there minimal effectively inseparable theories with respect to interpretability? We propose tEI, the theory version of EI. We first prove that there are no minimal tEI theories with respect to interpretability (i.e., for any tEI theory T, we can effectively find a theory which is tEI and strictly weaker than T with respect to interpretability). By a theorem due to Pour-EI, we have that tEI is equivalent with EI. Thus, there are no minimal EI theories with respect to interpretability. Also, we prove that there are no minimal finitely axiomatizable EI theories with respect to interpretability.

In this work, we aim at understanding incompleteness in an abstract way via metamathematical properties of formal theories. We systematically examine the relationships between the following twelve important metamathematical properties of arithmetical theories: Rosser, EI (effectively inseparable), RI (recursively inseparable), TP (Turing persistent), EHU (essentially hereditarily undecidable), EU (essentially undecidable), Creative, $0^{\prime }$ (theories with Turing degree $0^{\prime }$), REW (all RE sets are weakly representable), RFD (all recursive functions are definable), RSS (all recursive sets are strongly representable), RSW (all recursive sets are weakly representable). Given any two properties P and Q in the above list, we examine whether P implies Q.

In this paper, we prove that: if κ is supercompact and the HOD Hypothesis holds, then there is a proper class of regular cardinals in Vκ which are measurable in HOD. Woodin also proved this result independently [11]. As a corollary, we prove Woodin’s Local Universality Theorem. This work shows that under the assumption of the HOD Hypothesis and supercompact cardinals, large cardinals in V are reflected to be large cardinals in HOD in a local way, and reveals the huge difference between HOD-supercompact cardinals and supercompact cardinals under the HOD Hypothesis.

ABSTRACT We use Gödel’s incompleteness theorems as a case study for investigating mathematical depth. We examine the philosophical question of what the depth of Gödel’s incompleteness theorems consists in. We focus on the methodological study of the depth of Gödel’s incompleteness theorems, and propose three criteria to account for the depth of the incompleteness theorems: influence, fruitfulness, and unity. Finally, we give some explanations for our account of the depth of Gödel’s incompleteness theorems.

This work is motivated by the problem of finding the limit of the applicability of the first incompleteness theorem (G1). A natural question is, can we find a minimal theory for which G1 holds? We examine the Turing degree structure of recursively enumerable (RE) theories for which G1 holds and the interpretation degree structure of RE theories weaker than the theory R with respect to interpretation for which G1 holds. We answer all questions that we posed in [2], and prove more results about them. It is known that there are no minimal essentially undecidable theories with respect to interpretation. We generalize this result and give some general characterizations, which tell us under what conditions there are no minimal RE theories having some property with respect to interpretation.

This is a paper for a special issue of Semiotic Studies devoted to Stanislaw Krajewski’s paper. This paper gives some supplementary notes to Krajewski’s on the Anti-Mechanist Arguments based on Gödel’s incompleteness theorem. In Section 3, we give some additional explanations to Section 4–6 in Krajewski’s and classify some misunderstandings of Gödel’s incompleteness theorem related to AntiMechanist Arguments. In Section 4 and 5, we give a more detailed discussion of Gödel’s Disjunctive Thesis, Gödel’s Undemonstrability of Consistency Thesis and the definability of natural numbers as in Section 7–8 in Krajewski’s, describing how recent advances bear on these issues.

Isaacson’s thesis claims that Peano arithmetic is complete with respect to arithmetical truth as defined by Isaacson. According to this thesis, the incompleteness phenomenon revealed in Gödel’s incompleteness theorems does not pertain to arithmetical incompleteness. In our analysis, we discuss both the advantages and disadvantages of Isaacson’s thesis. Additionally, we propose seven case examples that may pose potential challenges to Isaacson’s thesis. To effectively defend Isaacson’s thesis, one must address these case examples. We conclude that either Isaacson’s notion of arithmetical truth is not right, or that it is difficult to defend Isaacson’s thesis.

In this paper, we examine the limit of applicability of Gödel’s first incompleteness theorem. We first define the notion “G1 holds for the theory T”. This paper is motivated by the following question: can we find a theory with a minimal degree of interpretation for which G1 holds. To approach this question, we first examine the following question: is there a theory T such that Robinson’s R interprets T but T does not interpret R and G1 holds for T? In this paper, we show that there are many such theories based on Jeřábek’s work using some model theory. We prove that for each recursively inseparable pair (A,B), we can construct a r.e. theory $U_{(A,B)}$ such that $U_{(A,B)}$ is weaker than R w.r.t. interpretation and G1 holds for $U_{(A,B)}$. As a corollary, we answer a question from Albert Visser. Moreover, we prove that for any Turing degree $0< d<0^{\prime }$, there is a theory T with Turing degree d such that G1 holds for T and T is weaker than R w.r.t. Turing reducibility. As a corollary, based on Shoenfield’s work using some recursion theory, we show that there is no theory with a minimal degree of Turing reducibility for which G1 holds.

This paper studies the resilience of remarkable cardinals—a type of large cardinal weaker than measurable cardinals—under various forcing extensions. The authors show that if a cardinal is remarkable, it can be made indestructible under certain types of forcing, including those that are closed and distributive below the cardinal, as well as two-step iterations involving Cohen forcing. A key tool introduced is the "remarkable Laver function," which helps anticipate sets during forcing. Applications include forcing any desired pattern of the continuum function above a remarkable cardinal and constructing a model where the cardinal is not weakly compact in HOD.