Questions tagged [incompleteness]
Questions about Gödel's incompleteness theorems and related topics.
0
votes
2answers
59 views
Can sets be constructed in ZFC using possibly undecidable conditions?
Let $P$ denote the set of all prime numbers, $E$ the set of even numbers greater than 2, and $$X:=\{e\in E \,\,|\,\, \exists x,y\in P: x+y=e \}.$$
Note that if Goldbach’s conjecture (that all even ...
0
votes
1answer
38 views
Are there alternative formalizations of consistency that bypass the Second Incompleteness Theorem?
Gödel's Second Incompleteness Theorem expresses the consistency of a formal system within the system itself using a rather carefully designed proof checking predicate. The conclusion of Gödel's ...
1
vote
0answers
36 views
Incompleteness of Robinson's Arithmetic
In Smith's book about Godel's Theorems a proof is given of incompleteness of Robinson Arithmetic. It's done by producing a special interpretation of the theory:
Domain is $N^* = N \cup \{a,b\}$, a ...
0
votes
1answer
52 views
Consistency and Gödel's Incompleteness theorem.
In Mathematical Logic, Kleene states a string of implications that are a result of Gödel's completeness theorem of predicate logic;
$$\{E_1,...,E_k \vdash P\&\neg{P}\} \rightarrow \{E_1,...,E_k \...
0
votes
1answer
100 views
Why doesn't the construction of $\mathbb{N}$ through ordinals in ZFC violate Gödel's Incompleteness Theorem?
The title kind of says it all. I've been working through Axiomatic Set Theory, Suppes and Mathematical Logic, Kleene. And I haven't thoroughly studied ordinals and incompleteness yet. But, ...
0
votes
0answers
8 views
Can completeness due to adding $\omega$-rule be extended to all recursive ordinals?
Is completeness due to $\omega$-rule effected by restricting matters to what the meta-theoretic indices confer? I mean in the case of the ordinary $\omega$-rule, we can do it over the world of finite ...
0
votes
1answer
18 views
Using the halting problem to create statement independent of ZFC
The proof of the halting problem gives us a way to create, for any halting algorithm, a program that the halting algorithm does not decide.
One possible halting algorithm would be enumerating all ...
0
votes
1answer
62 views
How does Godel use diagonalization to prove the 1st incompleteness theorem?
I'm looking for an intuitive explanation of this without too much jargon as I am new to set theory. I understand Cantor's diagonal proof as well as the basic idea of 'this statement cannot be proved ...
-1
votes
1answer
59 views
What decides completability of a first order theory?
[EDIT]: To make the question (the original posting presenting it I've put in a separate section below) non trivial a definition of "inference rule" needs to be given [Noah Schweber] as clearly ...
2
votes
0answers
81 views
Does probability theory suffer from Gödel's incompleteness theorem?
Let us consider the following two theorems by Gödel:
1) Any consistent formal system $F$ within which a certain amount of elementary arithmetic can be carried out is incomplete; i.e., there are ...
-1
votes
2answers
121 views
Proof of Godel's Incompleteness Theorem based on Recursion Theorem
I'm looking for a proof of Godel's Incompleteness Problems based on the recursion theorem in computability theory. I've skimmed lots of textbooks but I haven't found such proof. Can you name some ...
0
votes
0answers
119 views
A Growing Tree of Theories
Gödel' Incompleteness Theorem (GIT) states that certain theories $T$ (formal systems that are of sufficient complexity to express the basic arithmetic of the natural numbers and which are consistent, ...
1
vote
1answer
109 views
Legitimacy of Consistency Proofs
In this question I asked yesterday I put forward two interpretations of a statements such as "System X is consistent". (a) we can think of it as saying no finite sequence of applications of logical ...
3
votes
1answer
103 views
Consistency of PA from a Formalist Perspective
In this lengthy thread there's people bickering back and forth about the consistency of PA (Peano Arithmetic) and misunderstandings abound. In reading it I came to an understanding I found useful, ...
3
votes
0answers
74 views
Godel's theorem incompleteness, truth vs.provability
I know this question has been investigated in other threads, but I would like to pose yet another question on Gödel's theorem incompleteness, and truth in 'the standard model' compared with ...
3
votes
1answer
53 views
Several questions about the incompleteness theorem
I’ve read quite a few pop math books over the years with descriptions of the incompleteness theorem and I think I understand most of the broad details, but some still elude me. Specifically, these ...
2
votes
1answer
107 views
What is the purpose of Semantics/Model theory in Mathematical Foundations?
First off I know very little model theory so apologies if I say anything very dumb or offensive to logicians/model theorists. Second I should note that a lot of what I am saying here is motivated by ...
3
votes
1answer
58 views
Why is $\{\#F\mid\mathcal{N}\models F \text{ and $F$ is an $\exists$-formula} \}$ a recursive set?
Let $\mathcal{N}=(\mathbb{N},+,\cdot,0,1)$. I want to show that $\{\#F\mid\mathcal{N}\models F \text{ and $F$ is an $\exists$-formula} \}$ is a recursive set. Here $\#F$ is the Gödel number of $F$ and ...
1
vote
1answer
33 views
Gödel diagonalization and formulas not holding for themselves
Is there a formula $\varphi (n)$ in one free variable $n$ in ZFC (PA etc.) such that for every formula $\psi(n)$ in one variable the equivalence
$$ \varphi ( \ulcorner\psi\urcorner) \leftrightarrow \...
1
vote
1answer
64 views
What was the exact form of Gödel's original Second Incompleteness Theorem?
Gödel's second incompleteness theorem is usually stated as:
Any consistent formal system $F$ capable of elementary arithmetic can't prove its own consistency.
I'm having trouble deducing this ...
2
votes
0answers
110 views
n-consistency - provability/truth of $\Sigma^0_n$ and $\Pi^0_{n+1}$ -formulas; n-consistent extensions, etc.
I am facing difficulties with the following exercise.
(It is 1.5.9. from 'proof theory and logical complexity', Girard, '87)
(i) T is $\textbf{n-consistent} \ (n>0)$ if any $\Sigma^0_n$ - theorem ...
0
votes
1answer
82 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
69 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
43 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
95 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 ...
1
vote
0answers
108 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
62 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
63 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
107 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
774 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
89 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
73 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
91 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
54 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
119 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
105 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
78 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
81 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
68 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
109 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
68 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
160 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
957 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
210 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
384 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
57 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
116 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 ...
