Questions tagged [incompleteness]
Questions about Gödel's incompleteness theorems and related topics.
1
vote
1answer
37 views
Undecidable statement that doesn't involve infinity
All statements independent of ZFC I'm aware of involve infinity.
Do we know any statement independent of ZFC of the form $\forall n \in \mathbb{N}: P(n)$ where $P(n)$ is disprovable if false? (In ...
2
votes
1answer
52 views
Ordering between formal theories by provability of consistency
I am studying proof theory with Girard's monograph from '87 ('proof theory and logical complexity').
1.5.6. is an exercise called 'ordering between theories'.
It reads as follows:
" (i) Let $\...
1
vote
0answers
26 views
Are the HBL derivability conditions necessary for Gödel's incompleteness theorems? (For Löb's theorem?)
I am currently working with 'proof theory and logical complexity', a monograph on proof theory.
In the exercises of the first chapter one was asked to prove Löb's theorem (https://en.wikipedia.org/...
1
vote
1answer
81 views
An alternative formulation (or corollary) of Tarski's theorem? [Or just a typo?]
In my proof theory monograph (proof theory and logical complexity, Girard from '87) there is an exercise 1.5.4. on page 78 called 'Tarski's theorem'.
It says:
"Show that there is no truth predicate ...
0
votes
0answers
38 views
Why the 'natural' consistency proof of PA cannot be carried out $\textbf{in}$ PA
In my proof theory monograph there is this exercise:
"The natural proof of PA cannot be carried out in PA. Why?
(This proof consists in showing that all theorems of PA are ture.)"
Apparently, by '...
2
votes
0answers
57 views
Is every theory meeting Gödels incompleteness, also incomplete below its consistency level?
Is it always the case that for any theory $T$ that meets Godel's criteria for incompleteness, there is a sentence $P$ such that neither $T \vdash P$, nor $T\vdash \neg P$; and such that $T+P$ is equi-...
2
votes
1answer
37 views
Example of incomplete, but decidable theory, and of complete and undecidable theory, question
On wikipedia it is written that
Decidability should not be confused with completeness. For example, the theory of algebraically closed fields is decidable but incomplete, whereas the set of all ...
3
votes
2answers
83 views
How can a formal system ever be non-obviously unsound?
When reading about formal systems one is often warned that, even assuming the system is consistent, one can't be sure that any theorem proved in the system is actually true. For instance, if one can ...
15
votes
2answers
732 views
Gödel's completeness theorem and the undecidability of first-order logic
I'm working through this module, "Undecidability of First-Order Logic" and would love to talk about the two exercises given immediately after the statement of Godel's completeness theorem.
First, ...
3
votes
0answers
81 views
Recursion Theory/Incompleteness Theorems: Computability of sets of formulas in first order logic
I am struggling with the following two problems:
Suppose that $M$ is a structure with finite universe and finite alphabet. Show that the set of formulas $\{\varphi$ $\mid$ for every $M$-assignment $\...
2
votes
1answer
64 views
Why is $\forall x (x = x)$ an example of a first order sentence that is neither provable nor disprovable?
In the first answer to this question:
What is the difference between syntactic and semantic completeness?
the sentence $\forall x (x = x)$ is given as an example of something that is neither ...
17
votes
4answers
2k views
Why can't we prove consistency of ZFC like we can for PA?
this might be a silly question, but I was wondering: PA cannot prove its consistency by the incompleteness theorems, but we can "step outside" and exhibit a model of it, namely $\mathbb{N}$, so we ...
3
votes
2answers
87 views
Gödel's incompleteness 1: construction of the formula relating Gödel number of proof to Gödel number of proven statement
I'm trying to understand the proof sketch of Gödel's Incompleteness Theorem 1 on Wikipedia (https://en.wikipedia.org/wiki/Proof_sketch_for_G%C3%B6del%27s_first_incompleteness_theorem)
In particular, ...
2
votes
0answers
25 views
Can the Incompleteness Theorems be proven in the context of other logics, for example with Paraconsistent Logic?
And, if they cannot be proven, does anyone take this as a good argument to adopt the alternate logic?
0
votes
1answer
47 views
Reference textbook for Godel's incompleteness theorems proved in PRA or PA metatheory
I think one of my recent misunderstandings and confusions is about how can metatheory be PRA or PA if those are "formal theories". This confusion arose when I started reading Godel's theorem which ...
2
votes
1answer
105 views
Why Godel's theorem influences Hilbert's programme?
I have trouble understanding why it is being said that Godel's incompleteness theorem shows that Hilbert's programme is essentially impossible.
So, if I understand Godel's second incompleteness ...
2
votes
0answers
97 views
Proving fundamental theorem of arithmetic using primitive recursive functions
I am reading Kleene's "Introduction to Metamathematics" and in chapter 45 he mentions that "a given positive integer can be factored into a product of prime factors which is unique to within the order ...
2
votes
1answer
77 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
79 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
60 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
106 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
61 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
123 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?
7
votes
3answers
934 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.
...
24
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 ...
6
votes
1answer
171 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
268 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
55 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
113 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
110 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
100 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
90 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
81 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
53 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
65 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
91 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
85 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
83 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
179 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
51 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
126 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
49 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 ?
1
vote
2answers
99 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
91 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
85 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
57 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
71 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
99 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 ...
