2
$\begingroup$

I am in the middle of my PhD and I am trying to reinforce my knowledge of mathematics by studying the foundations of Analysis. The first task is to get the bases of the natural numbers. So for this I chose the ZFC axioms which gives the consistence of the PA axioms. My first question is related to completeness.
1) Does the incompleteness of PA imply the incompleteness of PA with the second-order induction axiom? (Considering that the incompleteness theorem only refers to PA in the first order version.) I really like the PA with the second-order induction axiom because it is categorical and allow us to define sum, multiplication and exponentiation.

2)It seems that once we have defined the natural numbers using ZFC and PA we can build integers, rationals, real and complex numbers without any other axiom. ¿or not?

3)For the foundations of topology and vector spaces, what kind of axioms do we need?

$\endgroup$
  • $\begingroup$ How could a categorical theory be incomplete? No, the incompleteness theorem is specific to 1st order theories. Not clear what you mean by "construction" in 2). If you mean, "beyond the axioms of $\mathsf{ZFC}$}, sure, but I suspect you mean that the only role of $\mathsf{ZFC}$ is to give us a model of $\mathsf{PA}$, and that the rest can be done internally within $\mathsf{PA}$. You probably need to clarify, as this seems to be mixing things up. Certainly, only a very weak theory beyond $\mathsf{PA}$ (and much weaker than $\mathsf{ZFC}$) allows us to formalize the construction of $\mathbb C$. $\endgroup$ – Andrés E. Caicedo Dec 24 '13 at 6:50
  • $\begingroup$ By categorical I mean that if $(\mathbb{N}_{1},0_{1},S_1)$ and $(\mathbb{N}_{2},0_{2},S_2)$ are systems satisfying PA (second order) then they are isomorphic. Are you saying that this guarantee the completeness of PA (second order)? In 2) if I assume ZFC we can define the natural numbers. Then we can define integers by $\{(m,n):m,n\in\mathbb{N}\}$ under the equivalence relation $(m,n)\sim(a,b)$ iff $m+b=a+n$. Then we can define $\mathbb{Q}$ in a similar way and so on. All this process without assuming any other axiom (if that is possible). $\endgroup$ – Chilote Dec 24 '13 at 7:13
  • $\begingroup$ oh! by construct I meant build. Sorry for my English. $\endgroup$ – Chilote Dec 24 '13 at 7:36
  • 1
    $\begingroup$ For the answers to the second and third question, this has been studied in great depth in Reverse Mathematics. But the short answer is that PA alone, or its conservative second-order extension $\mathsf{ACA}_0$, is sufficient for the bulk of standard undergraduate theorems about complete metric spaces and vector spaces. Topology, being more set-theoretic, is a more difficult problem, but many theorems of topology can be formalized in second-order arithmetic. $\endgroup$ – Carl Mummert Dec 24 '13 at 13:50
  • 2
    $\begingroup$ Due the number of so-called ZF "junk" theorems (e.g. stuff like $4\subset 33$ and $0^0=1$(?)), the Peano axioms themselves (with 2nd induction) may be a better starting point than the ZF axiom of infinity. See: mathoverflow.net/questions/90820/… and math.stackexchange.com/questions/604257/… $\endgroup$ – Dan Christensen Dec 26 '13 at 22:17
4
$\begingroup$

There is an important distinction to make. The second-order induction axiom is just that - an axiom. It can be interpreted in several ways.

In normal second-order arithmetic, $Z_2$, we do have the usual second-order induction axiom $$ (\forall X)\big [(0 \in X \land (\forall n)[n \in X \to n+1\in X]) \to (\forall n)[n \in X]\big ] $$ But $Z_2$ is usually studied with first-order semantics, and in that context it is an effective theory of arithmetic subject to the incompleteness theorems. In particular, $Z_2$ includes every axiom of PA, and it does include the second-order induction axiom, and it is still incomplete.

Therefore, the well-known categoricity proof must not rely solely on the second-order induction axiom. It also relies on a change to an entirely different semantics, apart from the choice of axioms. It is only in the context of these special "full" semantics that PA with the second-order induction axiom becomes categorical.

Now, if we fix a sound deductive system for $Z_2$, the change of semantics has no effect whatsoever on the formulas that are provable. So, even though $Z_2$ with full second-order semantics is categorical, for any sound effective deductive system there are still true formulas of $Z_2$ that are neither provable nor disprovable in that system.

This answers a question in the comments, "How can a categorical theory be incomplete?" The answer is that categoricity is determined both by the choice of axioms and the choice of semantics, while completeness in this sense is determined by the axioms and the choice of a deductive system. (Here "complete" means that the set of provable theorems is a maximal consistent set.) There is no reason why, in a general setting, categoricity should imply completeness. In fact, it doesn't.

No matter what semantics we wish to use, it is simply impossible - by the incompleteness theorems - to come up with any effective deductive system that extends PA and is complete in the sense of the previous paragraph. Moving to higher-order systems helps us prove additional true propositions about the natural numbers, but we can never find a deductive system to prove all of them.

$\endgroup$
2
$\begingroup$

You can find the answer to your question 1) in an "An Introduction to Godel's Theorems" by Peter Smith. It should be in chapter 17 or 21, depending on your edition (check the index for induction axiom).

For 2), you need some sort of equivalence class structure in your semantics in order to define the rational numbers in a rigorous way. Are you interested in the minimal axioms you need in order to generate a maximally complex arithmetical structure? If so, you may be interested in the arithmetical hierarchy and related topics.

For 3), there are interesting characterizations of topological spaces with modal semantics (using possibility and necessity operators to define closed and open conditions). Refer to Johan van Benthem's "Modal Logic for Open Minds" which has a chapter on defining topology with modal logic, and there are related topics concerning linear spaces, linear logics, etc.

$\endgroup$
  • 1
    $\begingroup$ The arithmetical hierarchy is not going to take us to $\mathbb R$. The right setting is subsystems of second order arithmetic. $\endgroup$ – Andrés E. Caicedo Dec 24 '13 at 6:56
  • 2
    $\begingroup$ Your answer to 3) is really not an answer, as you are changing the context. The question is, starting with the existence of $\mathbb N$, what set existence axioms are needed beyond those required to establish the existence of $\mathbb C$, if we want to develop basic topology and linear algebra (and, presumably, classical functional analysis and measure theory). $\endgroup$ – Andrés E. Caicedo Dec 24 '13 at 6:59
  • $\begingroup$ @AndresCaicedo: Thanks for the additional comments! I knew my answer was very incomplete. $\endgroup$ – Samuel Reid Dec 25 '13 at 9:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.