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

learn more… | top users | synonyms

4
votes
2answers
84 views

Is it possible to prove that some point belongs to Mandelbrot set? Is this an example of Gödel's theorem?

Everybody knows about Mandelbrot set drawing computer programs. Program takes some point, builds sequence from it, and if found that sequence goes out of circle with 2 radius, then knows that this ...
0
votes
1answer
37 views

What does First Godel's Incompleteness theorem mean?

I am terribly confused what really "Incomplete" mean in terms of the Godel's theorem. Does it mean there are some theorems that are definable in First order theory of natural numbers and true but ...
1
vote
1answer
88 views

Uncountable reals in the theory

The Question I'm looking for a possibility to somehow proof the "essence" of Cantor's diagonal argument within a recursive first-order theory which is satisfied by the reals (better: within a theory ...
1
vote
0answers
27 views

Algorithm to force decidability of statements using an intuitionistic series of new axioms

Consider pairs $(\Phi,n)$ where $\Phi$ is a finite set of statements in Peano arithmetic and $n$ is an integer. Say that $p'=(\Phi',n')$ is an elementary intuitionistic extension of $p=(\Phi,n)$ iff ...
7
votes
0answers
102 views

Fixed points in computability and logic

I asked this question on CS.SE, too: http://cstheory.stackexchange.com/questions/27322/fixed-points-in-computability-and-logic I would like to understand better the relation between fixed point ...
4
votes
2answers
123 views

Is it possible to deduce Godel's first incompleteness theorem from Chaitin's incompleteness theorem?

I want to ask if it is possible to deduce Godel's first incompleteness theorem from Chaitin's incompleteness theorem. I am reading the following AMS-Notice article. The authors claim that: The ...
1
vote
1answer
35 views

Show that the metric $d_1$ on $C([0,1])$ does not give rise to a complete metric space. [duplicate]

Show that the metric $d_1$ on $C([0,1])$ does not give rise to a complete metric space. $$ d_1(f,g) = \int_0^1 |f(s)−g(s)| \, ds $$
0
votes
0answers
19 views

Questions about godel's first incompleteness theorem

I'd rather not get into the formal proof of godel's first incompleteness theorem. But I have 2 general questions. Looking at the statement from wikipedia: ...
1
vote
1answer
21 views

How can Goodstein's theorem be expressed in PA

I understand Goodstein's Theorem and its proof. I'm trying to understand the proof of why Goodstein's Theorem cannot be proved in PA. However, it's not immediately clear to me that Goodstein's Theorem ...
2
votes
1answer
88 views

True but unprovable?

I would like to ask a question about Gödel's Incompleteness Theorems which I've had in the back of my head for some time. Since I'm a student working in a completely different area of maths (my usual ...
4
votes
1answer
52 views

About Gödel's Incompleteness Theorem

A short time ago, I've been thinking about what statements in Number Theory are true but not provable. I've seen the proof of the Incompleteness Theorem (in the Gödel's works) and he gave an example ...
1
vote
1answer
58 views

Question about the incompleteness proof (Theorem V)

Question in short: Where do I find a complete proof of Theorem V from Gödels incompleteness proof? If it does not exists, can someone provide it? Question in detail: I am trying to understand ...
2
votes
1answer
122 views

Can unprovability unprovable? Is there an $\omega$-fold unprovability?

I was just thinking about unprovability. I just wanted to know if it is possible to make a concrete boundary between provable problems and unprovable problems in a certain axiomatic system. We know ...
3
votes
1answer
182 views

Problems with nesting proof predicates in first order logic.

Whenever I start nesting proof predicates, I always seems to run into these bizarre situations. I was wondering if anyone knows about this and could shed some light on it or provide me with some ...
4
votes
1answer
142 views

Proof of “If $ZFC$ proves there is an inaccessible cardinal, then $ZFC$ is inconsistent”.

Let $I$ be the statement "there is an inaccessible cardinal". I'm aware of two proofs of "If $ZFC\vdash I$ then $ZFC$ is inconsistent". One proof uses the Second Incompleteness Theorem, which I ...
1
vote
1answer
70 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
41 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
3answers
117 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
0answers
92 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 ...
8
votes
2answers
607 views

Godel Incompleteness Theorem

Is there any mechanism or algorithm where one can generate mathematical statements/problems that are undecidable, i.e their proof is independent, from a certain set of axioms ?
4
votes
1answer
86 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)}$ ...
0
votes
1answer
74 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
88 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
43 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 ...
2
votes
1answer
75 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 ...
15
votes
1answer
294 views

Could it be that Goldbach conjecture is undecidable?

The result closest to Goldbach conjecture is Chen's theorem [Sci. Sinica 16 157–176], the proposition ``1+2''. It is natural to ask if it is likely that under our arithmetic axioms the Goldbach ...
5
votes
1answer
77 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?
9
votes
1answer
190 views

Gödel's way of teaching non-standard models to Takeuti.

In Memoirs of a Proof Theorist, Gaisi Takeuti relates how Gödel taught him about nonstandard models in an "interesting" way: It went as follows. Let T be a theory with a nonstandard model. By ...
0
votes
1answer
56 views

particular property and completeness?

I was puzzeling with the almost standard definition of completeness: In mathematical logic and metalogic, a formal system is called complete with respect to a particular property if every formula ...
0
votes
0answers
36 views

Tensor Product of Hilbert Spaces: incomplete?

Let $\mathcal{H}$ be an infinite dimensional Hilbert space and $\mathcal{H}\otimes_0\mathcal{H}$ its algebraic twofold tensor product. Define a scalar product on it as ...
1
vote
1answer
107 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
66 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 ...
2
votes
2answers
115 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 ...
1
vote
0answers
37 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
144 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 ...
0
votes
2answers
94 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 ...
0
votes
5answers
118 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
202 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
149 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 ...
-4
votes
2answers
78 views

How is Goedel's 1st incompleteness theorem related to the Axioms of a theory

i am thinking of various connections and formulations of Goedel's 1st incompleteness theorem. Apart from connections to Turing's Halting Problem and Algorithmic Complexity Theory, i am looking for ...
4
votes
2answers
246 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 ...
1
vote
1answer
170 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 ...
2
votes
0answers
47 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
101 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$. ...
3
votes
2answers
135 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 ...
5
votes
2answers
152 views

Modern book on Gödel's incompleteness theorems in all technical details

Is there a modern book on Gödel's incompleteness theorems that goes into each and every technical aspect of the proof of them (a classical one, if such exists)? I'm not interested in popular ...
1
vote
1answer
91 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
86 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 ...
2
votes
1answer
66 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
77 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 ...