0
$\begingroup$

In PA one can define the ordered pair function in term of naturals, i.e. the ordered pair of naturals is a natural itself. let's label these ordered pairs as natural ordered pairs.

Now working in second order arithmetic (formalized in first order logic language) can we speak of existence of a well ordering on $N$ that is defined in terms of being a set of natural ordered pairs, that satisfy the so and so.. well ordering conditions?

What confuses me is that this well ordering itself would be a subset of $N$, so it would well order itself by the way, so it would be a kind of auto-well ordering relation? Is that possible?

My attempts to solve this question to the positive relied on seeing that in the finite world a well ordering of a finite set $X$ must be at least of a size equal to $|X|-1 + |X|-2 + |X|-3 + ..+|X|-|X|$. So if $X$ is of $\aleph_0$ cardinality then the well ordering relation can be of $\aleph_0$ cardinality. I think a mapping showing this possibility for well ordering subset $R$ of $N$, is for the first element $\alpha$ of $R$ to code $\langle 0,1 \rangle$, then we jump by taking $\alpha + 2^n$ to represent the successive elements of the form $\langle 0, n \rangle$, etc.., now to represent pairs of the form $\langle 1,n \rangle$ for $n > 1$, we start with $\alpha+1$ and jump similarly by $+2^n$, this way we can have enough room to well order all $N$ including $R$ itself! But I'm not sure if this solves it?

$\endgroup$
3
  • $\begingroup$ Absolutely. This is an essential idea behind ordinal analysis, where you try to characterize the shortest well-ordering that a theory of (usually) second order arithmetic is unable to describe. $\endgroup$ – Malice Vidrine Apr 1 '20 at 11:14
  • $\begingroup$ Why isn't the natural well-ordering of $\mathbb{N}$ in type $\omega$, seen as a subset of $\mathbb{N}$ using your "natural ordered pairs" coding sufficient? Is seems to me that you answered yourself. $\endgroup$ – Jonathan Apr 1 '20 at 14:16
  • $\begingroup$ I mean this is exactly how linear oders (I don't see what is particular of ordinals here) are formalized in second order arithmetic, where a priori we can only talk about subsets of naturals. $\endgroup$ – Jonathan Apr 1 '20 at 14:21
1
$\begingroup$

I'm not quite certain what you're trying to do in your last paragraph, so it may be I've missed some more specific aspect of the question you're trying to answer, but...

Absolutely we can talk about well-orders defined in such a way, and it can be very interesting to do so. To see that it's possible is trivial: if we use the coding $\langle m,n\rangle:=(m+n)^2+m$, it's easy enough in anything at least as strong as $\mathsf{ACA}_0$ (really this is more than we need) to describe the lexicographic ordering on $N\times N$ with natural ordered pairs. It's even possible to prove that it's well-ordered, in the form of proving that every strictly decreasing sequence is finite. Such well-orders are, as you say, always countable, but the way pairs are coded usually means it isn't a well-ordering of all of $N$.

But note that this is an important point: we may be able to describe what is a well-ordering in the "real world", but be unable to prove that it is well-ordered. With some ingenuity one can code a well-ordering of length $\Gamma_0$ in $\mathsf{ACA}_0$ (using a Gödel numbering of ordinals in the Veblen hierarchy) but only initial segments of length less than $\varepsilon_0$ are provably well-ordered.

$\endgroup$
3
  • $\begingroup$ but the idea here is for $R$ to well order the whole of $N$, I mean like for example adding to axioms of second order arithmetic an axiom that states the existence of a well ordering on all N, provided that the elements of that well ordering are naturals, and thereby well ordering itself by the way, that's what the question is about. Can that be possible when we have more than 3 naturals? I mean is it consistent, and how we can define such a well ordering, that's what I was trying to do in my last paragraph. $\endgroup$ – Zuhair Apr 1 '20 at 14:00
  • 2
    $\begingroup$ @Zuhair - There are definable surjective pairing functions on the naturals, sure. And you define the ordering on $N\times N$ (for example) the same way you always would: as $\{\langle \langle x_1,x_2\rangle,\langle y_1,y_2\rangle\rangle\:|\: x_1\leq y_1\vee (x_1=y_1\wedge x_2\leq y_2)\}$. I don't see why this would be a worry. $\endgroup$ – Malice Vidrine Apr 1 '20 at 14:28
  • $\begingroup$ @Yes! You are right. $\endgroup$ – Zuhair Apr 1 '20 at 18:36

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.