Skip to main content
Philosophy

Return to Answer

Mod Moved Comments To Chat
added 3413 characters in body
Source Link
user21820
user21820
  • 811
  • 1
  • 9
  • 26

Arguably, noneNone of the existingother answers are correct. Here is(so far) addressed the correct answer:actual mathematical inquiry here.

Firstly, your question is straightforwardly formalized as follows: Suppose you have an oracle O that when given any computable formal system S and a sentence Q can determine in finitely many steps whether or not Q is a theorem of S. Then you ask whether or not O can be used to generate all and only true arithmetical sentences. (This notion of finite-step oracles is a standard way of formalizing programs that can use oracles. See any text on computability theory for technical details, but finer details don't really matter.)

In other words, if you want to generate all true arithmetical sentences, you need an oracle that is at least as powerful as the ω-th jump, which is simply defined asin the setsense that you need to be able to invoke any finite jump you like. This directly corresponds to the quantifier complexity of all pairs ⟨k,Jthe arithmetical sentence (karithmetical hierarchy)⟩ where k∈ℕ and J. We can computably decide the truth-value of any Σ0-sentence, since we can enumerate all the cases when all quantifiers are bounded. It is not hard to see that we can decide the truth-value of any Σ1-sentence using the first jump (khalting oracle) is, by asking whether the program that tries each possible value of the outer "∃" one by one halts or not. It turns out that we can in general decide the truth-value of any Σ[k]-sentence using the k-th jump.

Note that there have been extremely difficult mathematical problems that were shown (in a slightly stronger foundational system) to be equivalent to some arithmetical sentence of very low complexity. For example, Riemann Hypothesis is known to be equivalent to a Π1-sentence, so your powerful mathematician would already be able to solve it. But both Twin-Prime Conjecture and P≠NP are only known to be Π2, so we can solve them using the second jump but your powerful mathematician may not be able to solve them. However, your powerful mathematician can tell you whether ZFC proves or disproves any of them, and maybe that is good enough for you (if you assume ZFC does not prove any false arithmetical sentence).

For the curious, the mathematical content of this answer does not rely on any assumptions except the existence of (ℕ,0,1,+,·) as a model of PA and the existence of all finite jumps. These assumptions are provided by a very weak system known as ACA, so you can be assured that there are no sneaky philosophical assumptions that this answer relies on.

Note also that we in fact cannot extend the notion of "true arithmetical sentence" to "true mathematical statement". In the first place, "true arithmetical sentence" is defined as "arithmetical sentence true in N where N = (ℕ,0,1,+,·). So "true mathematical statement" is as meaningless as "true jyxowvazic statment" in the sense that we have not defined "mathematical statement".

Even if we fix our foundational system, say as ZFC, we cannot define "true ZFC statement" in the same manner because we would need to define it as "sentence over ZFC true in M" where M is some specific model of ZFC. But ZFC cannot prove the existence of a model of ZFC, again by the incompleteness theorem (in conjunction with the semantic completeness theorem for FOL), so this fails. The same goes for essentially any reasonable foundational system, not just ZFC.

Neither can we define "true set-theoretic sentence" as "sentence over ZFC that is true in V" where V is class of all sets (i.e. the meta-universe), because if this notion was definable by a predicate Tr then we can explicitly write down (by the same diagonalization as in Godel's original proof of the incompleteness theorem) a sentence D over ZFC such that we can prove D⇔¬Tr(str(D)) where str(D) is the string representing D, and then get D⇔¬D, which we certainly do not want to get. This fact was discovered by Tarski, and is called Tarski's undefinability theorem.

But anyway all that does not matter for the original inquiry. If the halting oracle is not powerful enough to enable us to decide all true arithmetical sentences, then of course it is not powerful enough to enable us to decide all true sentences in whatever ω-model of ZFC (i.e. model of ZFC that has the standard naturals) that we might ever specify.

Arguably, none of the existing answers are correct. Here is the correct answer:

Firstly, your question is straightforwardly formalized as follows: Suppose you have an oracle O that when given any computable formal system S and a sentence Q can determine in finitely many steps whether or not Q is a theorem of S. Then you ask whether or not O can be used to generate all and only true arithmetical sentences.

In other words, if you want to generate all true arithmetical sentences, you need an oracle that is at least as powerful as the ω-th jump, which is simply defined as the set of all pairs ⟨k,J(k)⟩ where k∈ℕ and J(k) is the k-th jump.

For the curious, the mathematical content of this answer does not rely on any assumptions except the existence of (ℕ,0,1,+,·) as a model of PA and the existence of all finite jumps. These assumptions are provided by a very weak system known as ACA, so you can be assured that there are no sneaky philosophical assumptions that this answer relies on.

None of the other answers (so far) addressed the actual mathematical inquiry here.

Firstly, your question is straightforwardly formalized as follows: Suppose you have an oracle O that when given any computable formal system S and a sentence Q can determine in finitely many steps whether or not Q is a theorem of S. Then you ask whether or not O can be used to generate all and only true arithmetical sentences. (This notion of finite-step oracles is a standard way of formalizing programs that can use oracles. See any text on computability theory for technical details, but finer details don't really matter.)

In other words, if you want to generate all true arithmetical sentences, you need an oracle that is at least as powerful as the ω-th jump, in the sense that you need to be able to invoke any finite jump you like. This directly corresponds to the quantifier complexity of the arithmetical sentence (arithmetical hierarchy). We can computably decide the truth-value of any Σ0-sentence, since we can enumerate all the cases when all quantifiers are bounded. It is not hard to see that we can decide the truth-value of any Σ1-sentence using the first jump (halting oracle), by asking whether the program that tries each possible value of the outer "∃" one by one halts or not. It turns out that we can in general decide the truth-value of any Σ[k]-sentence using the k-th jump.

Note that there have been extremely difficult mathematical problems that were shown (in a slightly stronger foundational system) to be equivalent to some arithmetical sentence of very low complexity. For example, Riemann Hypothesis is known to be equivalent to a Π1-sentence, so your powerful mathematician would already be able to solve it. But both Twin-Prime Conjecture and P≠NP are only known to be Π2, so we can solve them using the second jump but your powerful mathematician may not be able to solve them. However, your powerful mathematician can tell you whether ZFC proves or disproves any of them, and maybe that is good enough for you (if you assume ZFC does not prove any false arithmetical sentence).

For the curious, the mathematical content of this answer does not rely on any assumptions except the existence of (ℕ,0,1,+,·) as a model of PA and the existence of all finite jumps. These assumptions are provided by a very weak system known as ACA, so you can be assured that there are no sneaky philosophical assumptions that this answer relies on.

Note also that we in fact cannot extend the notion of "true arithmetical sentence" to "true mathematical statement". In the first place, "true arithmetical sentence" is defined as "arithmetical sentence true in N where N = (ℕ,0,1,+,·). So "true mathematical statement" is as meaningless as "true jyxowvazic statment" in the sense that we have not defined "mathematical statement".

Even if we fix our foundational system, say as ZFC, we cannot define "true ZFC statement" in the same manner because we would need to define it as "sentence over ZFC true in M" where M is some specific model of ZFC. But ZFC cannot prove the existence of a model of ZFC, again by the incompleteness theorem (in conjunction with the semantic completeness theorem for FOL), so this fails. The same goes for essentially any reasonable foundational system, not just ZFC.

Neither can we define "true set-theoretic sentence" as "sentence over ZFC that is true in V" where V is class of all sets (i.e. the meta-universe), because if this notion was definable by a predicate Tr then we can explicitly write down (by the same diagonalization as in Godel's original proof of the incompleteness theorem) a sentence D over ZFC such that we can prove D⇔¬Tr(str(D)) where str(D) is the string representing D, and then get D⇔¬D, which we certainly do not want to get. This fact was discovered by Tarski, and is called Tarski's undefinability theorem.

But anyway all that does not matter for the original inquiry. If the halting oracle is not powerful enough to enable us to decide all true arithmetical sentences, then of course it is not powerful enough to enable us to decide all true sentences in whatever ω-model of ZFC (i.e. model of ZFC that has the standard naturals) that we might ever specify.

Source Link
user21820
user21820
  • 811
  • 1
  • 9
  • 26

Arguably, none of the existing answers are correct. Here is the correct answer:

Firstly, your question is straightforwardly formalized as follows: Suppose you have an oracle O that when given any computable formal system S and a sentence Q can determine in finitely many steps whether or not Q is a theorem of S. Then you ask whether or not O can be used to generate all and only true arithmetical sentences.

Note that I changed "true mathematical statement" to "true arithmetical sentence", because the former is meaningless but the latter is meaningful once you assume the existence of the structure (ℕ,0,1,+,·). So what is the answer to the formalization of your question?

No! To see why, observe that we can trivially construct such an O using the halting oracle (the oracle that solves the halting problem for programs). But by the generalized incompleteness theorem, the set T of all true arithmetical sentences is not the theorems of any formal system that has a proof verifier program that is permitted to invoke the halting oracle! So O cannot generate T.

In fact, the very same theorem in the linked post generalizes to every finite Turing jump (the (k+1)-th jump is the oracle that solves the halting problem for programs that can invoke the k-th jump), as was briefly mentioned at the end of the linked post. Thus the answer is still no even if you allow your oracle O to invoke any finite jump (not just be able to determine deducibility over any foundational system).

In other words, if you want to generate all true arithmetical sentences, you need an oracle that is at least as powerful as the ω-th jump, which is simply defined as the set of all pairs ⟨k,J(k)⟩ where k∈ℕ and J(k) is the k-th jump.

For the curious, the mathematical content of this answer does not rely on any assumptions except the existence of (ℕ,0,1,+,·) as a model of PA and the existence of all finite jumps. These assumptions are provided by a very weak system known as ACA, so you can be assured that there are no sneaky philosophical assumptions that this answer relies on.