ω-inconsistency isn’t exactly the same thing as being false in the standard model. Being ω-inconsistent requires both that the theory prove all the statements P(n) for standard natural numbers n, but also prove that there is an n for which P(n) fails. Therefore a theory could be ω-consistent because it fails to prove P(n), even though P(n) is true in the standard model. So even if we could check ω-consistency, we could take PA, add an axiom T, and end up with an ω-consistent theory which nonetheless is not true in the standard model.
By the way, there are some papers on models for adding random (true) axioms to PA. “Are Random Axioms Useful?” involves some fairly specific cases, but shows that in those situations, random axioms generally aren’t likely to tell you anything you wanted to know.
Perhaps LessWrong is a place where I can say “Your question is wrong” without causing unintended offense. (And none is intended.)
Yes, for ω-consistency to even be defined for a theory it must interpret the language of arithmetic. This is a necessary precondition for the statement you quoted, and does not contradict it.
Work in PA, and take a family of statements P(n) where each P(n) is true but independent of PA, and not overly simple statements themselves—say, P(n) is “the function epsilon n in the fast growing hierarchy is a total function”. (The important thing here is that the statement is at least Pi2---true pure existence statements are always provable, and if the statements were universal there would be a different ω-consistency problem. The exact statement isn’t so important, but not that these statements are true, but not provable in PA.)
Now consider the statement T=”there is an n such that P(n) is false”. PA+T has no standard model (because T is false), but PA+T doesn’t prove any of the P(n), let alone all of them, so there’s no ω-consistency problem.
I’m a fan of Enderton’s “A Mathematical Introduction to Logic”. It’s short and very precisely written, which can make it a little difficult to learn from on its own, but together with a general familiarity with the subject and using wikipedia for additional examples elaboration, it should be perfect.
ω-inconsistency isn’t exactly the same thing as being false in the standard model. Being ω-inconsistent requires both that the theory prove all the statements P(n) for standard natural numbers n, but also prove that there is an n for which P(n) fails. Therefore a theory could be ω-consistent because it fails to prove P(n), even though P(n) is true in the standard model. So even if we could check ω-consistency, we could take PA, add an axiom T, and end up with an ω-consistent theory which nonetheless is not true in the standard model.
By the way, there are some papers on models for adding random (true) axioms to PA. “Are Random Axioms Useful?” involves some fairly specific cases, but shows that in those situations, random axioms generally aren’t likely to tell you anything you wanted to know.
I thought for ω-consistency to even be defined for a theory it must interpret the language of arithmetic?
Perhaps LessWrong is a place where I can say “Your question is wrong” without causing unintended offense. (And none is intended.)
Yes, for ω-consistency to even be defined for a theory it must interpret the language of arithmetic. This is a necessary precondition for the statement you quoted, and does not contradict it.
Work in PA, and take a family of statements P(n) where each P(n) is true but independent of PA, and not overly simple statements themselves—say, P(n) is “the function epsilon n in the fast growing hierarchy is a total function”. (The important thing here is that the statement is at least Pi2---true pure existence statements are always provable, and if the statements were universal there would be a different ω-consistency problem. The exact statement isn’t so important, but not that these statements are true, but not provable in PA.)
Now consider the statement T=”there is an n such that P(n) is false”. PA+T has no standard model (because T is false), but PA+T doesn’t prove any of the P(n), let alone all of them, so there’s no ω-consistency problem.
Thanks, can you recommend a textbook for this stuff? I’ve mostly been learning off Wikipedia.
I can’t find a textbook on logic in the lesswrong textbook list.
I’m a fan of Enderton’s “A Mathematical Introduction to Logic”. It’s short and very precisely written, which can make it a little difficult to learn from on its own, but together with a general familiarity with the subject and using wikipedia for additional examples elaboration, it should be perfect.