Questions about Gödel's incompleteness theorems and related topics.
3
votes
1answer
37 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
89 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
105 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
81 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))?$$
3
votes
1answer
146 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
178 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
64 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 ...
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
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 ...
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. ...
0
votes
1answer
353 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
129 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
116 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 ...
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 ...
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 ...
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 ...
2
votes
1answer
76 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 ...
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 ...
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
2answers
133 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 ...
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 ...
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 ...
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
620 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
136 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 ...
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.
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
574 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?
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 ...
10
votes
3answers
442 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 ...
6
votes
3answers
937 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 ...
3
votes
1answer
68 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 ...
22
votes
6answers
794 views
Why is the Continuum Hypothesis (not) true?
I'm making my way through Peter J. Cameron's seminal text "Sets, Logics and Categories" where he makes the statement that the Continuum Hypothesis (There does not exist a set with a cardinality less ...
2
votes
1answer
151 views
About a step in the proof of Gödel-Rosser Theorem.
I am reading about the Gödel-Rosser Theorem, i.e. the Rosser's refinement of first Gödel's incompleteness Theorem, which states that if $\mathbf{PA}$ is consistent then it is incomplete.
I am posting ...
3
votes
4answers
602 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 ...
1
vote
2answers
184 views
Is there a non-contradictory non-trivial axiomatic system in which Gödel's theorem is undecidable?
Gödel's Incompleteness Theorem states that in any non-contradictory non-trivial axiomatic system there are certain statements or theorems whom cannot be proved in that system,
For example in ZFC, ...
0
votes
2answers
157 views
What is actually “relatively consistent”?
Gödel's incompleteness theorem states that: "if a system is consistent, it is not complete." And it's well known that there are unprovable statements in ZF, e.g. GCH, AC, etc.
However, why does this ...
5
votes
3answers
299 views
Is the negation of the Gödel sentence always unprovable too?
The incompleteness theorem says that certain theories+deduction system contain at least one sentence (the Gödel sentence "$G$"), which can't be proven (in the system in which it holds).
(i) Is ...
2
votes
1answer
141 views
A qualitative, yet precise statement of Godel's incompleteness theorem?
I read online a statement to the effect that (I'm paraphrasing):
Goedel's incompleteness theorem shows that we cannot even have a complete and consistent theory for the natural numbers.
I am ...
3
votes
5answers
241 views
Gödel says: countable proofs, uncountable conjectures?
I thought I understood Gödel's Incompleteness Theorem to say:
Starting from ZF, there only a countable number of proofs you can write
The number of possible conjectures is uncountable.
Thus, ...
