All Questions

Tagged with
Filter by
Sorted by
Tagged with
1
vote
1answer
60 views

Why does one need to specify that the language is “well-orderable” for first order logic to be complete?

While reading Wikipedia I noticed the phrase "well-ordered language" in the following related to Gödel's completeness theorem: The completeness theorem then says that for any first-order theory T ...
0
votes
1answer
117 views

What is the relationship between computation and Gödel's incompleteness theorems? [closed]

In what way do Godel's incompleteness theorems impact computers/hypercomputers? Do they somehow prevent them from being capable of computing everything (of computing literally all uncomputable/...
8
votes
1answer
709 views

Gödel's incompleteness theorems - what are the religious implications?

Apparently Kurt Gödel believed that his incompleteness theorems have some kind of religious implications. Despite Gödel's belief in a personal God, this was still somewhat surprising to me. ...
7
votes
2answers
318 views

Is Propositional Logic Sound and Complete

After reading Gödel's incompleteness theorem, I wonder if there are any systems whose axioms are sound and complete. I realize that Gödel's arguments (at least from my sources) only apply to ...
3
votes
2answers
228 views

Gödel's incompleteness theorem and non-standard logics/foundational systems

I am amateur in the field of mathematical logic, so sorry for any confusing parts of this question. It is well known that Gödel's incompleteness theorem shows there are great limits to what first-...
5
votes
2answers
139 views

How is ω-consistency different from ordinary consistency?

I've read Gödel's explanation and others but my understanding is unclear. Answers to the followup questions below would help: does ω-consistency have any relevance to methods or ideas not connected ...
1
vote
0answers
45 views

Are semantic inferences between undecidable sentences in a system possible?

For example from the Gödel sentence "G iff ¬P([g])", where g is G's Gödel-number, is it possible to make semantic inference (not syntactic, only at the level of truth between the undecidable sentences ...
0
votes
1answer
501 views

Is it valid to prove the axioms of a system from themselves? How does it square with Gödel's incompleteness?

I recently asked whether the axioms are tautologies, and got comments that seemed to me highly suspicious. Namely, that you can always prove an axiom from itself, that you can trivially say A ...
2
votes
1answer
411 views

Existence as a predicate and Godel's ontological argument

I am referring to this paper https://github.com/FormalTheology/GoedelGod/blob/master/GodProof-ND.pdf which has formalized the ontological argument. If I am not mistaken, watered down, the argument ...
6
votes
3answers
829 views

Can you list examples of problems that can not be solved within a formal system but human beings have solved through construction or creativity?

This kind of problem is mentioned in a book I have read, but the book did not give a concrete example. If any such problem existed, this might help me understand human creativity. I think it would ...
5
votes
3answers
551 views

Gödel: Why is a proposition undecidable?

Gödel has proved the existence of undecidable propositions for any system of recursive axioms capable of formalizing arithmetic. But do we know the logical causes of this state of undecidability? In ...
3
votes
2answers
157 views

What motivated Gödel to arithmetize syntax?

What were the benefits of arithmetizing syntax for Gödel? What did the arithmetization of syntax allow for Gödel that was otherwise not possible?
9
votes
3answers
1k views

Was Kant anticipating Gödel's incompleteness in his antinomies?

Kant's attempts to prove that there's a limit to pure reason based on the existence of antinomies, i.e. pairs of propositions where each one is rational, but the propositions contradict each other. ...
10
votes
6answers
1k views

Does Gödel's argument that minds are more powerful than computers have the inconsistency loophole?

In "Raatikainen, P., 2005, “On the Philosophical Relevance of Gödel's Incompleteness Theorems,” , the author argues that Penrose's and others use of Gödel's theorem as an argument against mechanism (...
2
votes
6answers
820 views

If the ZFC axioms cannot be proven consistent, how can we say for certain that any theorems in mathematics have been proven?

The ZFC axioms are the basis of modern mathematics. But Gödel's 2nd Theorem says that it is impossible to prove that these axioms are consistent. Hence, it is possible (if ZFC is inconsistent) that ...
9
votes
1answer
336 views

Where did Gödel write that first-order logic is the “true” logic?

In "On How Logic Became First-Order" Matti Eklund writes (p. 2/148): It appears to be widely held today that arguments from Skolem and Kurt Gödel, both alleged proponents of the thesis that ...
1
vote
2answers
372 views

Are there any work around after Godel's incompleteness theorems?

It seems to me that mathematicians or computer science theorists are still trying to come up a proof for conjecture they made in first or second order logic. By Godel's incompleteness theorems there ...
0
votes
2answers
226 views

Regarding Godel's theorems

Given a formal logic system W with it's set of axioms, if it is capable of 'handling' basic arithmetic then W can not be used to 'prove' its own consistency. In other words there will always be a ...
3
votes
5answers
266 views

Provable and contradictory?

For each consistent formal theory T having the required small amount of number theory, the corresponding Gödel sentence G asserts: "G cannot be proved within the theory T". This interpretation of G ...
1
vote
3answers
515 views

Gödel's ontological proof and the incompleteness theorem

In Gödel's ontological proof, he concludes: "necessarily, God exists" (Theorem 4) Does Gödel's second incompleteness theorem apply to this proof?
4
votes
1answer
121 views

Does the finitary proof of the consistency of relevant PA shows that first order PA is irrelevant?

Relevance logic takes a closer look at the implication operation in first-order logic. It suggests that implications such as: p and not p -> q cannot hold; in ordinary English, an example of this ...
2
votes
2answers
174 views

Can we expand the notion of truth in Godels incompleteness theorem?

Godels incompleteness theorem, which really should be called the undecidability theorem given that the paper of Godels which this theorem is taken from is named 'On formally undecidable propositions ...
3
votes
3answers
485 views

What is the connection between provability logic & Gödel's first incompleteness theorem?

Provability logic is a modal logic that interprets the modal operator of K as provability and an additional axiom derived from Löb's theorem. Now the SEP shows that it's possible to derive Gödel's ...
3
votes
1answer
211 views

Is there a finitistic set theory, and if there is, is it provably consistent?

ZFC is the mainstream set theory. It has an axiom of infinity which claims that there is at least one infinite set. Now suppose like Aristotle, we object and say that there are no actually infinites ...
4
votes
1answer
700 views

What is the impact of paraconsistency on Gödel's theorem?

Russell's paradox forced a restriction of the natural abstraction principle (that every predicate determines a set) so that set theory could be consistent; the standard one being ZF. However ...
5
votes
2answers
613 views

Is Gödel's incompleteness theorem still valid if one uses a higher-order logic?

Gödel's incompleteness theorem is wholly formal (in my understanding), and relies on a proof system that I assume is first-order. Does it make any difference to the theorem if higher-order logic is ...
8
votes
1answer
562 views

In Gödels Incompleteness theorem what is the notion of truth?

The entry on Gödels Incompletenss theorem in Wikipedia says: Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete. In particular, for ...
4
votes
1answer
271 views

What happens when we drop the condition that proofs are finite strings of inferences in Gödel's incompleteness theorem?

Gödel's incompleteness theorem shows that there are sentences that are undecideable, that is they nor their negation can be proved. This theorem operates purely syntactically or formally, that it ...
28
votes
3answers
3k views

How is Gödel's incompleteness theorem interpreted in intuitionistic logic?

Classically, one sets up an axiomatic system with a formal deduction system & an interpretation in a model. Generally it is sound, that is: a formally deduced theorem is also true when interpreted ...
3
votes
3answers
203 views

Can we add to PA a new predicate T such that for every sentence A of the old vocabulary the new theory proves T(Godel numeric number of A) iff A

I am new to logic but I believe this is not a difficult problem, yet I am still soo confused, and the reason for that is because there are so many gaps in my knowledge or maybe I have overlooked so ...
12
votes
4answers
2k views

Gödel's theorem and God

I have seen it argued that Gödel's Incompleteness Theorems have implications regarding the existence of God. Arguments for the existence of God run mostly along the lines: "Because of Gödel's Theorem, ...
7
votes
6answers
1k views

What's the big deal with Gödel's second incompleteness theorem?

Edit: My question is specifically about Gödel's second incompleteness theorem. I get the significance of his first incompleteness theorem, which is of course completely amazing. According to the ...
3
votes
3answers
292 views

Do Gödel's incompleteness theorems support the idea that the examination of a 'system' should only be undertaken to arrive at the inconsistency?

Roughly, Gödel demonstrated that in a logical system, that contains a model or arithmetic, there are statements which may be true, but are unprovable within the system. If a statement is not ...
16
votes
1answer
3k views

When it is correct to use Tarski's undefinability theorem versus Gödel's incompleteness theorem?

Smullyan (1991, 2001) has argued forcefully that Tarski's undefinability theorem deserves much of the attention garnered by Gödel's incompleteness theorems. That the latter theorems have much to say ...
75
votes
8answers
11k views

Is Kurt Gödel's Incompleteness Theorem a “cheap trick”?

I found a throw-away critique of Kurt Gödel's Incompleteness Theorem in an essay about Deconstruction: The basic enterprise of contemporary literary criticism is actually quite simple. It is based on ...