Hacker News Reader

Does that mean that “finite” is not well defined? That would be very odd.

In first order logic this is correct, "finite" is not uniquely defined. Usually finite is defined in terms of natural numbers, but since natural numbers are not uniquely defined then it follows that finite is also not uniquely defined. Every model has its own interpretation of what it means to be finite, and in the model {0, 1, 2, ..., Q - 1, Q, Q + 1, ...}, Q is finite relative to that model.

In first order logic it's impossible to uniquely define any property that would also uniquely define the natural numbers.

From a sibling comment, it seems that using second-order logic resolves this. I'm comfortable saying that if you want to stick to first-order logic then you can say that BB(748) has different values depending on the model in some sense, but that the "real" BB function is defined using what we normally think of as the counting numbers as you'd define with second-order logic, and that's the value that's actually correct.

No second order logic does not resolve this, it actually makes the situation significantly worse since there is no effective proof system in second order logic. Second order logic is studied for its philosophical properties, as a way to understand the limits of logic and the relationship between syntax and semantics, but it's not used for the study of formal mathematics since it lacks an effective proof system.

What second order logic does let you do is deal with only one single model, called the categorical model. So instead of having a theory that has a whole bunch of different models including the actual natural numbers along with undesirable models that contain infinitely large values... you can force your theory to have one single model, no more "It's true in this model, but it's false in that other nonstandard model that's getting in the way." So yes in a particular theory of second order logic BB(748) has one single value because there is only one single model.

So problem solved right? Not even close... because that one single categorical model being used to represent the natural numbers may not be the actual natural numbers, the intended natural numbers where every number is actually finite. Having one single categorical model does not imply working with the actual model you intended to work with. Depending on your choice of second order theory you may be operating within a theory where the single categorical model is indeed unbeknownst to you {0, 1, 2, 3, ..., Q - 1, Q, Q + 1, ...} and hence BB(748) is equal to Q and you'll have no way of knowing this before hand since you lack an effective proof system.

That sounds to me like "your model might not be what you want it to be and it might define an infinite value for BB(748)," not "BB(748) has different values depending on the model."

BB(748) has a single value. It is a finite number of steps (N) of some specific Turing machine. ZFC can't prove neither BB(748)=N, nor ~(BB(748)=N). But BB(748)=N is true and ~(BB(748)=N) is false anyway. The end.

Ultimately, I am addressing the original point that was made:

>I think the more correct statement is that there are different models of ZFC in which BB(748) are different numbers.

You asked how this was possible and that's the specific question that I am addressing. As I mentioned elsewhere, to fully appreciate this answer requires parsing some very subtle and nuanced details that simply can not be glossed over or dismissed, if you genuinely want to know how it's possible that ZFC can be consistent even though different models give different values of BB(748).

If you want to argue something else, about what model is correct or what model is incorrect, that's a perfectly fine argument to have but it's more in the realm of philosophy than it is in the realm of formal mathematics.

If we just use the successor function, so 0 is a natural number, and if n is a natural number then so is S(n). That should be enough to count steps of a halting Turing machine.

How could such a definition give rise to such a set with Q in it?

You're right... with a catch.

What you described doesn't rule out {0,1,2... Q-1,Q,Q+1...}, because you only defined how to yield new natural number, but not exclude things that are not yielded that way from N (the set of all natural numbers).

Now, our intuition is to add this missing part into our axioms, right?

So instead:

> 0 is a natural number, and if n is a natural number then so is S(n)

We say:

> For any X⊆N, if 0 ∈ X, and for every n ∈ X, S(n) ∈ X, then X=N.

This is a perfect valid axiom. And it does rule out the nonstandard shit: for a set N' that looks like {0,1,2... Q-1,Q,Q+1...}, we can get X = {0,1,2...}, which is a subset of N'. According to this axiom, if N'=N then X=N', but it clearly doesn't because Q∈X while ~(Q∈N'). Therefore, N' isn't N.

However, this axiom is not included in the commonly accepted Peano Arithmetic! The reason is that this uses second-order logic, and Peano Arithmetic is a first-order theory.

The above axiom effectively defines a predicate, f(X), which accepts a set as input and returns whether the set is N. This is second-order logic.

Peano Arithmetic, being first-order logic, doesn't have such predicate. This is why we can't rule out these nonstandard {0,1,2... Q-1,Q,Q+1...}.

When it comes to ZFC, it's more complicate as in ZFC, 'natural numbers' are ordinals of sets. But ZFC is written in first-order logic as well, and it's known that an axiomatic system written in first-order logic will have nonstandard models. Even if you can rule out {0,1,2... Q-1,Q,Q+1...} by defining PA in ZFC in some unusual way or adding new axioms to ZFC, as long as it's still a first-order theory, it will have 0 (if inconsistent) or multiple (if consistent) models[0].

[0]: https://en.wikipedia.org/wiki/L%C3%B6wenheim%E2%80%93Skolem_...

"This is a perfect valid axiom. And it does rule out the nonstandard shit"

But the other commenter said:

"Yes, between you and me we know that BB(n) needs to be a natural number, but we have no way to formally and uniquely define what natural numbers are. The best we can do is come up with a formal definition of natural numbers that includes the actual natural numbers but will also include other number systems that contain mathematical objects that are infinitely big and hence are not actual natural numbers."

Is there some subtlety that allows both of these statements to be true, or is this just a contradiction? Was the other commenter implicitly assuming "unless you involve second-order logic"?

I think your contribution to this discussion has been very thorough but I need to nitpick some details:

>For any X⊆N, if 0 ∈ X, and for every n ∈ X, S(n) ∈ X, then X=N.

You're right that this is a perfectly valid axiom in SOL, but it's not true that it rules out non-standard "shit". What this axiom does is it forces your theory to have a single model, the categorical model. But this axiom does not in anyway pick out the standard model as the categorical model, it doesn't force the categorical model to be the standard model. It's possible that N = {0, 1, 2, ..., Q - 1, Q, Q + 1, ...} in which case the categorical model ends up being nonstandard. This axiom has no way to force N to be intended standard model.

> a model where BB(748) = Q is not the actual BB, it's some other function

What it means specifically? ZFC+~(BB(748)=N) allows to extend definition of the Turing machine to a non-standard number of steps?

Can "BB(748) is undefined" be a provable theorem in ZFC+~(BB(748)=N) instead?

While we know that ZFC+~(BB(748)=N) is consistent, we don't know whether \exist Q!=N where ZFC+(BB(748)=Q) is consistent.

Intuitively I see it as: by adding axiom ~(BB(748)=N), we codify that this formal system isn't powerful enough to describe a Turing machine with 748 states (and probably all the machines with number of states greater than 748).

It seems to be even easier: BB codomain is a set of standard natural numbers regardless of which model of ZFS we are using. Therefore BB(748)=Q is false for every non-standard natural number Q.

We can come up with some function BB' that admits that, but it's just a different function.

It seems we can't even define a function with standard domain and non-standard codomain while not using literals for non-standard numbers in its definition.

That is ~(BB(748)=ActualValueOfBB748) is false even if it can't be proven in ZFC. In a sense, busy beaver creates its own mathematical reality.