Questions about Gödel's incompleteness theorems and related topics.

learn more… | top users | synonyms

1
vote
1answer
85 views

set theory, Incompleteness and axiomatic systems

Is the number of theorems that can be proved (decidable) within a certain set of axioms (for instance ZFC) is finite or infinite ? in other words, are we going to fully exhaust that set of axioms ...
1
vote
1answer
168 views

Criticism on truth of Gödel sentence in standard interpretation

Mendelson in his book mentioned the Gödel sentence and argued that in standard interpretation it is true. But Peter Milne in his article (On Godel Sentences and What They Say) criticized: "But we know ...
0
votes
1answer
81 views

Truth of Godel's sentence in standard interpretation

It is siad that the Godel's sentence: g is true in the standard interpretation. But I have problem in truth of g in the standard interpretation. We proved that if theory K is consistent g is not ...
1
vote
3answers
186 views

In Godel's first incompleteness theorem the Godel sentence G is true otherwise it contradicts itself, however its truth implies it is not provable .

How can this be? I understand there are two basic definitions of truth in mathematics, one being the formalist definition which includes excluded middle and the second form being the intuitionist in ...
1
vote
1answer
79 views

Boolean Algebra and Godel

Can anyone give an example of a theorem in Boolean Algebra that isn't immediately obvious to someone with a computer that can construct a truth table? Clearly no propisition that can be proved using ...
1
vote
0answers
112 views

Do we know that if $\pi$ is normal then there is a proof of it?

We do not know whether $\pi$ is normal or it is not and many other weaker statements, e.g. (*) $\pi$ contains infinitely many $0$s. Inspired by the Godel's incompleteness theorem that there are some ...
2
votes
2answers
288 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 ...
4
votes
1answer
124 views

How can I imagine a model of $\mathsf{(ZF-Inf)} + \neg \mathsf{Con(ZF-Inf)}$?

Gödel's second incompleteness theorem states that if $\mathsf{ZF-Inf}$ is consistent, then $\mathsf{ZF-Inf} \nvdash \mathsf{Con(ZF-Inf)}$. Moreover, if $\mathsf{(ZF-Inf)} + \neg \mathsf{Con(ZF-Inf)}$ ...
3
votes
2answers
444 views

The Penrose–Lucas argument

I was looking at the Penrose–Lucas argument as discussed on Wikipedia. It states: In 1931, the mathematician and logician Kurt Gödel proved that any effectively generated theory capable of ...
0
votes
1answer
106 views

Godel's completeness theorem and formula that states consistency of ZF

Godel's completeness theorem, in original formulation, says that every logically valid statement/formula has finite deduction of a formula. Now then there is Godel's incompleteness theorem. Would this ...
2
votes
1answer
112 views

Expressibility of Gödel's Incompleteness Theorem

Can Gödel's Incompleteness Theorem be expressed as a formal sentence in ZFC and be proven formally or is it inherently meta-mathematical? (Note: I am referring to the theorem itself, not the ...
1
vote
2answers
50 views

Can two distinct formulae (or series of formulae) have the same Gödel number?

As I am studying Gödel's incompleteness theorem I am wondering if two distinct formulae or series of formulae can have the same Gödel number? Or the function mapping each formula or series of formulae ...
3
votes
1answer
118 views

Gödel's proof method and fundamental theorem of arithmetic

I am a novice to Gödel's proof (the theorem that consistency contradicts completeness), and, as it seems to me, he uses the fundamental theorem of arithmetic to uniquely number any formula. My ...
5
votes
1answer
93 views

If a statement holds for all standard models of PA, then does it hold for all models?

Suppose that $\varphi$ is a consequence of every standard model of PA. Then is it provable from PA?
-1
votes
2answers
254 views

Gödel incompleteness theorem [closed]

Gödel incompleteness theorem states that any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete.So what are some Gödel sentences about ...
0
votes
2answers
108 views

Scapegoat theory and PA

A theory T is scapegoat if for every formula A with only one free variable there exist a closed term s such that T proves: (∃x(¬A(x)))⇒¬A(s) I think it is an expectable property for each theory since ...
1
vote
0answers
66 views

What follows from Incompleteness about provability of partial correctness?

A colleague and I can't figure out what our professor is getting at with this question: What follows from the incompleteness theorems about the provability of partial correctness assertions? What ...
0
votes
2answers
254 views

Undecidable sentence in Godel's incompleteness theorem

In Godel's incompleteness theorem, the undecidable sentence is g: I am not provable. Ok. I accepted it and realized that in satandard interpretation it is true. So we found a true sentence which ...
3
votes
1answer
148 views

Non-self-referential undecidable sentences in arithmetic

Are there any known undecidable sentences for PA are neither "self-referential" (like a sentence equivalent to its own nonprovability) nor imply consistency of PA (like in the Paris Harrington ...
1
vote
5answers
227 views

Understanding ω-consistent and ω-incomplete theory

A theory $K$ is said to be $ω$-consistent if, for every formula $B(x)$ of $K$, if $﹁ B(n)$ is a theorem in $K$ for every natural number $n$, then it is not the case that $(∃x)B(x)$ is a theorem in ...
4
votes
3answers
291 views

Concrete example for diagonal lemma

Diagonal lemma says that in a theory with enough assumption for any formula $A(x)$ there exist a sentence $B$ such that $B$ $\iff$ $A(\#(B))$ is a theorem in that theory, in which $\#(B)$ represents ...
8
votes
1answer
296 views

How did Kurt Gödel's Incompleteness Theorem affect the mathematical world?

Hi I am looking not to understand the Incompleteness Theorem, but to find out more about how and what this has effected the mathematics world. I am in high school, in Honors Algebra II, and I am ...
2
votes
2answers
228 views

clarify the term “arithmetics” when talking about Gödel's incompleteness theorems

I am not quite sure what really is meant when talking about "arithmetics" in context of Gödel's incompleteness theorems. How I so far understand it: Gödel proved that every sufficiently powerful ...
4
votes
1answer
326 views

Under the impact of Gödel's incompleteness theorems, are the conclusions of statistics reliable?

After I read the Gödel's incompleteness theorems, I am confused about the following: Could you tell me if the conclusions of mathematical statistics are reliable? Gödel's incompleteness theorems ...
3
votes
2answers
200 views

Gödel's incompleteness theorems: where to learn? Is there a straightforward relation between the two?

What would be a good textbook or paper to learn the proofs of the two Gödel's incompleteness theorems from? I would prefer it to be as close to the original proofs as possible. I have not tried to ...
7
votes
2answers
433 views

Why doesn't “$V$ is a model of $ZF$” imply consistency of ZF?

One can prove that $V$, Von Neumann's universe, satisfies all of $ZF$ axioms, so it's a model of $ZF$. But I can't see why this doesn't imply the consistency of that theorem. I'm aware that ...
21
votes
2answers
2k 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
1answer
278 views

Is Douglas Hofstadter's version of Godel's proof utter nonsense?

Is Douglas Hofstadter's version of Godel's proof, which he offers in his book Godel, Escher, Bach, utter nonsense? Hofstadter goes to great length to disguise the fact that there are two distinct ...
3
votes
0answers
92 views

Maths, esp. Godel, and poetry

At the risk of being an interloper: I'm a poet with a bit of mathematical training. Right now I've got a grant from the Arts Council of Northern Ireland to write a collection (loosely) based on the ...
3
votes
2answers
127 views

If $T$ proves any incorrect $\forall$-rudimentary sentence, then $T$ is inconsistent

A theory $T$ in the language of arithmetic is called $\omega$-inconsistent if for some formula $F(x)$, $\exists x F(x)$ is a theorem of $T$, but so is $\neg F(n)$ for each natural number $n$. ...
1
vote
1answer
241 views

Must every decidable theory be axiomatizable?

Note: By "theory" I mean a set of sentences, not assumed to be closed under logical consequence (otherwise the question would be trivial). Comments/ideas: There's a well-known result that every ...
0
votes
1answer
95 views

Peano's theory of arithmetic and Gödel's 1st Incompleteness Theorem

Let $\mathcal{N}$ be Peano's 1st order theory of arithmetic and $\mathscr{A}$ it's standard model (which we assume exists). Infer from Gödel's 1st Incompleteness Theorem that there exists a closed ...
3
votes
1answer
109 views

Does second-order arithmetic (Z2) prove soundness and uniform reflection for first-order arithmetic (PA)?

(1) Does full second-order arithmetic (Z2) prove soundness and uniform reflection schemas for first-order arithmetic (PA)? That is, do we have for all formulas $\phi$: $$ \underset \phi \forall \; ...
2
votes
1answer
148 views

Con(PA) implies consistency of $\mathsf{PA}$ + ¬Con($\mathsf{PA}$)

The Wikipedia article for $\omega$-consistency says "Now, assuming PA is really consistent, it follows that $\mathsf{PA}$ + ¬Con($\mathsf{PA}$) is also consistent, for if it were not, then PA would ...
5
votes
2answers
221 views

Interaction of completeness and second incompleteness theorems

So I was reading the Wikipedia article on Godel's completeness theorem, the section on its relation to completeness. It says that completeness gives the existence of a model of arithmetic $\mathcal M ...
3
votes
1answer
79 views

The effects of requiring a recursive vs. a recursively enumberable axiomatization in the incompleteness theorem

I believe that the (paraphrased) original statement of Gödels first incompleteness theorem (including Rosser's trick) is If T is a sufficiently strong recursive axiomatization of the natural ...
1
vote
1answer
86 views

Logic soundness and completeness

I have to do a number of similar type questions, but I am having trouble grasping the general concepts around soundness and completeness. I have read up on the general definitions and think I ...
2
votes
2answers
147 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 ...
0
votes
1answer
53 views

Kolmogorov (Kolmogoroff-) Complexity, Contradiction with Invariance Theorem.

Fix some programming languages $S$ which is rich enough such that one can write interpreters for $S$ in $S$. Define $$ K(w) := \mbox{length of a shortest program producing $w$}. $$ Now fix some ...
3
votes
1answer
185 views

What other unprovable theorems are there? [duplicate]

Gödel's incompleteness theorem presents us with the possibility of having theorems that are neither provable nor disprovable in a given axiomatic set. Already we have the continuum hypothesis which ...
7
votes
2answers
806 views

Gödel's (in)completeness theorems and the axiomatization of Euclidean geometry

In David Hilbert's 1899 Grundlagen der Geometrie, Hilbert gives a rigorous axiomatization of Euclidean geometry. As I understand it, some of Hilbert's axioms must be expressed in second order logic ...
10
votes
1answer
212 views

What was the planned topic of Gödel's second paper on incompleteness?

Gödel's incompleteness theorems first appeared together in a paper titled (translated to English) "On formally undecidable propositions of Principia Mathematica and related systems I," with the Roman ...
1
vote
2answers
202 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
211 views

What does the completeness of a system mean for the provability of certain statments?

Through the 16th to 19th centuries mathematicians tried to prove the Euclids parallel postulate from Euclid's other four postulates. In the beginning of the 19th century the mathematics community ...
14
votes
2answers
2k views

Examples of statements which are true but not provable

Speaking informally and working, for example, in Peano Arithmetic (PA), we know that the essence of the Gödel's first incompleteness theorem is that there are true statements (in our model PA), which ...
0
votes
1answer
203 views

How can a statement be known to be undecidable in ZFC without ZFC being inconsistent?

I'm attempting to understand the answer to the question, Is there a statement whose undecidability is undecidable (as in independent, not a decision problem)? The answer appears to be "Yes". However, ...
9
votes
0answers
155 views

Elementary references on Robinson Arithmetic, Prim. Recursive fns etc.

I'm in the middle of revising my freely available and much-downloaded introductory notes Gödel Without (Too Many) Tears. (They are a sort of cut down version of part of my Gödel book, and I'm ...
2
votes
1answer
246 views

Any “natural” examples of true statements in number theory not provable in 2nd order systems?

I know that there are a few theorems in number theory that are somehow known to be true, but have been shown not to be provable in first-order Peano arithmetic (PA). Have any so-called "natural" ...
1
vote
2answers
91 views

Is this possibility ruled out by Godel's Incompleteness Theorem?

From Wikipedia: "The first incompleteness theorem states that no consistent system of axioms whose theorems can be listed by an "effective procedure" (e.g., a computer program, but it could be any ...
1
vote
1answer
155 views

Questions on a sentence in ZFC asserting that ZFC has a model

Question 1. Let $\operatorname{con}(\mathsf{ZFC})$ be a sentence in $\mathsf{ZFC}$ asserting that $\mathsf{ZFC}$ has a model. Let $S$ be the theory $\mathsf{ZFC}+\operatorname{con}(\mathsf{ZFC})$. ...