First-order logic can’t distinguish between different sizes of infinity. Any finite or countable set of first-order statements with an infinite model has models of all sizes.
However, if you take second-order logic at face value, it’s actually quite easy to uniquely specify the integers up to isomorphism. The price of this is that second-order logic is not complete—the full set of semantic implications, the theorems which follow, can’t be derived by any finite set of syntactic rules.
So if you can use second-order statements—and if you can’t, it’s not clear how we can possibly talk about the integers—then the structure of integers, the subject matter of integers, can be compactly singled out by a small set of finite axioms. However, the implications of these axioms cannot all be printed out by any finite Turing machine.
Appropriately defined, you could state this as “finitely complex premises can yield infinitely complex conclusions” provided that the finite complexity of the premises is measured by the size of the Turing machine which prints out the axioms, yielding is defined as semantic implication (that which is true in all models of which the axioms are true), and the infinite complexity of the conclusions is defined by the nonexistence of any finite Turing machine which prints them all.
However this is not at all the sort of thing that Dawkins is talking about when he talks about evolution starting simple and yielding complexity. That’s a different sense of complexity and a different sense of yielding.
I misinterpreted this: “we can never know all the truths of euclidean geometry, but we can still specify euclidean geometry via a set of axioms. Not so for arithmetic.”
Eliezer: There are an infinite number of truths of euclidean geometry. How could our finite brains know them all?
This was not meant to be a profound observation; it was meant to correct Silas, who seemed to think that I was reading some deep significance into our inability to know all the truths of arithmetic. My point was that there are lots of things we can’t know all the truths about, and this was therefore not the feature of arithmetic I was pointing to.
A decision procedure is a finite specification of all truths of euclidean geometry; I can use that finite fact anywhere I could use any truth of geometry. I suppose there is a difference, but even so, it’s the wrong thing to say in a Godelian discussion.
it was meant to correct Silas, who seemed to think that I was reading some deep significance into our inability to know all the truths of arithmetic. My point was that there are lots of things we can’t know all the truths about, and this was therefore not the feature of arithmetic I was pointing to.
Yes, it was. When I and several others pointed out that arithmetic isn’t actually complex, you responded by saying that it is infinitely complex, because it can’t be finitely described, because to do so … you’d have to know all the truths.
Am I misreading that response? If so, how do you reconcile arithmetic’s infinite complexity with the fact that scientists in fact use it to compress discriptions of the world? An infinitely complex entity can’t help to compress your descriptions.
That doesn’t sound right. Can you point me to for example a Wikipedia page about this?
First-order logic can’t distinguish between different sizes of infinity. Any finite or countable set of first-order statements with an infinite model has models of all sizes.
However, if you take second-order logic at face value, it’s actually quite easy to uniquely specify the integers up to isomorphism. The price of this is that second-order logic is not complete—the full set of semantic implications, the theorems which follow, can’t be derived by any finite set of syntactic rules.
So if you can use second-order statements—and if you can’t, it’s not clear how we can possibly talk about the integers—then the structure of integers, the subject matter of integers, can be compactly singled out by a small set of finite axioms. However, the implications of these axioms cannot all be printed out by any finite Turing machine.
Appropriately defined, you could state this as “finitely complex premises can yield infinitely complex conclusions” provided that the finite complexity of the premises is measured by the size of the Turing machine which prints out the axioms, yielding is defined as semantic implication (that which is true in all models of which the axioms are true), and the infinite complexity of the conclusions is defined by the nonexistence of any finite Turing machine which prints them all.
However this is not at all the sort of thing that Dawkins is talking about when he talks about evolution starting simple and yielding complexity. That’s a different sense of complexity and a different sense of yielding.
That makes more sense, thanks.
Any recommended reading on this sort of thing?
Decidability of Euclidean geometry#Some_decidable_theories).
I don’t know where Landsburg gets the claim that we can know all the truths of arithmetic.
Richard Kennaway:
I don’t know where Landsburg gets the claim that we can know all the truths of arithmetic.
I don’t know where you got the idea that I’d ever make such a silly claim.
I misinterpreted this: “we can never know all the truths of euclidean geometry, but we can still specify euclidean geometry via a set of axioms. Not so for arithmetic.”
Richard: Gotcha. Sorry if it was unclear which part the “not so” referred to.
Note that Landsburg is thus also incorrect in saying “we can never know all the truths of euclidean geometry”.
Eliezer: There are an infinite number of truths of euclidean geometry. How could our finite brains know them all?
This was not meant to be a profound observation; it was meant to correct Silas, who seemed to think that I was reading some deep significance into our inability to know all the truths of arithmetic. My point was that there are lots of things we can’t know all the truths about, and this was therefore not the feature of arithmetic I was pointing to.
A decision procedure is a finite specification of all truths of euclidean geometry; I can use that finite fact anywhere I could use any truth of geometry. I suppose there is a difference, but even so, it’s the wrong thing to say in a Godelian discussion.
Yes, it was. When I and several others pointed out that arithmetic isn’t actually complex, you responded by saying that it is infinitely complex, because it can’t be finitely described, because to do so … you’d have to know all the truths.
Am I misreading that response? If so, how do you reconcile arithmetic’s infinite complexity with the fact that scientists in fact use it to compress discriptions of the world? An infinitely complex entity can’t help to compress your descriptions.