Hacker News Reader

Comment by hackandthink | Hacker News Reader

"Categoricity is central to structuralism because it shows that the essence of our familiar mathematical domains, including ℕ, ℤ, ℚ, ℝ, ℂ, and so on, are determined by structural features that we can identify and express."

I do not buy this. I feel it is the other way around. Structural Features are essential. Categoricity may be nice to have but why should I care so much about it?

View on HN

I think you are onto something. Study mathematical objects and relations among these objects, without bringing in Categoricity. That's what Structuralism in Philosophy of Sciences is: "In the philosophy of science, structuralism[α] (also known as scientific structuralism or as the structuralistic theory-concept) asserts that all aspects of reality are best understood in terms of empirical scientific constructs of entities and their relations, rather than in terms of concrete entities in themselves" [1]

[1] https://en.wikipedia.org/wiki/Structuralism_(philosophy_of_s...

The fact that Peano Arithmetic isn't categorical, and that if you want to nail it down you need either bigger theories (within which you can of course nail down a single model) or move to theories which don't have proof theories like second order arithmetic, suggests all might not be as easy as it looks here.

Being an ex-proof theorist, I'm a bit dubious of not having one.

What does it mean that Peano Arithmetic isn't categorical?

Pure terminology. In some areas "Peano Arithmetic" is short for "first-order Peano arithmetic". In first-order logic, Peano's induction axiom can't be properly formalized, which means the resulting theory isn't categorical. For other people "Peano arithmetic" just describes the usual Peano axioms in natural language, which includes the proper induction axiom. Which can only be formalized by using at least second-order logic. That theory is categorical.

It has (lots of) non-standard models. Or, to put it another way, there are statements that can neither be proved or disproved. This extends to any theory containing "enough" arithmetic and certainly any containing Peano Arithmetic. So ZF set theory is also incomplete in that sense.

You can "solve" this in Second Order logic, because you have a more powerful induction axiom, but how exactly you define that logic is tricky. There's no proof system that defines it completely, so you have to do this via a semantics that relies on knowing which models are or are not OK.

I don't think it solves the problem that you can't define all the "truths" (as most logicians would put it) of Peano Arithmetic.

The quote says why you should care about it. Without categoricity the axioms of a theory don't define a specific structure.

So what? We can still only prove those theorems that also hold in all of those other structures that we don't mean, but sweep up anyway.

It's not clear what "the structure we mean" means without a way of definitely identifying it in our mind. Categorical axioms just make this explicit.

Yes, that's true. I think it is good to have a logic with a semantics which allows you to clearly say what the "standard models" are. For those models categoricity should be achievable. But at the same time it is also clear that there will always be other models, for which categoricity doesn't hold.

Categoricity isn't a property of a model, it's a property of a set of axioms which only have "one model up to isomorphism", or one "structure" in the sense of structuralism.

As commonly defined, you are right, but if you have the ability to select among your models, then you can use that to sharpen your notion of categoricity by considering only a certain class of models instead of all models.

You can say for example, categorical with respect to a certain cardinality of the model, that is you are only considering models of that cardinality.

And just like that, if your semantic allows it, you can also say categorical with respect to standard models. But for that you of course need a clear definition of what "standard" means. First-order logic doesn't provide such a clear definition.

Categories are the main and most developed tool building around relations that are the building blocks of structure.

Reply on news.ycombinator.com