# Tagged Questions

72 views

### If $T$ proves any incorrect $\forall$-rudimentary sentence, then $T$ is inconsistent

A theory $T$ in the language of arithmetic is called $\omega$-inconsistent if for some formula $F(x)$, $\exists x F(x)$ is a theorem of $T$, but so is $\neg F(n)$ for each natural number $n$. ...
90 views

### Gödel's incompleteness theorems: where to learn? Is there a straightforward relation between the two?

What would be a good textbook or paper to learn the proofs of the two Gödel's incompleteness theorems from? I would prefer it to be as close to the original proofs as possible. I have not tried to ...
113 views

### Modern book on Gödel's incompleteness theorems in all technical details

Is there a modern book on Gödel's incompleteness theorems that goes into each and every technical aspect of the proof of them (a classical one, if such exists)? I'm not interested in popular ...
60 views

### Must every decidable theory be axiomatizable?

Note: By "theory" I mean a set of sentences, not assumed to be closed under logical consequence (otherwise the question would be trivial). Comments/ideas: There's a well-known result that every ...
71 views

### Peano's theory of arithmetic and Gödel's 1st Incompleteness Theorem

Let $\mathcal{N}$ be Peano's 1st order theory of arithmetic and $\mathscr{A}$ it's standard model (which we assume exists). Infer from Gödel's 1st Incompleteness Theorem that there exists a closed ...
40 views

123 views

### Problem with completeness theorem and $\mathsf{Con(ZFC)}$

Using the reflection theorem we can prove in $\mathsf{ZFC}$ that for any finite $\Lambda\subseteq\mathsf{ZFC}$ there is some limit ordinal $\gamma$ such that $R(\gamma)\models\Lambda$. Then by the ...
51 views

### Are forcing techniques possible to automate for mechanized reasoning?

Looking at Cohen's success at proving independence of the Axiom of Choice and the Continuum Hypothesis, I was wondering if it was possible to mechanize forcing techniques for the purpose of proving ...
158 views

### What is the notion of truth used in Godels incompleteness theorem?

First-order logic is complete & sound. The notion of truth used here is model-theoretic. Informally Godels incompleteness theorem says that for a sufficiently strong formal language there are ...
64 views

### Completeness condition in Gödel first incompleteness theorem superflous

Wikipedia says: Theory is complete if it is a maximal consistent set of sentences. Than it says: Any effectively generated theory capable of expressing elementary arithmetic cannot be both ...
80 views

### Looking for counterexamples where the output of a computable function always has a computably checkable property, but PA cannot prove this

Suppose we have a computable function $f$, say over the naturals, and a decidable set $S$ of naturals, such that $f(x) \in S$ for all $x$. In this case, for any specific $x$, there is some specific ...
629 views

### Examples of statements which are true but not provable

Speaking informally and working, for example, in Peano Arithmetic (PA), we know that the essence of the Gödel's first incompleteness theorem is that there are true statements (in our model PA), which ...
219 views

### $\omega$-consistency and related terms

We know that a theory $T$ is $\omega$-inconsistent if there is a formula $\psi$ such that $T$ proves $(\exists x)\psi(x)$, and $T$ also proves $\lnot \psi(n)$ separately for each standard natural ...
74 views

### In Godel's first incompleteness theorem, what is the appropriate notion of interpretation function?

Wikipedia states Godel's first incompleteness as follows. Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete. In particular, for ...
533 views

### Are (some) axioms “unprovable truths” of Godel's Incompleteness Theorem?

Like any math newbie, Godel's Incompleteness Theorems are easy to understand in general layman's terms, but difficult to understand beyond the typical "liar's paradox" and "barber's paradox" type ...
417 views

### Where, specifically, did Principia Mathematica fail?

I'm very fascinated by the book Principia Mathematica. From what I've learned so far, Principia Mathematica set out to be, essentially, the bible of mathematics and logic, from which all mathematical ...
98 views

### On consistency of axiomatic systems

Can an axiomatic system (which is capable of expressing arithmetic) be complete and consistent? Let me explain my motivation a little bit (though it can be a kind of a mess...) I'm aware of Goedel's ...
119 views

### Running programs in nonstandard models of PA

I came across the following problem in several places, to paraphrase: Let $T$ be a recursively axiomatizable, consistent extension of PA. Then there exists some $e$ such that the $e'$th program ...
5k views

### Can someone explain Gödel's incompleteness theorems in layman terms?

Can you explain it in a fathomable way at high school level?
173 views

### Are the Godel's incompleteness theorems valid for both classical and intuitionistic logic?

I am studying an undergraduate text about math logic. The proofs of the two Godel's incompleteness theorems are not completely formal: they are admittedly simpler that the real proofs. For what I ...
191 views

### Proving and understanding the Fixed point lemma (Diagonal Lemma) in Logic - used in proof of Godel's incompleteness theorem

http://en.wikipedia.org/wiki/Diagonal_lemma I am wondering about the proof of the "Fixed-Point Lemma" $\text{Mod } \Sigma$ is the class of all models of $\Sigma$. $\text{Th Mod } \Sigma$ is the set ...
145 views

### How to prove primitive recursive functions are definable in Peano Arithmetic?

Background: I'm working on a talk that presents Godel's first Incompleteness Theorem from a computability-theoretic perspective. The idea is to show that the first incompleteness theorem follows from ...
294 views

### Don't Gödel's completeness and incompleteness theorems contradict each other? [duplicate]

Gödel's completeness theorem: Given a set of axioms, if we cannot derive a contradiction, then the system of axioms must be consistent. Gödel's incompleteness theorem:'Given any consistent, ...
93 views

### Incompleteness theorem and $\mathbb{L}$.

Let $\alpha > \omega$ and $u = \{\ulcorner \sigma \urcorner : \sigma \in \mathrm{Th}(\mathbb{L}_\alpha, \in)\} \subseteq \omega$, where by $\mathbb{L}_\alpha$ we denote as usual the constructible ...