6

Can arithmatic when codified by the first-order Peano Axioms recreate the transfinite (cardinal) hierarchy of Set Theory (ZFC)?

I suspect not, simply because we have no formal means of creating a set - and so we cannot even take the first step to define cardinality.

How about 2nd-order Peano Axioms, I suspect here it can (but am not sure), as in the introduction of the previous article we have:

It is an alternative to axiomatic set theory as a foundation for much, but not all, of mathematics.

(I've labelled this as metaphysics, following Badiou).

Improve this question
14
  • 1
    I suspect not, but just on simple cardinality grounds. If it can't even get you all of real analysis, I can't see how it could go beyond aleph-null in the hierarchy.
    – Dennis
    Commented Mar 8, 2013 at 4:40
  • @Dennis: I'm not sure that analysis is relevant here. Cardinality is about measuring the size of sets by looking at injections between them - and 2nd-order arithmetic allows quantification over sets of numbers. Presumably if the formal language allows you to talk about injections and we can take all subsets of a set of numbers we can get started on the hierarchy.
    – Mozibur Ullah
    Commented Mar 8, 2013 at 4:58
  • 1
    I was taking my cue from the end of section 7 of the linked wiki: "These systems cannot speak of real functions, or subsets of the reals. Nevertheless, continuous real functions are legitimate objects of study, since they are defined by their values on the rationals. Moreover, a related trick makes it possible to speak of open subsets of the reals. Even Borel sets of reals can be coded in the language of second-order arithmetic, although doing so is a bit tricky." My naive assumption was that the limitation here was a matter of cardinality.
    – Dennis
    Commented Mar 8, 2013 at 5:14
  • I realize, though, that it could just be a matter of the expressive power of 2nd order PA.
    – Dennis
    Commented Mar 8, 2013 at 5:14
  • Ch. 5 of this book should be of interest to you. He does say that second order PA can capture a fragment of descriptive set theory, but a quick scan wasn't enough for me to gather exactly how much.
    – Dennis
    Commented Mar 8, 2013 at 5:29

2 Answers 2

Reset to default
3

TL;DR: Assuming the axiom of choice, the answer is No for First Order PA.

Given the axiom of choice, every cardinal can be identified with a unique ordinal. So an easier question is to ask is if the class of ordinal numbers can be represented in PA.

The set of ordinals representable in PA is Kleene's O, the recursive ordinals. This set is bounded above by a limit ordinal ω1CK, which is still countable and thus less than ℵ1. So using recursive ordinals, PA cannot express even the smallest uncountable cardinality.

Improve this answer
3

The answer by Carl Mummert to the same question in math.stackexchange shows that it can in sufficiently rich 2-PA:

We can define an interpretation of set theory into second-order arithmetic. I will skip the details, but one way is to define a "code for a set" to be a certain kind of tree. The general idea is that the root of the tree that codes a set has one child for each element of the set.

For example, the empty set is coded by a tree with only one node, because ∅ has no members. The set {∅} is coded by a tree with two nodes, the root and a single child; the tree for the child is then a one-node tree, which codes ∅. In general a countable set {an} is coded by a well founded tree whose root has one child cn for each an, such that the tree below cn is a code for an for each n.

In this way any countable well-founded model of set theory can be encoded into second-order arithmetic as a single sequence of codes of sets. Of course ZFC "really" has a countable well-founded model, which can be coded via this interpretation into a single set of natural numbers.

On the other hand, none of the usual axiom systems for second-order arithmetic will prove that there is a coded model of ZFC. So it is not the case that the usual theories of second-order arithmetic interpret ZFC in the sense of one theory interpreting another. Instead we have an interpretation that only works in sufficiently rich models of second-order arithmetic.

Once we define this interpretation, it is possible to define all the usual notions of set theory within second-order arithmetic in terms of a coded model M. We can define what it means for one coded set in M to have the same M-cardinality as another coded set in M, what it means for a coded set in M to be cardinal number in M, etc. In this way, we are essentially using second-order arithmetic as a metatheory to study coded models of set theory.

The details of this interpretation are all given in Subsystems of Second-order Arithmetic by Simpson, although the presentation there is somewhat advanced.

Improve this answer

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .