Questions about Gödel's incompleteness theorems and related topics.
Questions about Gödel's theorems and related topics.
Questions tagged [incompleteness]
868 questions
0
votes
1 answer
Can a second-order theory that contains the first-order theory of the structure (N,+,x,1) have a decidable axiomatization?
Hedman in his "A First Course in Logic" (2004) says, in p.359,
"... we now demonstrate a second-order theory containing $T_N$ that does have a decidable axiomatization." where $T_N$ is the first-order theory of arithmetic of the structure…
0
votes
0 answers
Are many generalized formula unprovable (related to Godel's first incompleteness theorem)?
Context: I've been reading through the Dover English translation of Godel's paper "On Formally Undecidable Propositions of Principia Mathematica and Related Systems".
It seems the key to producing Godel formulas is the generalization operation, such…
yters
- 35
0
votes
1 answer
Have a question regarding this introduction to Gödel foundations of mathematics/incompleteness theorem.
I am a math noob. These questions will likely sound dumb so I apologize ahead of time. But I like to code, and I've been getting into lisp languages. Someone wrote an introductory summary to Gödel foundations of mathematics/incompleteness theorem…
cphoover
- 101
0
votes
0 answers
How do we find mathematical equation of any statement which is not about mathematics with Gödel numbering?
I have 3 questions and they are closely related so I asked them in same post.
With Gödel numbering we can encode statements like "0 = 0" or maybe "a then b". And this is basically just transformation of symbols or group of symbols to a unique…
Muber17
- 1
0
votes
1 answer
Do any of you see any problems re the following reasoning about (1) Gödel’s first incompleteness theorem and (2) the Gödel-Penrose conjecture?
Gödel’s first incompleteness theorem (GT1) states that for every algorithmic set of axioms (AlgoS) capable of expressing basic arithmetic, there exists a true arithmetical statement GS (the Gödel statement of S) that AlgoS cannot prove. This…
0
votes
1 answer
Is Godel's G statement an arbitrary construction or is it derived by rules?
Godel's proof involves a statement G. I undestand that it is losely arranged to look like "This statement G is not provable in this sytem". My question is how this statement was created and used in Godel's proof. Is the statement just an…
Juel Herbranson
- 103
0
votes
1 answer
Can someone please help my differentiate Gödel’s 2 Incompleteness Theorems
Just a small note: I’m taking High School Geometry, so in no way am I advanced in mathematics.
Recently I’ve started a project attempting to explain Gödel’s incompleteness theorems. However I can’t seem to comprehend the difference between the 2…
0
votes
0 answers
Analogy between incompleteness theorem and infinite primes
I am self-learning about Godel's incompleteness theorems and think that this analogy is good:
When trying to prove that infinite primes exist we assume finite number of them exist and then we arrive at a number that cannot be built by those…
rajashekar
- 101
0
votes
1 answer
Godel's Incompleteness Theorems & the Laws of Thought
If Godel showed that a sufficiently powerful formal system can be consistent or complete but not both, is this equivalent to saying that the law of non-contradiction or the law of excluded middle cannot both hold within a system of logic.
I…
Bonj
- 75
0
votes
1 answer
The set of tuths depends on our assumptions of the world, so how can 'truth' be more fundamental than assumptions?
For example, we define 'what a set is' or 'what natural numbers are' using a bunch of assumptions about how they should behave. Those assumptions are all there is to the 'world or sets' or 'world of natural numbers'. So we cannot assert that a…
Ryder Rude
- 1,417
0
votes
1 answer
Incompleteness of Robinson Arithmetic Q and Goedel's theorem
I'm trying to understand the Goedel's theorem. My question is to check if the following thoughts are correct.
Goedel considers the formal sistem Q which describes natural numbers with addition and multiplication without any induction axioms. If we…
Emanuele Paolini
- 21,447
0
votes
1 answer
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 theorems of ZFC, and checking if that theorem either…
user623070
0
votes
0 answers
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, and effectively axiomatized) e.g. Peano…
draks ...
- 18,449
0
votes
1 answer
What does it mean to encode some statement in Theory of Natural Numbers $Th(\mathbb{N})$?
For example Godel's Incompleteness Theorem says "Some statement in $Th(\mathbb{N})$ has no proof".
Consider sentence "This sentence is not provable".
We can encode this sentence in $Th(\mathbb{N})$.
Thus, "This sentence is not provable" $ \in…
YanyongXu
- 81
0
votes
3 answers
Godel's incompletness theorem - proving a statement is false
I have two question regarding Godel's incompletness theorem. The theorem says that every axiomatic system is either incomplete or inconsistent. If it's consistent, then there are true statements that are unprovable.
If so, then it must also be the…
user4205580
- 2,083