All Questions

Tagged with
35 questions
Filter by
Sorted by
Tagged with
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 ...
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/...
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. ...
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 ...
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-...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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?
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. ...
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 (...
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 ...
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 ...
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 ...
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 ...
266 views

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 ...
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?
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
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 ...