Questions about Gödel's incompleteness theorems and related topics.
3
votes
1answer
35 views
Complexity of transforming an indirect proof into a direct one
Suppose that ZFC is consistent, and let ZFC'=ZFC+Con(ZFC). We can define a reasonable notion of
the length of a proof inside ZFC', such that for any $n$ the set $P_n$ of all proofs of length $\leq n$
...
4
votes
1answer
54 views
Special undecidability situation
Suppose that ZFC is consistent, and let ZFC'=ZFC+Con(ZFC). Can one construct two
statements $\phi_1$ and $\phi_2$ such that
$$
ZFC' \vdash ((ZFC \vdash \phi_1) \ \text{or} \ (ZFC \vdash \phi_2))
$$
...
3
votes
2answers
87 views
Does $\Sigma_1 \cup \Pi_1$ generate the complete first order theory of arithmetic?
If a set $T$ of sentences in the language of arithmetic
is deductively closed under the usual inference rules of first order logic, and
includes all true $\Sigma_1$ sentences and all true $\Pi_1$ ...
6
votes
4answers
104 views
Second order logic question.
I'm reading Michael Potter's book "Set Theory and its Philosophy" and where he's explaining why he chose to use first-order predicate calculus with identity instead of second order logic to reason ...
2
votes
3answers
79 views
If $\newcommand\PA{\mathrm{PA}}\newcommand\Con{\operatorname{Con}}\Con(\PA)$, then $\Con(\PA+\Con(\PA))$?
Assume that $\PA$ is consistent.
Then we know that $\PA$ cannot prove $\Con(\PA)$. I was wondering. Can $\PA$ prove that $$\Con(\PA) \Rightarrow \Con(\PA + \Con(\PA))?$$
10
votes
5answers
721 views
Is there a proof of Gödel's Incompleteness Theorem without self-referential statements?
For the proof of Gödel's Incompleteness Theorem, most versions of proof use basically self-referential statements.
My question is, what if one argues that Gödel's Incompleteness Theorem only matters ...
3
votes
1answer
144 views
Are Real Numbers axioms a consistent or complete system?
Do we know if the axioms of the real numbers are consistent, complete or neither of both?
And if so, is it a consequence of Godel's theorem or of something else?
7
votes
2answers
175 views
Proof of Proposition/Theorem V in Gödel's 1931 paper?
Proposition V in Gödel's famous 1931 paper is stated as follows:
For every recursive relation $ R(x_{1},...,x_{n})$ there is an n-ary "predicate" $r$ (with "free variables" $u_1,...,u_n$) such that, ...
5
votes
1answer
63 views
How many digits of Chaitin's $\Omega$ constant would we know if we had a $\Sigma_1$-Oracle?
According to Wikipedia (and it seems intuitive from the definition itself), $\Omega$ is Turing equivalent to the halting problem and thus at level $\Delta_2^0$ of the arithmetical hierarchy. Do this ...
5
votes
2answers
197 views
“Completeness modulo Godel sentences”?
So this has been bugging me for roughly four years. When I was an undergraduate, I attended a colloquium in which the speaker was a 'cheerleader' for AD (the axiom of determinacy- an alternative to ...
3
votes
2answers
88 views
Talking about Gödel's incompleteness theorems…
I will give a talk about Gödel's incompleteness theorems to a group of people consisting of undergraduates of mathematics, graduates of informatics and etc (they are not really familiar with the ...
4
votes
1answer
92 views
Understanding the syntactical completeness
A formal system is syntactically complete if for each sentence
(closed formula) $\varphi$ either $\varphi$ or $\lnot \varphi$ is
provable.
A formal system is semantically complete if every ...
1
vote
1answer
65 views
One cannot know if a number could be written any shorter according to Gödel's incompleteness theorem
I am reading Tor Nørretranders (cannot find the English version, sry) and he states that Gödel's incompleteness theorem implies that we cannot know if we can write a number any shorter (e.g. ...
1
vote
1answer
56 views
What percentage of formulas is unprovable in a given axiomatic system?
I am trying to use language I am not familiar with, so bear with me. If I make no sense, I try to be clearer.
Assume we are given a formal language. Assume $S$ is the set of every well-formed formula ...
3
votes
1answer
110 views
System with infinite number of axioms
Assume we have a set of axioms $A_0$. There exists a statement that can be formulated with these axioms that cannot be proven to be true with this system. Assume we give such a statement axiomatic ...
2
votes
2answers
701 views
Is Gödel's theorem invalid? [closed]
Right now I've skim through Gödel's theorem is invalid by Diego Saá on arXiv (freely available).
As it seems very plausible, I ask for any references and scrutinizations of the paper.
0
votes
1answer
352 views
URM computable indicating RAM computability
How can we show that every URM computable function is RAM computable?
I can see that that from Church's thesis, URM Computability iff p.r., but now sure how to get this claim above.
Taking the hint ...
3
votes
1answer
127 views
Gödel Completeness theorem
I realized recently that I did not understand well the completeness theorem of Godel, and how it interacts with the incompleteness theorems.
What I understand now (and you will see my understanding ...
0
votes
1answer
40 views
Completeness and consistency of system of calculus
It is widely held that ZFC cannot be shown to be self-consistent or complete.
So, what happens to the system of calculus? Can it be shown to be complete or self-consistent?
(Edit: Oops. So, two ...
6
votes
2answers
75 views
Is Goedel term (in incomleteness theorem) both true and unproveable?
In Goedel incompleteness theorem is Goedel term both true and unproveable, or just unproveable and truth neutral?
Can we add Goedel term to the theory as axiom and get new theory?
Can we add Goedel ...
9
votes
1answer
101 views
Is there a quicker argument from the HBL derivability conditions to the equivalence of fixed points of $\neg\Box$ to $\mathsf{Con}$?
I'm just about to send off the final, final corrected PDF of the second edition of my Gödel book, and the following (neurotic?!?) question occurs to me.
In discussing matters around and about the ...
4
votes
2answers
115 views
Sequent calculus and first incompletness theorem
Wikipedia says that sequent calculus is sound and complete (http://en.wikipedia.org/wiki/Sequent_calculus#Properties_of_the_system_LK). Godel first incompleteness theorem says that system capable of ...
2
votes
1answer
62 views
When and why does the Lindenbaum extension construction fail for second order theories?
From any consistent set of first order sentences $\Gamma$, one may generate by an inductive process a unique set of sentences $\Delta(\Gamma)$ such that $\forall A, \Gamma \models A \implies A \in ...
3
votes
4answers
601 views
Consistency of Peano axioms (Hilbert's second problem)?
(Putting aside for the moment that Wikipedia might not be the best source of knowledge.)
I just came across this Wikipedia paragraph on the Peano-Axioms:
The vast majority of contemporary ...
7
votes
0answers
143 views
Gödelian incompleteness; Smullyan's Puzzle
I am currently doing exercises on the Gödelian theorems; and we are confronted with the introductory puzzle of R. Smullyan's book, which is as follows:
Suppose we have a machine which prints strings ...
6
votes
3answers
927 views
are there non-standard models of arithmetic in second order arithmetic?
non-standard models of arithmetic in second order arithmetic?
Background:
According to Godel's theorem, if we have, in a given consistent system S, a non-provable wff. A, then we can extend the ...
0
votes
1answer
110 views
Gödel's Incompleteness Theorem — meta-reasoning “loophole”?
Gödel's Theorem says that I can construct a mathematical statement like "f(x1,x2,...,x_n)=0 has no integer solution", where it is impossible (in a certain system of axioms) to formally prove that it's ...
10
votes
6answers
2k views
Why bother with Mathematics, if Gödel's Incompleteness Theorem is true?
OK, maybe the title is exaggerated, but is it true that the rest of math is just "good enough", or a good approximation of absolute truth - like Newtonian physics compared to general relativity? How ...
7
votes
3answers
201 views
“The set of all true statements of first order logic”
In one of my lectures, the lecturer put a bunch of examples of sets on the board, stuff like the set of all humans, set of all well typed programs in some programming language, the set of all true ...
4
votes
1answer
103 views
Question about $\Sigma_n$-soundness
According to wikipedia (http://en.wikipedia.org/wiki/%CE%A9-consistent_theory#Definition): "$\Sigma_n$-soundness has the following computational interpretation: if the theory proves that a program C ...
2
votes
1answer
75 views
question about Godel numbering
I have a question about Godel numbering, it is trivial but I would like to know how can you know the length of an expression through its Godel number. ¿?
I think you can use a recursive function but ...
2
votes
2answers
132 views
I do not understand why the Turing computable sets of N are exactly the sets at level $\Delta_1^0$ of the arithmetical hierarchy
The reason I don't understand it is this. Take for example the twin primes conjecture, which is $\Pi_2^0$. The set of twin primes is computable right? (there is a Turing machine that enumerates all of ...
0
votes
1answer
46 views
Question about computability of true/provable formulas
I would like to clarify some things related to the computability of the sets of all theorems and true formulas for the formal arithmetic.
Consider the theory $T$ of formal arithmetic (the theory of ...
2
votes
1answer
79 views
Is there a mechanical procedure within PA to reduce any ϕ to its simplest (in terms of the arithmetical hierarchy) logically equivalent form?
The question is motivated because we know that the Turing computable sets of natural numbers are exactly the sets at level $\Delta_1^0$ of the arithmetical hierarchy. We also know that the finite ...
1
vote
1answer
35 views
Finding polynomials with a specific property
I am stuck with the following problem.
Show that there exist a $n \in \mathbb{N}$ and polynomials $p,q \in \mathbb{N}[x_1,\ldots,x_n]$ such that neither the formula $$ \phi(n,p,q) = \forall x_1 ...
5
votes
1answer
136 views
Is every φ above the second level of the arithmetical hierarchy independent of PA?
If I am not wrong, every $\Sigma_n$ (or $\Pi_n$ ) statement $\phi$ is equivalent to a statement that says that a given Turing machine halts (or doesn't halt) on input $C$ using a ...
2
votes
3answers
156 views
What is it wrong in this argument about the interpretability hierarchy?
This is a question that I fully reedited to make it more precise. Many thanks to the people that answered the previous version to get this distilled one.
Background: (from ...
12
votes
4answers
617 views
Does Gödel's Incompleteness Theorem really say anything about the limitations of theoretical physics?
Stephen Hawking believes that Gödel's Incompleteness Theorem makes the search for a 'Theory of Everything' impossible. He reasons that because there exist mathematical results that cannot be proven, ...
2
votes
1answer
71 views
Given a φ independent of PA which is true in the standard model, will always (PA+ ¬φ) be Σn-unsound for some n?
Given a φ independent of PA which is true in the standard model, will always (PA+ ¬φ) be Σn-unsound for some n?
This is a follow up from a previous question:
Given a φ independent of PA which is true ...
9
votes
1answer
135 views
Given a φ independent of PA which is true in the standard model, will always (PA+ ¬φ) be ω-inconsistent?
Given a φ independent of PA which is true in the standard model, will always (PA+ ¬φ) be ω-inconsistent? Does it mean that every such ¬φ can be used to prove that a Turing machine halts on a given C ...
28
votes
5answers
4k views
Understanding Gödel's Incompleteness Theorem
I am trying very hard to understand Gödel's Incompleteness Theorem. I am really interested in what it says about axiomatic languages, but I have some questions:
Gödel's theorem is proved based on ...
2
votes
3answers
79 views
Provability becoming decidable in a larger system?
Let $T$ be an effectively axiomatizable system that we believe to be consistent, and expressive enough so that Godel’s theorem applies to it.
Then we have that the provability statements related to ...
9
votes
5answers
572 views
What does it mean for something to be true but not provable in peano arithmetic?
Specifically, the Paris-Harrington theorem.
In what sense is it true? True in Peano arithmetic but not provable in Peano arithmetic, or true in some other sense?
10
votes
3answers
437 views
What is the prerequisite knowledge for learning Godel's incompleteness theorem
I am very interested in learning the incompleteness theorem and its proof.
But first I must know what things I need to learn first.
My current knowledge consists of basic high school education and the ...
1
vote
2answers
612 views
Explanation of proof of Gödel's Second Incompleteness Theorem
I am looking for a simple explanation/outline of the proof of Gödel's Second Incompleteness Theorem, and I haven't yet been able to find anything that is within my grasp. I'm looking for something ...
4
votes
6answers
441 views
prove that it's not provable
Is it possible to prove that you can't prove some theorem? For example: Prove that you can't prove the rieman hypothesis. I have a feeling it's not possible but I want to know for sure. Thanks in ...
0
votes
1answer
197 views
Use of undecidability
Suppose someone proved that the Goldbach conjecture was undecidable in an axiomatic system that is consistent as far as we know.
Then in some sense we know that Goldbach conjecture must be "true", ...
3
votes
1answer
67 views
Can decidability results for monadic second-order logic be extended to monadic higher-order logics?
Call a higher-order logic fully monadic if and only if all of its predicate constants (at any order) and higher-order variables (at any order) are monadic (and it has no function symbols). In Solvable ...
8
votes
2answers
180 views
Axiomatic system and Hilbert's 2nd problem
Hilbert's second problem asks if the axioms of arithmetic are consistent. Has this problem been resolved? Shouldn't an axiomatic system ideally be consistent and complete(given that we have the ...
4
votes
4answers
2k views
What is the difference between Completeness and Soundness in first order logic?
Completeness is defined as if given $\Sigma\models\Phi$ then $\Sigma\vdash\Phi$.
Meaning if for every truth placement $Z$ in $\Sigma$ we would get $T$, then $\Phi$ also would get $T$. If the previous ...
