Questions tagged [incompleteness]
Questions about Gödel's incompleteness theorems and related topics.
2
votes
1answer
65 views
How can any proof of Gödel's incompleteness theorem be accepted considering systems of mathematics themselves are incomplete?
I believe there are at least several proofs of Gödel's incompleteness theorem. Nagel and Newman wrote a book (1958) that presents one in particular.
But considering the theorem itself exposes ...
2
votes
1answer
69 views
Is this “Simple Proof of Godel's Theorems” assuming some form of the Axiom of Choice?
I found this paper as a first result in Google after searching for "godel theorem proof".
On page 3:
Let $B_1(n), \,B_2(n), \,\dots$ be an enumeration of all formulas in $\mathcal{N}$ having ...
2
votes
1answer
54 views
Usefulness of Gödel's incompleteness theorem
Given a first-order language $L$ and a theory $T$ in that language (a set of formulas of $L$), if $T$ is strong enough to prove arithmetic, then Gödel's second incompleteness theorem tells us that $T$ ...
2
votes
1answer
103 views
How to prove a generalized version of Gödel's Second Incompleteness Theorem?
Let's start from Gödel's Second Incompleteness Theorem (GST) in the following form:
If $\mathcal{T}$ is a consistent, recursively axiomatizable first order theory that contains $\mathsf{PA}$ as a ...
3
votes
0answers
57 views
Are there any simple explicit examples of formal systems which prove their own consistency?
Godel's first incompleteness theorem states roughly that you can't write down a finite list of axioms that can decide all statements about arithmetic: any such formal system is incomplete. I feel like ...
-2
votes
2answers
104 views
Does Gödel's incompleteness theorem invoke a Law of Excluded Middle contradiction? [closed]
Does Gödel's incompleteness theorem cause the Law of Non Contradiction to contradict its self?
If so, would this be a considered a conjecture?
6
votes
3answers
914 views
George Boolos and Gödel's Second Incompleteness Theorem
In Mind, Vol. 103, January 1994, pp. 1-3, George Boolos wrote:
And so on. In fact, if a claim can be proved, then it can be proved
that the claim can be proved. And that too can be proved.
...
23
votes
6answers
3k views
Is consistency an axiom of mathematics?
I watched the numberphile video on Gödel's Incompleteness Theorem today, and I was wondering about something.
It seems the key to accepting the truth of Gödel's Theorem is to demand that mathematics ...
5
votes
1answer
127 views
Is Fermat's last theorem provable in Peano arithmetic?
The sentence $S$ which Gödel in his proof of the incompleteness theorem proves to be be unprovable in the system of Peano arithmetic can be proved (as a true theorem of PA) outside PA (and necessarily ...
-2
votes
1answer
169 views
I want a simple example of Gödel's incompleteness theorems as it applies to Mathematics [closed]
I want a simple example of Gödel's incompleteness theorems as it applies to Mathematics. I am looking for an example not a proof. If possible a simple example that involves little Mathematical ...
-3
votes
1answer
54 views
Is there a statement which can not be proved in any axiom systems
As we know a statement may not be proved in some axiom system according to the godel incompleteness theory, can we always solve it by some way that change the axiom system?
2
votes
1answer
99 views
Goedel's first incompleteness theorem, the omega rule, and Tennant's reflection rule
Typical discussions of Goedel's first incompleteness theorem note that PA can prove of each integer that it doesn't number the proof of the Goedel sentence $G$. They then note that using an omega rule ...
0
votes
1answer
104 views
Can an error be found in this proof of Gödel's incompleteness theorem?
Can you find a division by zero error in the following short proof of Gödel's incompleteness theorem?
First a little background. $\text{G($a$)}$ returns the Gödel number of the formula $a$. As in ...
3
votes
1answer
92 views
Is Godel's incompleteness theorem unavoidable?
So after Godel's Incompleteness theorem and the fact that some theorems mathematicians are interested in are independent of ZFC (e.g. Continuum Hypothesis) is there some hope for some other ...
2
votes
1answer
78 views
What if someone comes up with a proof of consistency of arithmetic under the following conditions?
Suppose that one day, someone comes up with a proof of consistency of Peano arithmetic (PA) within itself. Then, does it mean that PA is actually inconsistent? Because, by the Gödel's incompleteness ...
2
votes
0answers
78 views
Minimal axioms necessary to prove the incompleteness theorems?
What's the minimal sufficient (plausibly) consistent system of axioms to prove the First incompleteness theorem? More interestingly can the First incompleteness theorem be proved in a consistent self-...
7
votes
7answers
3k views
Does it follow from Gödel's theorem that this world cannot be fully described by math?
What are the flaws in the following reasoning?
By Gödel's theorem, for any non-contradictory formal system $F$, at least as complex as ordinary arithmetic, there exists a true statement $G(F)$ (or ...
2
votes
2answers
47 views
Incomplete theory proving its incompleteness by a formula neither provable true nor false in the theory
Would it be possible that an incomplete theory had a formula that proved its incompleteness, but that same formula belonged to the set of formulae of that theory that can't be proven true or false, so ...
2
votes
0answers
62 views
Do Tarski's Axioms prove all of Euclid's Elements? [duplicate]
A fairly self explanatory title; do Tarski's first order axioms given in his famous 'What is Elementary Geometry?' Suffice to prove all of the theorems in Euclid's Elements? (Excluded non-plane ...
1
vote
1answer
86 views
Understanding variable replacement in Gödel's Incompleteness Theorem
I am a High School student and I am doing a school work on the Fundamentals of Math and in the moment I am reading Gödel’s 1931 article On Formally Undecidable Propositions.
I am having a great ...
2
votes
1answer
80 views
How do mathematicians know the problems they're trying to solve are not undecidable?
I'm not a mathematician so apologies if this question makes no sense.
My understanding of modern mathematics is that it is built on a set of axioms known as Zermelo–Fraenkel set theory + the axiom of ...
0
votes
1answer
81 views
What do the Incompleteness theorems really say about the inexhaustibility of mathematics.
It seems that Godel himself believed that the incompleteness theorems seem to imply the inexhaustibility of mathematics; since he states you can simply add the consistency statement of the system as a ...
13
votes
1answer
173 views
On the clarification of Manin's remark about Gödel’s incompleteness theorems
In his paper Georg Cantor and his heritage Yuri I. Manin writes (see page 7, 3rd paragraph),
Baffling discoveries such as Gödel’s incompleteness of arithmetics
lose some of their mystery once one ...
1
vote
1answer
48 views
$\Sigma\subset Th(\mathbb{N})$ is finite, so $\Sigma$ has $2^{\aleph_0}$ non-isomorphic models
I want to prove the statement in the title using Godel's theorems.
Without Godel's theorem, I may use the theorem about infinite model from cardinality $\kappa$ $\Rightarrow$ infinite models from any ...
5
votes
2answers
123 views
Negative Numbers and Gödel’s Incompleteness Theorem
I was examining Q (Robinson Arithmetic) when it occurred to me that Q contains no statements about the negative numbers or subtraction. No resource that I’ve been able to find has discussed Gödel’s ...
2
votes
0answers
46 views
Do we need to go in meta-theory for proving completeness?
Do I need to go in some meta-theory A for proving theory B is complete ? Or can I do it inside the theory B ? If I really need it, what is the reason for that ?
2
votes
0answers
56 views
Multiplication in Presburger Arithmetic [duplicate]
In Presburger Arithmetic multiplication is not an axiom. Why does defining multiplication by repeated addition not affect its status as complete? Is there better definition that you can make of ...
1
vote
2answers
91 views
True yet unprovable statement?
I have recently been studying Godel's Incompleteness Theorem. I am completely new to the study of logic, so I have been working to break down each component. Assuming I've understood the theorem ...
2
votes
1answer
83 views
Can a theory be consistent but not $\omega$ consistent?
Say we have an axiomatizable theory $T$ extending $Th(A_E)$ where $A_E$ are the axioms of arithmetic. Is it possible to extend $T$ such that our extended theory is consistent but not $\omega$-...
5
votes
1answer
72 views
Every Turing machine corresponds to a formal system
Solomon Feferman, at page 138 of his 2006 paper "Are there absolutely unsolvable problems" says that each formal system of axioms can be made to correspond to a suitably designed Turing machine so ...
0
votes
1answer
54 views
Proving the impossibility of a proof
Given that according to Gödel's theorems there are propositions in any language equivalent to first order logic that cannot be proven right or wrong, is it possible to prove that some of such ...
1
vote
2answers
70 views
expression that cannot be “written down” re: incompleteness, logic
I apologize for the poor title.
We are given a computer that writes down only expressions that are true. Let $\omega$ be an expression. Define the composition C of $\omega$ as $\omega(\omega)$. We ...
3
votes
1answer
44 views
How to understand Smullyan's notion of weakly adequate Gödel numbering
I was working on Smullyan's Diagonalization and Self-Reference (1994). In Chapter 9 (p.168), he defines the notion of a weakly adequate Gödel numbering as follows:
Let $\mathscr{L}$ be a first-...
0
votes
1answer
92 views
Is First Order Logic + Arithmetic semi-decidable?
I understand that it is not complete, but is it decidable, semidecidable or not decidable? Also, does something have to be complete for it to be considered decidable or semidecidable? Meaning, can ...
2
votes
1answer
36 views
Categoricity of categorical arithmetic
Consider the elementary theory of the category of sets (ETCS). Inside this framework, we have that $(\mathbb N, 0, s)$ is a natural number objet and that :
it is a model of the Peano axioms,
it is ...
18
votes
5answers
3k views
With this definition of completeness, Gödel's Incompleteness result seems not surprising, so why it was back then?
According to wikipedia a theory (i.e. a set of sentences) is complete iff for every formula either it, or its negation, is provable.
On the other side, a logic is complete iff "semantically valid" ...
4
votes
1answer
108 views
Are statements of arithmetic without logical negation or existential quantifiers decidable?
Consider the set of statements of arithmetic, such that:
the statement contains no existential quantifiers, only universal quantifiers;
the statement contains only logical ...
0
votes
1answer
22 views
Supplementing $L_A$ with new function symbols
I'm working on this homework problem:
We know that all primitive recursive formulas can be expressed in $L_A$. We could have just define new function symbols for them then, to save space. Show that ...
0
votes
1answer
81 views
Is the set of primitive recursive functions (on $\mathbb{N}$) effectively enumerable?
My intuition says that the set of PR functions on $\mathbb{N}$ are not effectively enumerable. I'm trying to come up with a diagonal argument to show this.
Suppose that $f_1,f_2,...$ was an ...
0
votes
1answer
57 views
“Un-coordinatable” Spaces
Recently, I have been considering incompleteness in many different contexts - I'm sure many would agree that incompleteness evidently arises in contexts where certain structures gain sufficient ...
3
votes
1answer
74 views
Are there “structure-specific” logical axiomatic systems? Do these have extra power?
I suspect that it will be hard to correctly convey this question, but here goes:
How its normally done:
The way I've been taught, and what is normally done in mathematical logic, is as follows:
We ...
17
votes
4answers
2k views
What's wrong with this “proof” that Gödel's first incompleteness theorem is wrong?
Edit: I've added an answer myself, based on the other answers and comments.
Here is a very very informal "proof" (sketch) that Gödel's theorem is wrong (or at least that the idea of the proof is ...
0
votes
1answer
60 views
Does Gödel's theorem rule out derivations from all possible logical systems or just first-order logic?
Gödel's first incompleteness theorem excludes the possibility of formulating a consistent and decidable set of first order sentences which are true in standard arithmetic from which the truth/...
1
vote
0answers
60 views
Alternative approach in self-referential step of the proof of Gödel's first incompleteness theorem
I have read the Proof sketch for Gödel's first incompleteness theorem on Wikipedia and do some contemplation about it. Then I was wondering about the self-referential step of the proof.
The proof ...
5
votes
1answer
179 views
Gödel's second incompleteness theorems
Usually Gödel's second incompleteness theorem is interpreted thus: "No sufficiently strong formal theory can prove its own consistency, assuming it is consistent", but in the book Per Lindstroem "...
1
vote
1answer
85 views
Existence of an inner model of ZFC implies $Con(ZFC)$?
The question arise from a statement that I have heard a lot "ZFC cannot prove the existence of a model of itself by Godel's 2nd incompleteness theorem", in particular referred to the existence of ...
0
votes
2answers
85 views
Why does incompleteness not imply consistency?
A very simple question about the relationship between incompleteness and consistency of any theory strong enough to express PA.
We know from Gödel that if such a theory is consistent, then it is ...
-2
votes
1answer
101 views
Write a relatively simple, recursive claim in arithmetic which is equivalent to Tarski's indefinability of truth
Write a relatively simple, recursive claim in arithmetic which is equivalent to defining truth.
For example: Define $f(x):\Bbb{N}\to\Bbb{N}$ such that if we set:
$x_{n+1}=f(x_n)$
Then any proof of ...
14
votes
5answers
2k views
How can we know we're not accidentally talking about non-standard integers?
This question is mostly from pure curiosity.
We know that any formal system cannot completely pin down the natural numbers. So regardless of whether we're reasoning in PA or ZFC or something else, ...
3
votes
1answer
124 views
How/why does Gödel's incompletness theorem apply to set theory?
Set theory in the usual first order axiomatization, as far as I understand, is powerful enough to construct structures that satisfy the axioms of the second order axiomatization for naturals, integers,...
