2 ms·
> [Trichotomy]'s still present in the current NNG Cool; it wasn't there yet 6 weeks ago: https://news.ycombinator.com/item?id=37880788 https://news.ycombinator
by 082349872349872 3y ago
> [Trichotomy]'s still present in the current NNG
Cool; it wasn't there yet 6 weeks ago: https://news.ycombinator.com/item?id=37880788 https://news.ycombinator.com/item?id=37880788
"pred succ n = n" reminds me a lot of def'ns of the form "(left p, right p) = p"; I'll have to think about that a bit. Injectivity of succ is, I guess, what distinguishes ℕ from similar constructions with different characteristic? (did I just think that, or am I parroting NNG?)
> ∀x.(r(x)→⊥)→r(f(x)) ⟹ ∃x.r(x)∧r(f(f(x)))
I think I gave up on incredible.pm too early (although I did skip ahead for SKI) ... I'll have to go back and try that. It seems to have a bit of the flavour of "all people who claim to be Sir Anthony Charles Lynton Blair KG are liars"
- thaumasiotes 3y agoI've been thinking more about succ_inj and I keep thinking Peano was right (injectivity of the successor function must be an axiom) and the NNG is wrong (it's not a theorem). NNG gives you the pred_succ theorem, and calls it a theorem, but I don't see how it's supposed to be proved. Suppose the successor to 9 were 3. What's stopping that from being the case? I don't see that pred_succ ("pred succ n = n" for all n) is a lemma from which succ_inj can be proved - it looks to me like pred_succ is logically equivalent to succ_inj. Each is true if and only if the other is. Here the problem is not so much that the pred function is mathematically pathological as that the axioms, without the axiom that the successor function is injective, do not allow us to define a predecessor function at all. The guarantee that when, you call succ on nine, you don't get a number that is also the successor of some other number -- which is necessary in order for pred_succ to be a valid theorem -- is precisely the statement that succ is injective. Am I missing something?
- 082349872349872 3y agoThe equivalence sounds reasonable to me; it ensures that 0 is the start of a unique head. Does it also prevent a forward fork, to two separate tails? I was very wrong earlier: characteristic is taken care of by 0 not being a successor; injectivity of succ also allows circular pseudo-nats. PS. found Peano (1889): https://archive.org/details/arithmeticespri00peangoog/page/n22/mode/2up https://archive.org/details/arithmeticespri00peangoog/page/n... his: 7. a,b ∈ N .Ↄ: a = b .=. a+1 = b+1 8. a ∈ N .Ↄ. a+1 -= 1 are our: 7. a,b ∈ ℕ ⇒ (a = b ↔ S a = S b) 8. a ∈ ℕ ⇒ S a ≠ 0
- thaumasiotes 3y ago> Does it also prevent a forward fork, to two separate tails? This is prevented by saying that the successor function is a function. If a = b, then S(a) necessarily equals S(b). (The other half of axiom 7, the statement that when S(a) = S(b) then a = b, is the definition of an injective function. It's what prevents us from saying that the successor to 9 is 3.) There is a fun image of dominos on the wikipedia page for the Peano axioms that explains how the structure of the natural numbers is constrained by the axioms. A backwards loop from a number in the chain of succession from zero to an earlier number in the same chain can't happen because the successor function is injective. A backwards fork (two chains meeting) can't happen for the same reason. A forwards fork would be invisible to us as long as our only available tool is the successor function, which will always choose the same branch of the fork. This essentially means that forwards forks don't exist. There could be a larger structure in which it is true that e.g. the "9" node has one outgoing edge pointing to "10" and another one pointing to "green", but only one of those edges can be the edge picked out by the successor function, so our structure would only include one of the "10" or "green" nodes. A loop parallel to the chain of succession from zero [imagine the normal chain "0, 1, 2, ..." alongside the three special elements 甲 乙 丙 arranged in a three-element circle] is ruled out by axiom 9, which says that any set that contains the chain of succession from zero contains all the natural numbers. thinking out loud... we are free to define a predecessor function by saying it is the inverse of the successor function. That definition would immediately prove the pred_succ theorem, as long as the successor function is invertible. Half the definition of being invertible is being injective, so this doesn't let us prove succ_inj in a non-circular way. I don't know how else we would attempt to define the predecessor function, given the algebraic structure we're working with where all values take the form "0" or "succ n".