Search

In this paper, we provide a simple proof of the Holonomy theorem using a new Lyndon-Chiswell length function on the Karnofsky-Rhodes expansion of a semigroup. Unexpectedly, we have both a left and a right action on the Chiswell tree by elliptic maps.

Abstract: Frege’sGrundgesetzewas one of the 19th century forerunners to contemporary set theory which was plagued by the Russell paradox. In recent years, it has been shown that subsystems of theGrundgesetzeformed by restricting the comprehension schema are consistent. One aim of this paper is to ascertain how much set theory can be developed within these consistent fragments of theGrundgesetze, and our main theorem (Theorem 2.9) shows that there is a model of a fragment of theGrundgesetzewhich defines a model of all the axioms of Zermelo–Fraenkel set theory with the exception of the power set axiom. The proof of this result appeals to Gödel’s constructible universe of sets and to Kripke and Platek’s idea of the projectum, as well as to a weak version of uniformization (which does not involve knowledge of Jensen’s fine structure theory). The axioms of theGrundgesetzeare examples ofabstraction principles, and the other primary aim of this paper is to articulate a sufficient condition for the consistency of abstraction principles with limited amounts of comprehension (Theorem 3.5). As an application, we resolve an analogue of the joint consistency problem in the predicative setting.

AbstractFrege’sGrundgesetzewas one of the 19th century forerunners to contemporary set theory which was plagued by the Russell paradox. In recent years, it has been shown that subsystems of theGrundgesetzeformed by restricting the comprehension schema are consistent. One aim of this paper is to ascertain how much set theory can be developed within these consistent fragments of theGrundgesetze, and our main theorem (Theorem 2.9) shows that there is a model of a fragment of theGrundgesetzewhich defines a model of all the axioms of Zermelo–Fraenkel set theory with the exception of the power set axiom. The proof of this result appeals to Gödel’s constructible universe of sets and to Kripke and Platek’s idea of the projectum, as well as to a weak version of uniformization (which does not involve knowledge of Jensen’s fine structure theory). The axioms of theGrundgesetzeare examples ofabstraction principles, and the other primary aim of this paper is to articulate a sufficient condition for the consistency of abstraction principles with limited amounts of comprehension (Theorem 3.5). As an application, we resolve an analogue of the joint consistency problem in the predicative setting.

This paper presents new constructions of models of Hume's Principle and BasicLaw V with restricted amounts of comprehension. The techniques used in theseconstructions are drawn from hyperarithmetic theory and the model theory offields, and formalizing these techniques within various subsystems ofsecond-order Peano arithmetic allows one to put upper and lower bounds on theinterpretability strength of these theories and hence to compare these theoriesto the canonical subsystems of second-order arithmetic. The main results ofthis paper are: (i) there is a consistent extension of the hyperarithmeticfragment of Basic Law V which interprets the hyperarithmetic fragment ofsecond-order Peano arithmetic, and (ii) the hyperarithmetic fragment of Hume'sPrinciple does not interpret the hyperarithmetic fragment of second-order Peanoarithmetic, so that in this specific sense there is no predicative version ofFrege's Theorem.

This paper presents new constructions of models of Hume's Principle and BasicLaw V with restricted amounts of comprehension. The techniques used in theseconstructions are drawn from hyperarithmetic theory and the model theory offields, and formalizing these techniques within various subsystems ofsecond-order Peano arithmetic allows one to put upper and lower bounds on theinterpretability strength of these theories and hence to compare these theoriesto the canonical subsystems of second-order arithmetic. The main results ofthis paper are: (i) there is a consistent extension of the hyperarithmeticfragment of Basic Law V which interprets the hyperarithmetic fragment ofsecond-order Peano arithmetic, and (ii) the hyperarithmetic fragment of Hume'sPrinciple does not interpret the hyperarithmetic fragment of second-order Peanoarithmetic, so that in this specific sense there is no predicative version ofFrege's Theorem.

Let $p$ be a prime, and let $n>0$ and $r$ be integers. In this paper we studyFleck's quotient $$F_p(n,r)=(-p)^{-\lfloor(n-1)/(p-1)\rfloor} \sum_{k=r(modp)}\binom {n}{k}(-1)^k\in Z.$$ We determine $F_p(n,r)$ mod $p$ completely by certain number-theoretic andcombinatorial methods; consequently, if $2\le n\le p$ then$$\sum_{k=1}^n(-1)^{pk-1}\binom{pn-1}{pk-1} \equiv(n-1)!B_{p-n}p^n (modp^{n+1}),$$ where $B_0,B_1,...$ are Bernoulli numbers. We also establish theKummer-type congruence $F_p(n+p^a(p-1),r)\equiv F_p(n,r) (mod p^a)$ for$a=1,2,3,...$, and reveal some connections between Fleck's quotients and classnumbers of the quadratic fields $\Q(\sqrt{\pm p})$ and the $p$-th cyclotomicfield $\Q(\zeta_p)$. In addition, generalized Fleck quotients are also studiedin this paper.

Let $p$ be a prime, and let $n>0$ and $r$ be integers. In this paper we studyFleck's quotient $$F_p(n,r)=(-p)^{-\lfloor(n-1)/(p-1)\rfloor} \sum_{k=r(modp)}\binom {n}{k}(-1)^k\in Z.$$ We determine $F_p(n,r)$ mod $p$ completely by certain number-theoretic andcombinatorial methods; consequently, if $2\le n\le p$ then$$\sum_{k=1}^n(-1)^{pk-1}\binom{pn-1}{pk-1} \equiv(n-1)!B_{p-n}p^n (modp^{n+1}),$$ where $B_0,B_1,...$ are Bernoulli numbers. We also establish theKummer-type congruence $F_p(n+p^a(p-1),r)\equiv F_p(n,r) (mod p^a)$ for$a=1,2,3,...$, and reveal some connections between Fleck's quotients and classnumbers of the quadratic fields $\Q(\sqrt{\pm p})$ and the $p$-th cyclotomicfield $\Q(\zeta_p)$. In addition, generalized Fleck quotients are also studiedin this paper.

The Denjoy integral is an integral that extends the Lebesgue integral and canintegrate any derivative. In this paper, it is shown that the graph of theindefinite Denjoy integral $f\mapsto \int_a^x f$ is a coanalytic non-Borelrelation on the product space $M[a,b]\times C[a,b]$, where $M[a,b]$ is thePolish space of real-valued measurable functions on $[a,b]$ and where $C[a,b]$is the Polish space of real-valued continuous functions on $[a,b]$. Using thesame methods, it is also shown that the class of indefinite Denjoy integrals,called $ACG_{\ast}[a,b]$, is a coanalytic but not Borel subclass of the space$C[a,b]$, thus answering a question posed by Dougherty and Kechris. Some basicmodel theory of the associated spaces of integrable functions is also studied.Here the main result is that, when viewed as an $\mathbb{R}[X]$-module with theindeterminate $X$ being interpreted as the indefinite integral, the space ofcontinuous functions on the interval $[a,b]$ is elementarily equivalent to theLebesgue-integrable and Denjoy-integrable functions on this interval, and eachis stable but not superstable, and that they all have a common decidable theorywhen viewed as $\mathbb{Q}[X]$-modules.

The Denjoy integral is an integral that extends the Lebesgue integral and canintegrate any derivative. In this paper, it is shown that the graph of theindefinite Denjoy integral $f\mapsto \int_a^x f$ is a coanalytic non-Borelrelation on the product space $M[a,b]\times C[a,b]$, where $M[a,b]$ is thePolish space of real-valued measurable functions on $[a,b]$ and where $C[a,b]$is the Polish space of real-valued continuous functions on $[a,b]$. Using thesame methods, it is also shown that the class of indefinite Denjoy integrals,called $ACG_{\ast}[a,b]$, is a coanalytic but not Borel subclass of the space$C[a,b]$, thus answering a question posed by Dougherty and Kechris. Some basicmodel theory of the associated spaces of integrable functions is also studied.Here the main result is that, when viewed as an $\mathbb{R}[X]$-module with theindeterminate $X$ being interpreted as the indefinite integral, the space ofcontinuous functions on the interval $[a,b]$ is elementarily equivalent to theLebesgue-integrable and Denjoy-integrable functions on this interval, and eachis stable but not superstable, and that they all have a common decidable theorywhen viewed as $\mathbb{Q}[X]$-modules.

This paper transfers a randomized algorithm, originally used in geometric optimization, to computational problems in commutative algebra. We show that Clarkson's sampling algorithm can be applied to two problems in computational algebra: solving large-scale polynomial systems and finding small generating sets of graded ideals. The cornerstone of our work is showing that the theory of violator spaces of Gärtner et al. applies to polynomial ideal problems. To show this, one utilizes a Helly-type result for algebraic varieties. The resulting algorithms have expected runtime linear in the number of input polynomials, making the ideas interesting for handling systems with very large numbers of polynomials, but whose rank in the vector space of polynomials is small (e.g., when the number of variables and degree is constant).

This paper transfers a randomized algorithm, originally used in geometric optimization, to computational problems in commutative algebra. We show that Clarkson's sampling algorithm can be applied to two problems in computational algebra: solving large-scale polynomial systems and finding small generating sets of graded ideals. The cornerstone of our work is showing that the theory of violator spaces of Gärtner et al. applies to polynomial ideal problems. To show this, one utilizes a Helly-type result for algebraic varieties. The resulting algorithms have expected runtime linear in the number of input polynomials, making the ideas interesting for handling systems with very large numbers of polynomials, but whose rank in the vector space of polynomials is small (e.g., when the number of variables and degree is constant).

Abstract: Frege’s theorem says that second-order Peano arithmetic is interpretable in Hume’s Principle and full impredicative comprehension. Hume’s Principle is one example of anabstraction principle, while another paradigmatic example is Basic Law V from Frege’sGrundgesetze. In this paper we study the strength of abstraction principles in the presence of predicative restrictions on the comprehension schema, and in particular we study a predicative Fregean theory which contains all the abstraction principles whose underlying equivalence relations can be proven to be equivalence relations in a weak background second-order logic. We show that this predicative Fregean theory interprets second-order Peano arithmetic (cf. Theorem 3.2).

AbstractFrege’s theorem says that second-order Peano arithmetic is interpretable in Hume’s Principle and full impredicative comprehension. Hume’s Principle is one example of anabstraction principle, while another paradigmatic example is Basic Law V from Frege’sGrundgesetze. In this paper we study the strength of abstraction principles in the presence of predicative restrictions on the comprehension schema, and in particular we study a predicative Fregean theory which contains all the abstraction principles whose underlying equivalence relations can be proven to be equivalence relations in a weak background second-order logic. We show that this predicative Fregean theory interprets second-order Peano arithmetic (cf. Theorem 3.2).

In his 1936 paper, On the Concept of Logical Consequence, Tarski introduced the celebrated definition of logical consequence: “The sentenceσ follows logically from the sentences of the class Γ if and only if every model of the class Γ is also a model of the sentence σ.” [55, p. 417] This definition, Tarski said, is based on two very basic intuitions, “essential for the proper concept of consequence” [55, p. 415] and reflecting common linguistic usage: “Consider any class Γ of sentences and a sentence which follows from the sentences of this class. From an intuitive standpoint it can never happen that both the class Γ consists only of true sentences and the sentence σ is false. Moreover, … we are concerned here with the concept of logical, i.e., formal, consequence.” [55, p. 414] Tarski believed his definition of logical consequence captured the intuitive notion: “It seems to me that everyone who understands the content of the above definition must admit that it agrees quite well with common usage. … In particular, it can be proved, on the basis of this definition, that every consequence of true sentences must be true.” [55, p. 417] The formality of Tarskian consequences can also be proven. Tarski's definition of logical consequence had a key role in the development of the model-theoretic semantics of modern logic and has stayed at its center ever since.

In his 1936 paper, On the Concept of Logical Consequence, Tarski introduced the celebrated definition of logical consequence: “The sentenceσ follows logically from the sentences of the class Γ if and only if every model of the class Γ is also a model of the sentence σ.” [55, p. 417] This definition, Tarski said, is based on two very basic intuitions, “essential for the proper concept of consequence” [55, p. 415] and reflecting common linguistic usage: “Consider any class Γ of sentences and a sentence which follows from the sentences of this class. From an intuitive standpoint it can never happen that both the class Γ consists only of true sentences and the sentence σ is false. Moreover, … we are concerned here with the concept of logical, i.e., formal, consequence.” [55, p. 414] Tarski believed his definition of logical consequence captured the intuitive notion: “It seems to me that everyone who understands the content of the above definition must admit that it agrees quite well with common usage. … In particular, it can be proved, on the basis of this definition, that every consequence of true sentences must be true.” [55, p. 417] The formality of Tarskian consequences can also be proven. Tarski's definition of logical consequence had a key role in the development of the model-theoretic semantics of modern logic and has stayed at its center ever since.