Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

Questions tagged [incompleteness]

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

-3
votes
1answer
50 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
82 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
90 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
0answers
66 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
56 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
74 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
45 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
60 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
81 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
70 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
76 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 ...
11
votes
1answer
129 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
46 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 ...
4
votes
2answers
112 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
43 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
52 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
88 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
78 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
64 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
52 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
67 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
40 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
82 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
33 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" ...
3
votes
1answer
104 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
66 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
66 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
55 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
58 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
160 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
79 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
72 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
108 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,...
1
vote
2answers
31 views

A statement in second-order-arithmetic which proves second-order-arithmetic consistency

Is there a statement in second order arithmetic which it's truth proves the consistency of second order arithmetic? Note that if such statement exists it must be unprovable in second order arithmetic.
0
votes
1answer
41 views

Language of an Axiomatic System in the Incompleteness Theorem

From wikipedia, the statement of Gödel's First Incompleteness Theorem is : "Any consistent formal system F within which a certain amount of elementary arithmetic can be carried out is incomplete; i.e....
9
votes
1answer
390 views

What is finitistic reasoning?

I have been looking at various introductions to Hilbert's program, and they all use the concept of finitistic reasoning. What is precisely finitistic reasoning, and what would be an example of non-...
-1
votes
1answer
42 views

How simple it can be? [closed]

My dream axiom system is only the integers with the usual addition axioms (commutative, associative), and with induction. a) does it have a name, b) can I show define ab, and show ab=ba in this system?...
0
votes
1answer
65 views

Is it possible to construct a formal system such that all interesting statements from ZFC can be proven within the system?

I'm familiar with Godel's incompleteness theorem, which very basically states that there exists a statement that can be neither proved or disproved within a formal system powerful enough to include ...
0
votes
2answers
156 views

Incompleteness Theorem gives a contradiction?

We know two things (two smart people told me these) : 1.) Gödel's famous Incompleteness Theorem can be established (proved) using the ZFC axiom system. In particular, there exists an undecidable ...
0
votes
1answer
51 views

Can all unprovable statements in a given mathematical theory be determined with the addition of a finite number of new axioms?

This question is related to Godel's incompleteness theorem, which states that no sufficiently complex formal system can be both consistent and complete. Is it possible to add axioms to a formal ...
2
votes
1answer
78 views

A tricky proof of a Diophantine equation is valid?

Statement F. $\ a^n+b^n+c^n=d^n$ has no positive integer solutions $a,b,c,d$ for any $n=3,4,5,...$. (Please don't comment on whether or not Statement F is true!) $Suppose$ I proved in the Gödel-...
1
vote
0answers
68 views

First Incompleteness Theorem made exact…

First Incompleteness Theorem, according to WIKIpedia: "Any consistent formal system F within which a certain amount of elementary arithmetic can be carried out is incomplete; i.e., there are ...
31
votes
2answers
2k views

What axioms Gödel is using, if any?

Gödel states and proves his celebrated Incompleteness Theorem (which is a statement about all axiom systems). What is his own axiom system of choice? ZF, ZFC, Peano or what? He surely needs one, doesn'...