Hacker News Reader

Comment by cubefox | Hacker News Reader

At the moment I don't remember enough of the axiom of choice to comment on it in detail, but we can infer from the Downward Löwenheim-Skolem theorem (roughly, every first-order theory, including ZFC, has a countable model) that the Choice axiom can't imply uncountable sets.

View on HN

Admittedly I know nothing about the theorem you’re referring to, but is there a compelling reason to limit ourselves to first-order logic?

The main reason people like first-order logic is Gödel's completeness theorem. It says that for first-order logic there is a proof system such that it proves a sentence if and only if it is true in every model. That is, the proof system is both sound and complete. This doesn't work for second or higher order logic. If we want a second-order proof system to be sound (proves no false things), it must be incomplete, i.e. not prove some true statements.

On the other hand, the main advantage of second (and higher) order logic is that it allows for "categorical" theories. A theory, like second-order Peano arithmetic, is categorical when it only has one model up to isomorphism. For second-order PA this model is the natural numbers. First-order logic doesn't allow categorical theories, so the axiom of first-order PA can't rule out the existence of weird non-standard numbers. Categoricity of a theory means that the axioms of the theory "define" ("pin down") some model. First-order theories can't do that.

So naturally, first-order ZFC isn't categorical. It even allows for countable and uncountable models. It's interpretation (model) is highly indeterminate. However, second-order ZFC (unlike, say, second-order PA or second-order analysis) is also not categorical. It doesn't have a countable model anymore, but it is still has many non-isomorphic models. (Though I think it has some weaker property which means that it is at least "more categorical" in some sense.)

So second-order ZFC doesn't give us the main advantage that second-order logic allows (the possibility of categorical theories), while also not having the complete proof system of first-order logic.

However, we could simply not use ZFC at all and only use second (or rather: higher) order logic. Higher-order logic is powerful on its own to (often categorically) formalize mathematical theories, like PA, without the need of any set theory. Instead of sets we have properties ("being a real number" instead of the set of real numbers), relations, properties of properties etc.

Formal proof checkers like Isabelle actually use higher-order logic instead of first-order ZFC as a basis.

There is also some argument to be made that categoricity is more important than completeness, since completeness of a proof system turns out to be not a plausible property anymore once self-referential statements, like the Gödel sentence, get involved. But that would lead me too far afield, and it isn't the standard opinion, which favors completeness over categoricity.

Reply on news.ycombinator.com