cruegge

Correct me if I'm wrong, but I don't think humans are reptiles, phylogenetically. The Synapsida (containing mammals) and Sauropsida (containing reptiles) are sibling groups inside the Amniota.

They're not infailable, though. For example, TeX's primitive for fractions is actually {a \over b}, LaTeX's \frac is a macro on top of that. The consequence is that while typesetting a formula, the engine does not know the current text size, since an \over further down the line may put the entire thing into a numerator. Dealing with this can be quite a pain when writing math macros.

I think a = sqrt(2), b = log(9)/log(2) with a^b = 3 is easier. To show that b is irrational, assume b = n/m for integer n, m. Then 9^m = 2^n, which can't be the case since the lhs is odd and the rhs is even.

> Yes, I thought this was clear from my statement.

Yeah, sorry, wasn't really necessary to repeat that point. I was too focused on the "limiting the height of the tree to 32" formulation.

I have to admit that I don't quite understand what invariants along the lookup you mean. All lookups that reach a particular node on level 32 have the same hash, so regardless of how you compute the branch from the hash below level 32, they will always follow the same path starting from there (except for terminating at different levels, obviously). So nodes only ever have one child at most, and there's no loss in simply picking child 0 in all cases.

Sorry if what I'm describing is again obvious, maybe I just don't understand your point correctly.

It's not limited to 32, but afterwards search will be linear along child[0]. Using rotation would not make a difference, since you're in the collision case already, so you would effectively always branch to the same child for levels below 32.

Ok, the more I try to understand this, the more confused I get. Probably just scrap everything I said, I'll need to do some more reading.

I see. Checking the formulation of the incompleteness theorem again, I noticed that I probably misunderstood something here: it indeed essentially requires proofs to be verifyable, which second order theories do not provide. So second order PA can (and in fact does) have a proof of every statement or its negation, without contradicting incompleteness, but provability is somewhat useless in this case. For theories that fit the conditions you listed, unprovability is indeed due to multiple models. Does that make sense?

Edit: however, consistent second order theories don't always have a model. In first order, if S is an undecideable statement in theory T, then both T+S and T+!S have models, both of which are models for T, so undecideable statements always come from multiple models. But that does not need to be the case in second order, so your claim "it is independent from the axioms, i.e. there exist multiple models" is not neccessarily true, i.e. there may be cases when decideability of some statement fails in a theory with a unique model. Or is there another argument for your claim?

Forgive me for spamming questions, I just try to understand how these things fit together. But maybe we should just stick to first order, since everything else is too weird anyway.

What I meant to say is that multiple models are not the only reason for something to be true but unprovable, the incompleteness theorem also holds in more general conditions.

Concerning multiple models of ZFC: I'm always confused by such statements about the foundations of set theory itself, they seem weirdly self-referential. ZFC certainly can't prove that it has multiple (or even any) models. Does such a statement need additional axioms, or is there a general theorem like "If a first order theory has any model, then it has multiple ones."?

That's a good intuition for first order PA, where the completeness theorem holds, but not the full story either. PA in second order logic only has a single model, but is still incomplete: there are statements that are true in the only model, but not provable.

It does double the residue, but modulo 19. 2 * 18 = 36 = 17 (mod 19) and 2 * 10 = 20 = 1 (mod 19). The reason is that the method consists essentially of two steps. (1) Subtract a suitable multiple of 19 to make the number a multiple of 10. (2) Divide by 10. And dividing by 10 is the same as multiplying by 2, since 2 * 10 = 20 = 1 (mod 19).