5 ms·
> finite is quite rigidly defined It's a bit more subtle. Wikipedia puts it well: Even for those mathematicians who embrace infinite sets, in certain importan
by cousin_it 11y ago
> finite is quite rigidly defined
It's a bit more subtle. Wikipedia puts it well:
Even for those mathematicians who embrace infinite sets, in certain important contexts, the formal distinction between the finite and the infinite can remain a delicate matter. The difficulty stems from Gödel's incompleteness theorems. One can interpret the theory of hereditarily finite sets within Peano arithmetic (and certainly also vice versa), so the incompleteness of the theory of Peano arithmetic implies that of the theory of hereditarily finite sets. In particular, there exists a plethora of so-called non-standard models of both theories. A seeming paradox, non-standard models of the theory of hereditarily finite sets contain infinite sets - but these infinite sets look finite from within the model. (This can happen when the model lacks the sets or functions necessary to witness the infinitude of these sets.) On account of the incompleteness theorems, no first-order predicate, nor even any recursive scheme of first-order predicates, can characterize the standard part of all such models. So, at least from the point of view of first-order logic, one can only hope to characterize finiteness approximately.
https://en.wikipedia.org/wiki/Finite_set https://en.wikipedia.org/wiki/Finite_set
- ikeboy 11y agoCan you have a model of ZF with natural numbers that aren't just 0,1,2,...? Or only PA? It seemed obvious that defining the natural numbers in the way above results in only such numbers. You can give an intuitive argument that any natural number can be recursively generated from 0 by the successor operator. Is this wrong? Edit: looks like http://www1.cuni.cz/~svejdar/papers/sv_ybk10_p.pdf http://www1.cuni.cz/~svejdar/papers/sv_ybk10_p.pdf says you can get such a model. >A model M of (some) set theory is non-standard if it contains an ordinal α such that M |= “α is finite”, i.e. M |= “α is less than the first limit ordinal”, but looking from outside, the set of all ordinals β < α is infinite. The proof of the existence of non-standard models of set theory is basically the same as for PA.
- cousin_it 11y agoYes, all theories at least as strong as PA (including ZF) have models with nonstandard naturals. Another fun fact is that ZF has a countable model, even though ZF proves that uncountable sets exist. https://en.wikipedia.org/wiki/Skolem%27s_paradox https://en.wikipedia.org/wiki/Skolem%27s_paradox
- ikeboy 11y agoCan you express the notion of nonstandardsness within the language (and so add the axiom "no natural numbers are non standard")?
- danharaj 11y agoNot in first order logic.
- wolfgke 11y agoWhy doesn't one simply use higher order logic to solve this problem? (serious question, I'm a mathematician, but not a set theorist).
- danharaj 11y agoA lot of properties that you'd want in a logic stop holding once you hit second-order logic: https://en.wikipedia.org/wiki/Second-order_logic#Metalogical_results https://en.wikipedia.org/wiki/Second-order_logic#Metalogical...
- John_Baez 11y agoIt turns out this only pushes back the problem. You can write down second-order axioms for arithmetic which have a unique model, but in a model of a second-order theory predicates are interpreted as sets. So, you need to choose a version of set theory, to know what a model actually is. Suppose you choose ZFC (the usual axioms of set theory). Unfortunately this itself has infinitely many models! I explained this in a bit more detail here: https://johncarlosbaez.wordpress.com/2016/04/02/computing-the-uncomputable/#comment-79002 https://johncarlosbaez.wordpress.com/2016/04/02/computing-th...
- wolfgke 11y agoThanks, this looks plausible.
- 11y ago