The disruption -- Capital assembled -- Capital goes to work -- Capital goes to market -- Capital evolves -- The geography of it all -- Creative destruction on the land -- What is to be done? And who is going to do it?

We define a class of functions, the descent recursive functions, relative to an arbitrary elementary recursive system of ordinal notations. By means of these functions, we provide a general technique for measuring the proof-theoretic strength of a variety of systems of first-order arithmetic. We characterize the provable well-orderings and provably recursive functions of these systems, and derive various conservation and equiconsistency results.

The notion of interpretation is absolutely fundamental to mathematical logic and the foundations of mathematics. It is also crucial for the foundations and philosophy of science - although here some crucial conditions generally need to be imposed; e.g., “the interpretation leaves the mathematical concepts unchanged”.

We now fix A ⊆ Q. We study a fundamental class of digraphs associated with A, which we call the A-digraphs. An A,kdigraph is a digraph (Ak,E), where E is an order invariant subset of A2k in the following sense. For all x,y ∈ A2k, if x,y have the same order type then x ∈ E ↔ y ∈ E.

The kind of unknowability I will discuss concerns the count of certain natural finite sets of objects. Even the situation with regard to our present strong formal systems is rather unclear. One can just profitably focus on that, putting aside issues of general unknowability.

Equational Boolean Relation Theory concerns the Boolean equations between sets and their forward images under multivariate functions. We study a particular instance of equational BRT involving two multivariate functions on the natural numbers and three infinite sets of natural numbers. We prove this instance from certain large cardinal axioms going far beyond the usual axioms of mathematics as formalized by ZFC. We show that this particular instance cannot be proved in ZFC, even with the addition of slightly weaker large cardinal (...) axioms, assuming the latter are consistent. (shrink)

The Borel reducibility theory of Polish equivalence relations, at least in its present form, was initiated independently in [FS89] and [HKL90]. There is now an extensive literature on this topic, including fundamental work on the Glimm-Effros dichotomy in [HKL90], on countable Borel equivalence relations in [DJK94], and on Polish group actions in [BK96].

“Sentential reflection” in the sense of [Fr03] is based on reflecting down from a category of classes. “Elemental sentential reflection” is based on reflecting down from a category of elemental classes. We present various forms of elemental sentential reflection, which are shown to interpret and be interpretable in certain set theories with large cardinal axioms.

We give a detailed extended abstract reflecting what we know about Boolean relation theory. We follow this by a proof sketch of the main instances of Boolean relation theory, from Mahlo cardinals of finite order, starting at section 19. The proof sketch has been used in lectures.

There are two kinds of such limiting results that must be carefully distinguished. Results of the first kind state the nonexistence of any algorithm for determining whether any statement among a given set of statements is true or false.

We present some examples of mathematically natural nonrecursive sets of integers and relations on integers by combining results from Part 1, recursion theory, and from the negative solution to Hilbert’s 10th Problem ([3], [1], and [2]).

An unprovable theorem is a mathematical result that can-not be proved using the com-monly accepted axioms for mathematics (Zermelo-Frankel plus the axiom of choice), but can be proved by using the higher infinities known as large cardinals. Large car-dinal axioms have been the main proposal for new axioms originating with Gödel.

It has been accepted since the early part of the Century that there is no problem formalizing mathematics in standard formal systems of axiomatic set theory. Most people feel that they know as much as they ever want to know about how one can reduce natural numbers, integers, rationals, reals, and complex numbers to sets, and prove all of their basic properties. Furthermore, that this can continue through more and more complicated material, and that there is never a real problem.

We present some formal systems in the language of linearly ordered rings with finite sets whose nonlogical axioms are strictly mathematical, which correspond to polynomially bounded arithmetic. With an additional strictly mathematical axiom, the systems correspond to exponentially bounded arithmetic.

We present a way out of Russell’s paradox for sets in the form of a direct weakening of the usual inconsistent full comprehension axiom scheme, which, with no additional axioms, interprets ZFC. In fact, the resulting axiomatic theory 1) is a subsystem of ZFC + “there exists arbitrarily large subtle cardinals”, and 2) is mutually interpretable with ZFC + the scheme of subtlety.

We axiomatize EFA in strictly mathematical terms, involving only the ring operations, without extending the language by either exponentiation, finite sets of integers, or polynomials.

A bi-infinite approximate fixed point of type (n,k) is an approximate fixed point of type (n,k) whose terms are biinfinite; i.e., contain infin-itely many positive and infinitely many negative elements.

We can equivalently present this by the recursion equations f1(n) = 2n, fk+1(1) = fk(1), fk+1(n+1) = fk(fk+1(n)), where k,n ≥ 1. We define A(k,n) = fk(n).

We discuss several axiomatizations of set theory in first order predicate calculus with epsilon and a constant symbol W, starting with the simple system K(W) which has a strong equivalence with ZF without Foundation. The other systems correspond to various extensions of ZF by certain large cardinal hypotheses. These axiomatizations are unusually simple and uncluttered, and are highly suggestive of underlying philosophical principles that generate higher set theory.

A number of comparability theorems have been investigated from the viewpoint of reverse mathematics. Among these are various comparability theorems between countable well orderings ([2],[8]), and between closed sets in metric spaces ([3],[5]). Here we investigate the reverse mathematics of a comparability theorem for countable metric spaces, countable linear orderings, and sets of rationals. The previous work on closed sets used a strengthened notion of continuous embedding. The usual weaker notion of continuous embedding is used here. As a byproduct, we (...) sharpen previous results of [3],[5]. (shrink)

This is an introduction to the most primitive form of the new Boolean relation theory, where we work with only one function and one set. We give eight complete classifications. The thin set theorem (along with a slight variant), and the complementation theorem are the only substantial cases that arise in these classifications.

Informal statements of Gödel's Second Incompleteness Theorem, referred to here as Informal Second Incompleteness, are simple and dramatic. However, current versions of Formal Second Incompleteness are complicated and awkward. We present new versions of Formal Second Incompleteness that are simple, and informally imply Informal Second Incompleteness. These results rest on the isolation of simple formal properties shared by consistency statements. Here we do not address any issues concerning proofs of Second Incompleteness.

A lot of the well known impact of the Gödel phenomena is in the form of painful messages telling us that certain major mathematical programs cannot be completed as intended. This aspect of Gödel – the delivery of bad news –is not welcomed, and defensive measures are now in place.

It turns out, time and time again, in order to make serious progress in f.o.m., we need to take actual reasoning and actual development into account at precisely the proper level. If we take these into account too much, then we are faced with information that is just too difficult to create an exact science around - at least at a given state of development of f.o.m. And if we take these into account too little, our findings will not have (...) the relevance to mathematical practice that could be achieved. (shrink)

Mathematical statements arising from program verification are believed to be much easier to deal with than statements coming from serious mathematics. At least this is true for “normal programming”.

This is an immediate conse-quence of a more general combinatorial theorem called Ramsey’s theorem, but it is much simpler to state. We call this adjacent Ramsey theory.

1. Transfer principles from N to On. A. Mahlo cardinals. B. Weakly compact cardinals. C. Ineffable cardinals. D. Ramsey cardinals. E. Ineffably Ramsey cardinals. F. Subtle cardinals. G. From N to (...) 4. Decidability of statements on N. 5. Decidability of statements on shrink)

Gödel's definitive results and his essays leave us with a rich legacy of philosophical programs that promise to be subject to mathematical treatment. After surveying some of these, we focus attention on the program of circumventing his demonstrated impossibility of a consistency proof for mathematics by means of extramathematical concepts.

We present a range of mathematical theorems whose proofs require unexpectedly strong logical methods, which in some cases go well beyond the usual axioms for mathematics.

Russell’s way out of his paradox via the impredicative theory of types has roughly the same logical power as Zermelo set theory - which supplanted it as a far more flexible and workable axiomatic foundation for mathematics. We discuss some new formalisms that are conceptually close to Russell, yet simpler, and have the same logical power as higher set theory - as represented by the far more powerful Zermelo-Frankel set theory and beyond. END.

I. WKL0 is a conservative extension of PRA for ’-0-2 sentences. II. ACA0 is a conservative extension of PA for arithmetic sentences. III. ATR0 is a conservative extension of IR for arithmetic sentences. IV. ’-1-1-CA0 is a conservative extension of ID(

Areas of Mathematics in Philosophy of Mathematics

 

Export citation  

 

Bookmark  

The main powerful method for establishing termination of term rewriting systems was discovered by Nachum Dershowitz through the introduction of certain natural well founded orderings (lexicographic path orderings). This leads to natural decision problems which may be of the highest computational complexity of any decidable problems appearing in a natural established computer science context.

This topic has been discussed earlier on the FOM email list in various guises. The common theme is: big numbers and long sequences associated with mathematical objects. See..

S. Adams, W. Ambrose, A. Andretta, H. Becker, R. Camerlo, C. Champetier, J.P.R. Christensen, D.E. Cohen, A. Connes. C. Dellacherie, R. Dougherty, R.H. Farrell, F. Feldman, A. Furman, D. Gaboriau, S. Gao, V. Ya. Golodets, P. Hahn, P. de la Harpe, G. Hjorth, S. Jackson, S. Kahane, A.S. Kechris, A. Louveau,, R. Lyons, P.-A. Meyer, C.C. Moore, M.G. Nadkarni, C. Nebbia, A.L.T. Patterson, U. Krengel, A.J. Kuntz, J.-P. Serre, S.D. Sinel'shchikov, T. Slaman, Solecki, R. Spatzier, J. Steel, D. Sullivan, S. (...) Thomas, A. Valette, V.S. Varadarajan, B. Velickovic, B. Weiss, J.D.M. Wright, R.J. Zimmer. (shrink)

The classical Ulm theory provides a complete set of invariants for countable abelian p-groups, and hence also for countable torsion abelian groups. These invariants involve countable ordinals. One can read off many simple structural properties of such groups directly from the Ulm theory. We carry out a reverse mathematics analysis of several such properties. In many cases, we reverse to ATR0, thereby demonstrating a kind of necessary use of Ulm theory.

Provide a formal system that is a conservative extension of PA for Π02 sentences, and even a conservative extension of HA, that supports the worry free smooth development of constructive analysis in the style of Errett Bishop.

BRT is always based on a choice of BRT setting. A BRT setting is a pair (V,K), where V is an interesting family of multivariate functions. K is an interesting family of sets. In this talk, we will only consider V,K, where V is an interesting family of multivariate functions from N into N. K is an interesting family of subsets of N.

Gödel's legacy is still very much in evidence. We will not attempt to properly discuss the full impact of his work and all of the ongoing important research programs that it suggests. This would require a book length manuscript. Indeed, there are several books discussing the Gödel legacy from many points of view, including, for example, (Wang 1987, 1996), (Dawson 2005), and the historically comprehensive five volume set (Gödel 1986-2003).

We focus on two formal methods contexts which generate investigations into decision problems for finite strings.

An o-minimal structure is any relational structure in any relational type in the first order predicate calculus with equality, where one symbol is reserved to be a dense linear ordering without endpoints, satisfying the following condition: that every first order definable subset of the domain is a finite union of intervals whose endpoints are in the domain or are ±•. First order definability always allows any parameters, unless explicitly indicated otherwise.

For digraphs G, we write V(G) for the set of all vertices of G, and E(G) for the set of all edges of G. A digraph on a set E is a digraph G where V(G) = E.

(1984). Gender Differences in Subject Preference and Perception of Subject Importance among Third Year Secondary School Pupils in Single‐sex and Mixed Comprehensive Schools. Educational Studies: Vol. 10, No. 3, pp. 243-253.

NOTE: This is an expanded version of my lecture at the special session on reverse mathematics, delivered at the Special Session on Reverse Mathematics held at the Atlanta AMS meeting, on January 6, 2005.

This distinction between logic and mathematics is subject to various criticisms and can be given various defenses. Nevertheless, the division seems natural enough and is commonly adopted in presentations of the standard foundations for mathematics.

We show the algorithmic unsolvability of a number of decision procedures in ordinary two dimensional Euclidean geometry, involving lines and integer points. We also consider formulations involving integral domains of characteristic 0, and ordered rings. The main tool is the solution to Hilbert's Tenth Problem. The limited number of facts used from recursion theory are isolated at the beginning.

An extreme kind of logic skeptic claims that "the present formal systems used for the foundations of mathematics are artificially strong, thereby causing unnecessary headaches such as the Gödel incompleteness phenomena". The skeptic continues by claiming that "logician's systems always contain overly general assertions, and/or assertions about overly general notions, that are not used in any significant way in normal mathematics. For example, induction for all statements, or even all statements of certain restricted forms, is far too general - mathematicians (...) only use induction for natural statements that actually arise. If logicians would tailor their formal systems to conform to the naturalness of normal mathematics, then various logical difficulties would disappear, and the story of the foundations of mathematics would look radically different than it does today. In particular, it should be possible to give a convincing model of actual mathematical practice that can be proved to be free of contradiction using methods that lie within what Hilbert had in mind in connection with his program”. Here we present some specific results in the direction of refuting this point of view, and introduce the Strict Reverse Mathematics (SRM) program. (shrink)