Skip to main content
16 votes
Accepted

Confusion about Löb's theorem

Say that the formal system is $\sf PA + \lnot Con(PA).$ Then the system proves every statement is provable in $\sf PA$, but surely it doesn't prove every statement (unless it is inconsistent, which by ...
spaceisdarkgreen's user avatar
12 votes
Accepted

Formally how do we view finite sets

This is actually very subtle, in fact IMO one of the most underrated subtleties to come out of mathematical logic. To get the unsurprising part out of the way first, the way we do it is, as you ...
spaceisdarkgreen's user avatar
11 votes
Accepted

PA + "(PA + this axiom) is consistent"

Actually, whipping up a self-referential axiom isn't difficult at all; the real issue is that doing so in the way you want just produces an inconsistent system. We can indeed produce a sentence $\...
Noah Schweber's user avatar
10 votes

Allegedly: the existence of a natural number and successors does not imply, without the Axiom of Infinity, the existence of an infinite set.

As noted in the comments, the structure ($V_\omega$, $\in$) satifies all the axioms of ZFC except for the axiom of existence of an inductive set, and moreover every object of it is finite under all (...
ac15's user avatar
  • 1,084
8 votes

Confusion about Löb's theorem

If you prove the Riemann hypothesis, then before believing that the Riemann hypothesis is true, I'd ask you what assumptions (axioms) you used in the proof. If you used any false assumptions, I won't ...
Andreas Blass's user avatar
8 votes
Accepted

What are the parameter-free definable elements of a model of Peano Arithemetic?

Nope, this is very false! For example, suppose $M\models\neg Con(\mathsf{PA})$. Then there is an $m\in M$ which $M$ thinks is the (code for the) shortest proof of a contradiction in $\mathsf{PA}$, and ...
Noah Schweber's user avatar
7 votes
Accepted

Specific example of a property $P$ that Peano arithmetic proves holds true for every specific number, but not for all numbers.

The standard example is $P(x)$ = "$x$ is not a (code for a) proof of a contradiction in $\mathsf{PA}$." Assuming $\mathsf{PA}$ is consistent, we obviously have $\mathsf{PA}\vdash P(n)$ for ...
Noah Schweber's user avatar
6 votes

Why define addition with successor?

Note that he is defining addition. So to avoid circularity he uses recursion, defining $m+(n+1)$ in terms of two things already defined: $m+n$ and the successor operation. So his recursive definition ...
Paul Tanenbaum's user avatar
6 votes
Accepted

Precise statement of Gödel's Incompleteness Theorems

Your last sentence is the key. Setting aside the issue of optimizing for strength (e.g. replacing $\mathsf{PA}$ by a weaker theory of arithmetic such as $\mathsf{Q}$), the following is a language ...
Noah Schweber's user avatar
5 votes

Does the property $T\vdash Pvbl_T(\ulcorner \sigma \urcorner) \implies T\vdash \sigma$ apply to set theories?

This is ultimately an arithmetic soundness assumption on the theory. For instance, it fails for $\sf PA+\lnot Con(PA),$ or any other theory that is consistent but proves its own inconsistency. There’s ...
spaceisdarkgreen's user avatar
5 votes
Accepted

Representability of Goodstein function in PA

Strong representability (in a given theory) does not imply provable totality (in that theory). Specifically, a function $f:\mathbb{N}\rightarrow\mathbb{N}$ is strongly representable in an appropriate ...
Noah Schweber's user avatar
5 votes
Accepted

On the consistency of satisfiable first order theories

Yes, if you believe everything makes sense and checks out regarding the basic ideas of model theory and $\mathbb N$ being a model of PA, then you believe in the consistency of PA. Most people are ...
spaceisdarkgreen's user avatar
5 votes

Confusion about Löb's theorem

The question suggests that the distinction between expressibility of truth and provability ought to be addressed. It may conceptually add some light to the present discussion to take into ...
Tankut Beygu's user avatar
  • 2,396
5 votes
Accepted

Is Gödels second incompleteness theorem provable within peano arithmetic?

This is a common confusion, and in particular Halbeisen/Krapf messed it up here (either Exercise 11.4(c) or Theorem 11.1 needs to be rephrased). The same confusion happens around the first ...
Noah Schweber's user avatar
4 votes

Is Russell's proof of addition with Peano's 5. Axiom valid?

We have to start from the definition of sum in terms of $0$ and sucecssor: $m+0=m$ and: $m+s(n)=s(m+n)$, and then we have to use induction to prove that the definition "works", i.e. &...
Mauro ALLEGRANZA's user avatar
4 votes

Is there a concept of finiteness independent of the successor function?

We can use the definition of Dedekind infinite to avoid appealing to "foreverness" or the successor function. To do this we say a set $S$ is infinite if there exists some $S' \subsetneq S $ ...
CyclotomicField's user avatar
4 votes

If Goldbach's conjecture G is undecidable in PA, then can we prove $\mathbb N\models G$?

If we could prove (in any given system) that $G$ is undecidable in PA, then we could prove there that it is true. But it is quite possible that $G$ happens to be undecidable (and true) but there is ...
Robert Israel's user avatar
4 votes
Accepted

Are the natural numbers definable in ZFC-Inf

Yes. If $\mathfrak{M}\models\mathsf{ZF}$-$\mathsf{Inf}$, the "natural numbers of $\mathfrak{M}$" are the things which $\mathfrak{M}$ thinks satisfy the following formula: $\nu(x):\quad$ $x$ ...
Noah Schweber's user avatar
4 votes

Formally how do we view finite sets

In modern mathematics, there's nothing but sets (well, we have proper classes which aren't sets but they just appear in category theory or NBG set theory). That is to say, we discuss things under ...
Timothée Jinsheng Yu's user avatar
4 votes
Accepted

Why Löwenheim–Skolem theorem asserts the non-existence of such predicates in 1st order logic

This is called the overspill principle. If there were such a predicate $\varphi(x)$ for some model $M$, then $M\models\varphi(0)$ and $M \models \forall x( \varphi(x)\to \varphi(x+1))$ (since the ...
spaceisdarkgreen's user avatar
4 votes

Can we conclude that Peano's axioms consistent from soundness?

Yes, absolutely. It is a theorem that $\mathsf{PA}$ is consistent. The easiest way to prove this theorem is to exhibit $\mathbb{N}$ as a model of $\mathsf{PA}$.
Alex Kruckman's user avatar
3 votes

If Goldbach's conjecture G is undecidable in PA, then can we prove $\mathbb N\models G$?

It is a theorem of $\sf PA$ that $\lnot\mathsf{provable}_{\sf PA}(\mathsf{negation}(\ulcorner G\urcorner))\to G.$ When we work in set theory, "$G$" means (internally) the exact same thing ...
spaceisdarkgreen's user avatar
3 votes
Accepted

Peano axioms and meaning of successor map in Jacobson's Basic Algebra I

The Peano axioms are a way to define the natural numbers; to introduce the concepts of addition when trying to define the natural numbers would be circular. So: "for any $a$" means "for ...
Gerry Myerson's user avatar
3 votes
Accepted

Peano’s Fifth axiom as stated by Russell

It is simply the original (1889) Peano's axiom of induction: "if $K$ is a class such that: $0$ is in $K$, and for every natural number $n$, $n$ being in $K$ implies that the successor of $n$ is ...
Mauro ALLEGRANZA's user avatar
3 votes
Accepted

Why universal closure?

If we want to talk about existentially quantified things, we often want to refer to them by name, so it's usually a good idea to name them by Skolemisation: instead of $∃x.P(x)$ introduce a constant ...
Alex's user avatar
  • 349
3 votes

Confusion about Löb's theorem

In essence, Löb's theorem deals with a pretty mind-bending idea in formal logic. You're right to think, "If something is provable, then it's true, right?" But here's the kicker: in the world ...
Jackson 2.0's user avatar
3 votes

Peano axioms - do we need a specific property to show that the principle of mathematical induction implies the "correct" set of natural numbers?

The Peano axioms include the induction axiom but are not sufficient to prove that there are no numbers outside the set you can access from $0$ with the successor function. The induction guarantees ...
Ross Millikan's user avatar
3 votes
Accepted

Modern reference on PA degrees?

If you are just looking to understand the basic results for $PA$ degrees I would recommend "Reverse Mathematics: Problems, Reductions and Proofs" by Mummert and Dzhafarov. In particular look ...
Giorgio Genovesi's user avatar
3 votes

Modern reference on PA degrees?

Another good source is Diamondstone/Dzhafarov/Soare's survey paper $\Pi^0_1$ Classes, Peano Arithmetic, Randomness, and Computable Domination. In particular, they go into detail about weak basis ...
Noah Schweber's user avatar
3 votes

Allegedly: the existence of a natural number and successors does not imply, without the Axiom of Infinity, the existence of an infinite set.

The answer of ac15 is correct and to the point. It helps to clarify the underlying philosophical terminology. Namely, there are two types of infinity, in a sense. If one says Take $n$, form its ...
Linear Christmas's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible