4 ms·

1. I'm studying set theory, and finite is quite rigidly defined (albeit there's multiple definitions, which require the axiom of choice to prove identical.) We

by ikeboy 11y ago

1. I'm studying set theory, and finite is quite rigidly defined (albeit there's multiple definitions, which require the axiom of choice to prove identical.) We can define natural number as an ordinal that's well ordered by its element relation and the reverse of the element relation (all those terms are defined). Or just as a finite ordinal, in the sense of not being equipollent to any strict subset. Or as the ordinals not containing any limit ordinals or being a limit ordinal. 2. This should probably be thought of as the machine doesn't halt, but in some models, we can "prove" that it halts and has any result. This is kind of like how you can rearrange the terms of some series to sum to any number. https://en.wikipedia.org/wiki/Riemann_series_theorem https://en.wikipedia.org/wiki/Riemann_series_theorem (I wonder if there's a way to get the computability result from this result by some clever isomorphism.) Edit: fixed definition and added another one.

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 ago
  Can 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 ago
    Yes, 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 ago
      Can you express the notion of nonstandardsness within the language (and so add the axiom "no natural numbers are non standard")?
      - danharaj 11y ago
        Not in first order logic.
        wolfgke 11y ago
        Why doesn't one simply use higher order logic to solve this problem? (serious question, I'm a mathematician, but not a set theorist).
leni536 11y ago
>finite is rigidly defined Set theory have infinite number of models, each model having different kind of "finite" ordinals.
emblem21 11y ago
Godel's incompleteness will explain some of the problems of finite regarding set theory.
ikeboy 11y ago
After considering the responses, I declare the analogue of Hofstadter's law: foundations of math are always weirder than you give them credit for, even after you've taken Hofstadter's law into account.
- cousin_it 11y ago
  Most of the weirdness comes from Godel's and Lob's theorems, and they don't seem that strange to me anymore. Here's a little tidbit that might make you more at peace with what's happening. Imagine that you didn't know anything about Godel's results. If you found some theory that proved its own consistency, would that be a reason to trust that theory more? Not at all! Inconsistent theories also happily prove their own consistency (because they prove all sentences). So it seems like Godel's theorems are thwarting a desire that was wrong-headed to begin with.
  - ikeboy 11y ago
    I'm not worried about the inconsistencies. I'm worried that we can't even define natural number and be sure that there's no infinite natural number.

by ikeboy 11y ago

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 ago
Can 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 ago
  Yes, 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 ago
    Can you express the notion of nonstandardsness within the language (and so add the axiom "no natural numbers are non standard")?
    - danharaj 11y ago
      Not in first order logic.
      - wolfgke 11y ago
        Why doesn't one simply use higher order logic to solve this problem? (serious question, I'm a mathematician, but not a set theorist).

leni536 11y ago

>finite is rigidly defined Set theory have infinite number of models, each model having different kind of "finite" ordinals.

emblem21 11y ago

Godel's incompleteness will explain some of the problems of finite regarding set theory.

ikeboy 11y ago

After considering the responses, I declare the analogue of Hofstadter's law: foundations of math are always weirder than you give them credit for, even after you've taken Hofstadter's law into account.

cousin_it 11y ago
Most of the weirdness comes from Godel's and Lob's theorems, and they don't seem that strange to me anymore. Here's a little tidbit that might make you more at peace with what's happening. Imagine that you didn't know anything about Godel's results. If you found some theory that proved its own consistency, would that be a reason to trust that theory more? Not at all! Inconsistent theories also happily prove their own consistency (because they prove all sentences). So it seems like Godel's theorems are thwarting a desire that was wrong-headed to begin with.
- ikeboy 11y ago
  I'm not worried about the inconsistencies. I'm worried that we can't even define natural number and be sure that there's no infinite natural number.