6
$\begingroup$

I asked this question in Philosophy.StackExchange whilst trying to get to grips on Badious declared philosophy on using mathematics as ontology. But was advised to ask it here because of the mathematical content.

Can arithmetic when codified by the first-order Peano Axioms recreate the transinfinite (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.

But if you can only take subsets of the integers, then although you can construct the reals (by identifying them with certain subsets of the naturals), you won't be able to take subsets of them - which will stop one from building bigger sets. But on the other hand you can always generalise then to 3rd-order arithmetic and so on.

However, in the SEP entry on higher-order logic they say that:

'there is a sense in which the power-set operation is definable in second-order logic'

and

'This second-order expressibility of the power-set operation permits the simulation of higher-order logic within second order'.

So maybe you don't have to walk up the ladder of n-PA but only simulate it in 2-PA.

$\endgroup$
7
$\begingroup$

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 $\emptyset$ has no members. The set $\{\emptyset\}$ 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 $\emptyset$. In general a countable set $\{a_n\}$ is coded by a well founded tree whose root has one child $c_n$ for each $a_n$, such that the tree below $c_n$ is a code for $a_n$ 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.

$\endgroup$
3
$\begingroup$

If "recreating the transfinite hierarchy of ZFC" entails interpreting ZFC, then the answer is no, this is not possible. If PA were to interpret ZFC then ZFC would be consistent relative to PA, but the consistency strength of ZFC is strictly higher. The same goes for the full theory of $(n+1)$-st order arithmetic as well: ZFC proves that it has a model, namely $(V_{\omega+n}; \in)$, so if ZFC could be interpreted in this theory then it would prove its own consistency, violating Gödel's second incompleteness theorem.

$\endgroup$
  • $\begingroup$ I can see that interpretation would lead to violations of incompleteness; so encoding the whole of ZFC in PA can't work. But certainly one can encode some fragment of ZFC - specifically that part of ZFC that specifically gives you PA! $\endgroup$ – Mozibur Ullah Mar 8 '13 at 12:51
  • $\begingroup$ @MoziburUllah True, but if you want to go very far beyond PA you will probably want the axioms of Infinity and Power Set. And those axioms (together with pairing etc.) are already enough to prove the consistency of $n$-th order arithmetic for any finite $n$. $\endgroup$ – Trevor Wilson Mar 9 '13 at 5:27

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.