= 27d567bc2d48d9f40e9ccc20ea370b15)
An element of the nonstandard chain is greater than any natural number...
Can someone explain this? I don't understand how > can be a valid operation on two disconnected chains of number-thingies.
< is defined in terms of plus by saying x<y iff there exists a such that y=z+x. + is supposed to be provided as a primitive operation as part of the data consisting of a model of PA. It's not actually possible to give a concrete description of what + looks like in general for non-standard models because of Tenenbaums's Theorem, but at least when one of x or y (say x) is a standard number it's exactly what you'd expect: x+y is what you get by starting at y and going x steps to the right.
To see that x<y whenever x is a standard number and y isn't, you need to be a little tricky. You actually prove an infinite family of statements. The first one is "for all x, either x=0 or else x>0". The second is "for all x, either x=0 or x=1 or x>1", and in general it's "for all x, either x=0,1,..., or n, or else x>n". Each of these can be proven by induction, and the entire infinite family together implies that a non-standard number is bigger than every standard number.
Yes we do.
The problem of a chain isn't intended to be limited to the problem of exactly one chain, and I didn't want to complicate the diagram or confuse my readers by showing them a copy of the rationals with each rational replaced by a copy of the integers. If you can't get rid of a larger structure that has a chain in it, you can't get rid of the chain. To put it another way, showing that the chain depicted implies further extra elements isn't the same as ruling out the existence of that chain.
Hence the wording, "How do we get rid of the chain?" not "How do we get rid of this particular exact model here?"
A very quick way to see that there must be more than one chain is to note that if x > y, then x + z > y + z. An element of the nonstandard chain is greater than any natural number, so if we add two nonstandard numbers together, the result must be greater than the nonstandard starting point plus any natural number. Therefore there must be another chain which comes after the first one. For more on this see the linked paper.
EDIT: Several others reported misinterpreting what I had in the original, so I've edited the post accordingly. Thanks for raising the issue, Ilya!
It's probably worth explicitly mentioning that the structure that you described isn't actually a model of PA. I'd imagine that could otherwise be confusing for readers who have never seen this stuff before and are clever enough to notice the issue.
You get a formula which is true of the standard numbers m and i if and only if the m'th Turing machine halts on input i. Is there really any meaningful sense in which this formula is still talking about Turing machines when you substitute elements of some non-standard model?
In a sense, no. Eliezer's point is this: Given the actual Turing machine with number m = 4 = SSSS0 and input i = 2 = SS0, you can substitute these in to get a closed formula φ whose meaning is "the Turing machine SSSS0 halts on input SS0". The actual formula is something like, "There is a number e such that e denotes a valid execution history for machine SSSS0 on input SS0 that ends in a halting state." In the standard model, talking about the standard numbers, this formula is true iff the machine actually halts on that input. But in first-order logic, you cannot pinpoint the standard model, and so it can happen that formula φ is false in the standard model, but true in some nonstandard model. If you use second-order logic (and believe its standard semantics, not its Henkin semantics), formula φ is valid, i.e. true in every model, if and only if machine 4 really halts on input 2.
Okay. This is exactly what I thought it should be, but the way Eliezer phrased things made me wonder if I was missing something. Thanks for clarifying.
Yeah, there's a little non-obvious trick to talking about properties of Turing machines in the language of arithmetic, which is essential to understanding this.
The first thing you do is to use a little number theory to define a bijection between natural numbers and finite lists of natural numbers. Next, you define a way to encode the status of a Turing machine at one point in time as a list of numbers (giving the current state and the contents of the tapes); with your bijection, you can encode the status at one point in time as a single number. Now, you encode execution histories as finite lists of status numbers, which your bijection maps to a single number. You can write "n denotes a valid execution history that ends in a halting state" (i.e., n is a list of valid statuses, with the first one being a start status, the last one being a halting status, and each intermediate one being the uniquely determined correct successor to the previous one). After doing all this work, you can write a formula in the language of arithmetic saying "the Turing machine m halts on input i", by simply saying "there is an n which denotes a valid execution history of machine m, starting at input i and ending in a halting state".
Now consider an execution history consisting of a "finite" list of nonstandard length.
you can write a formula in the language of arithmetic saying "the Turing machine m halts on input i"
You get a formula which is true of the standard numbers m and i if and only if the m'th Turing machine halts on input i. Is there really any meaningful sense in which this formula is still talking about Turing machines when you substitute elements of some non-standard model?
In response to
Standard and Nonstandard Numbers
Nice post, but I think you got something wrong. Your structure with a single two-sided infinite chain isn't actually a model of first order PA. If x is an element of the two-sided chain, then y=2x=x+x is another non-standard number, and y necessarily lies in a different chain since y-x=x is a non-standard number. Of course, you need to be a little bit careful to be sure that this argument can be expressed in first order language, but I'm pretty sure it can. So, as soon as there is one chain of non-standard numbers, that forces the existence of infinitely many.
HP: Punch AM in snout to establish superiority.
Anyone else getting tired of this? Harry does it to everyone he meets, including Minerva and Hermione.
In response to
comment
by
on
Harry Potter and the Methods of Rationality discussion thread, part 17, chapter 86
I bet a large portion of the readership would have been disappointed if that didn't happen.
And in this particular case, that was the only fast way for Alastor to gain enough respect for Harry's competence that they could cooperate in the future. It wouldn't have been consistent with his already established paranoia if he just believed Dumbledore & co.
I can imagine this getting old eventually, but imo it hasn't happened yet.
About a year.
Were you trying to diet at the same time? Have you ever tried exercising more without also restricting your food intake?
Also, have you ever enjoyed exercising while doing it?
Edit: Just to be clear, this isn't supposed to be advice, implicit or otherwise. I'm just curious.
In response to
The Fabric of Real Things
"Does your rule there forbid epiphenomenalist theories of consciousness - that consciousness is caused by neurons, but doesn't affect those neurons in turn? The classic argument for epiphenomenal consciousness has always been that we can imagine a universe in which all the atoms are in the same place and people behave exactly the same way, but there's nobody home - no awareness, no consciousness, inside the brain. The usual effect of the brain generating consciousness is missing, but consciousness doesn't cause anything else in turn - it's just a passive awareness - and so from the outside the universe looks the same. Now, I'm not so much interested in whether you think epiphenomenal theories of consciousness are true or false - rather, I want to know if you think they're impossible or meaningless a priori based on your rules."
How would you reply?
You can account for a theory where neurons cause consciousness, and where consciousness has no further effects, by drawing a causal graph like
(universe)->(consciousness)
where each bracketed bit is short-hand for a possibly large number of nodes, and likewise the -> is short for a possibly large number of arrows, and then you can certainly trace forward along causal links from "you" to "consciousness", so it's meaningful. And indeed for the same reason that "the ship doesn't disappear when it crosses the horizon" is meaningful.
We reject epiphenomenal theories of consiousness because the causal model without the (consciousness) subgraph is more simpler than the one with it, and we have no evidence for the latter to overcome this prior improbability. This is of course the exact same reason why we accept that the ship still exists after it crosses the horizon.
In response to
The Fabric of Real Things
In a universe without causal structure, I would expect an intelligent agent that uses an internal causal model of the universe to never work.
Of course you can't really have an intelligent agent with an internal causal model in a universe with no causal structure, so this might seem like a vacuous claim. But it still has the consequence that
P(intelligence is possible|causal universe)>P(intelligence|acausal universe).
= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
= f037147d6e6c911a85753b9abdedda8d){kind=logo}
ZF can't prove that models of ZF exist because proving models of ZF exist is equivalent to proving that ZF is consistent, and ZF can't prove its own consistency (if it is in fact consistent) by the incompleteness theorem. I don't think ZFC can prove the consistency of ZF either, but I'm not a set theorist.
Also not a set theorist, but I'm pretty sure this is correct. ZF+Con(ZF) proves Con(ZFC) (see http://en.wikipedia.org/wiki/Constructible_universe), so if ZFC could prove Con(ZF) then it would also prove Con(ZFC).