Questions tagged [peano-axioms]

For questions on Peano axioms, a set of axioms for the natural numbers.

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

Does transfinite induction follow from second-order induction?

Second-order induction is defined in the Peano Axioms as follows: for all formulas $φ$, $φ(0) \rightarrow (\forall v(A(v) \rightarrow φ(s(v))) \rightarrow \forall n φ(n))$, where $s$ is some ...
2
votes
1answer
45 views

Using the Compactness Theorem for First-order Logic to find a model

The problem I am trying to understand is as follows, which was posed as an example in one of my lectures. The motivation of the problem is to apply the compactness theorem: Consider the language with ...
1
vote
1answer
38 views

Proving that $\mathbb{Z_{-}} \cap \mathbb{N}=\emptyset$

In assumption that $\mathbb{N}$ and successor function ($\overline{x}$) over $\mathbb{N}$ is defined by 5 Peano axioms: $1\in\mathbb{N}$ $n\in\mathbb{N} \Rightarrow \overline{n}\in\mathbb{N}$ $\...
0
votes
1answer
44 views

Function by recursion on a set $X$ satisfy Peano's axioms

I've been stuck on this theorem for like two days and I still don't really get it. I'm reading the construction of natural numbers using "classic set theory for guided independent study", ...
0
votes
1answer
42 views

What is a set with a function $f$ that don't satisfy peano's axioms?

I'm reading "classic set theory for guided independent study", and i'm studying the construction of natural numbers using peano's axioms. The three axioms they give me are: A Peano system is ...
0
votes
0answers
24 views

Could you guys correct my Peano's axiom induction principle translation in predicate logic?

I'm reading "classic set theory for guided independent study", and i'm studying the construction of natural numbers using peano's axioms, one of the axioms, called induction axiom, states: &...
1
vote
0answers
27 views

Peter Smith's Hilbertian argument

Peter Smith in "An Introduction to Gödel's Theorems" presents a broadly Hilbertian argument (in the sense of Hilbert's program) on page 276 (2nd edition): Theorem 37.2 If $I$ is consistent ...
0
votes
0answers
50 views

Kripke's proof of the incompleteness of PA

In Hillary Putnam's writeup on Kripke's beautiful incompleteness proof of PA, which I learned about from Noah Schweber's answer here, I can convince myself that (see the top of p.56) "$s$ ...
0
votes
0answers
25 views

Prove that for there is no $n \in \mathbb{N} \setminus \{1\}$ for which there is another $m \in \mathbb{N}$ so that $nm = 1$.

Question is in the title, here's my proof attempt: Let $n \in \mathbb{N} \setminus \{1\}$ be arbitrary but fixed. Define the following set: $$S = \{m \in \mathbb{N}: nm \neq 1\}$$ Let $m = 1$. Since $...
2
votes
1answer
60 views

Peano arithmetics formulae examples [closed]

Help me please to come up with an example of two arithmetic formulae $\varphi$ and $\psi$ such that $PA\vdash\varphi\vee\psi$, but neither $\varphi$ nor $\psi$ is derivable in $PA$ ($PA$ is Peano ...
0
votes
0answers
49 views

Can PA be interpreted in a theory about a total function on sets that is sensitive to proper subsethood?

Language tri-sorted FOL with identity, with lower cases representing individuals, and upper cases representing sets of them, and asterisked upper cases for sets of sets of individuals.A one place ...
0
votes
1answer
37 views

Prove that $+:\mathbb{N} \times \mathbb{N} \to \mathbb{N}$ is a binary operation

The question is in the title. The definition of $+:\mathbb{N} \times \mathbb{N} \to \mathbb{N}$ is given as follows: $$\forall m,n \in \mathbb{N}: [n+1 := n'] \land [n+m' := (n+m)']$$ where $n'$ ...
0
votes
1answer
102 views

How do I prove this? (Set Theory, Mathematical Logic)

I'm studying for an exam of mathematical logic. This question envolves the Peano axioms, I think. Prove that, for all $ n \in \omega$, $ n \notin n$. It's kind of obvious that it's true but I don't ...
2
votes
2answers
81 views

Is the axiom of induction required for proving the first Gödel's incompleteness theorem?

I'm reading a book about the mathematical logic. In the 6.3 chapter of that book, a theory $Q$ is introduced that contains precisely these axioms: $Q1: \forall x. (S(x) \not= 0)$ $Q2: \forall x,y. (...
3
votes
0answers
58 views

Every provably recursive function in PA is bounded by a Hardy function

The following lemma and proof are from Takeuti's Proof Theory (2nd edition, pp. 126-127), I've highlighted the problematic part in blue: How does Takeuti get this inequality? If the proof $x$ is not ...
4
votes
0answers
77 views

Characterization of provably recursive functions in PA

This concerns Takeuti's Proof Theory: the book contains a lot of wonderful material, but the presentation is sometimes lacking (and so many typos!). At least that has been my experience so far, ...
0
votes
1answer
80 views

While using the method of proof by contradiction, are we “assuming” consistency?

I am aware of threads here and here which asks something similar. However, I had something very specific to ask under the same context. I have a very elementary question about the connection between ...
0
votes
0answers
23 views

What's the proof theoretic ordinal of this number-set theory?

I was thinking of defining a number-set theory, that is a theory that uses the primitives of equality, strict smaller than, and set membership, in order to coin a theory that is at least as strong as ...
0
votes
1answer
21 views

What's the strength of weakening induction in PA by relativizing it to naturals?

If we weaken induction in PA to the following scheme: $\forall m [\phi(0) \land \forall n < m (\phi(n) \to \phi(n+1)) \to \forall n \leq m (\phi(n))]$ Where $\phi$ is any formula in the language ...
0
votes
0answers
35 views

Proving addition preserves order in natural numbers

I have the following question: Prove $a≥b$ if and only if $a+c≥b+c$ $\forall$ natural numbers. (using Peano Axioms) The solution I checked is different from what I used and same applies to the ones I ...
0
votes
0answers
27 views

When can a statement in Second Order Logic be converted into a statement in First Order Logic

I was reading on first and second order logic (The first has quantifiers over individuals of the domain and the second can have quantifiers over predicates as well - see this question: Differentiating ...
2
votes
3answers
102 views

Are mathematical operations axioms?

Are mathematical operations axioms? I will give an example of multiplication, but this also applies to division, subtraction and addition. Idea of multiplication was invented by people to increase/...
2
votes
0answers
45 views

Exercise 2.2.1 in Analysis by Terence Tao Induction Proof of Addition Associative Law Natural Numbers

The proposition 2.2.5 and also exercise 2.2.1 of Analysis by Terence Tao is as below: Show for any natural numbers $a, b, c$, we have $(a+b)+c = a+(b+c)$ the associative rule The proof should use ...
0
votes
0answers
32 views

Defining specific Exponentiation in PA

Given the dictionary {0,1,+,*,<} can I write a simple formula with only x occurs free, that states "x is an exponent of 6"? When I say simple, I mean, without using complicated techniques like ...
1
vote
2answers
44 views

Show that the decidability of a statement is undecidable.

In this system of axioms, it can be shown that A = 5 is undecidable Axioms: A is a prime number, A is greater than 4, A is less than 8 This is because both A = 5 and A = 7 are consistent with these ...
1
vote
0answers
34 views

Proving Natural Predecessor existence using Well Order

I know that the Principle of Induction is equivalent to Well Order at least in Natural Numbers, but I have seen that the demonstration of Induction using Well Order uses the existence of Predecessor: ...
1
vote
1answer
31 views

Prove trichotomy of order WITHOUT induction?

Claim. If $x,y \in \mathbb N$, then at least one of these is true: (a) $x>y$; (b) $x=y$; or (c) $x<y$. It seems that the usual proof of this claim uses induction. Is it possible to prove this ...
1
vote
1answer
35 views

How do I derive fraction multiplications from Peano axioms

and sorry for the noob questions :) Trying to teach my 10 year old daughter some math and came across the Peano axioms. On the following resource there are two sets of axioms, one is based on symbols ...
0
votes
1answer
19 views

Is there a place which has the functional (programming) definition of Numbers in various forms?

I am familiar with the Peano Natural Number definition which is what you see in intro to functional programming courses and examples. But I have also much later encountered a practical implementation ...
0
votes
1answer
31 views

Peano arithmetic - Why is adding n to m the same as incrementing m n times?

Addition(+) is defined using the successor function(++) in Peano arithmetic as: 0 + m = m (n++) + m = (n + m)++ While these are intuitive axioms that are consistent with my previous, elementary, ...
6
votes
0answers
117 views

Is there a natural intermediate version of PA?

Below, "logic" means "regular logic containing first-order logic" in the sense of Ebbinghaus/Flum/Thomas. Setup For a logic $\mathcal{L}$, let $\mathcal{PA}(\mathcal{L})$ be the ...
2
votes
1answer
73 views

How to prove $x=5$ using the Peano Axioms?

This question relates to Proposition V of Gödel's 1931 Incompleteness theorem (and another one posted on math.stackexchange here ) which says: For every recursive relation $ R(x_{1},...,x_{n})$ there ...
3
votes
1answer
64 views

A question about Dedekind-infinite sets and Peano natural integers.

I've doubt about Dedekind-infinite sets, sets which are in bijection with a proper part, in the ZF axiomatic framework, without Axiom of Choice. Assume a Dedekind-infinite set X exists. Then it can ...
0
votes
1answer
79 views

A fundamental question about relations between axioms

In mathematics, there are several sets of axioms. For example, we have ZFC axioms, Peano axioms, Hilbert's axioms of Euclidean geometry(https://en.wikipedia.org/wiki/Hilbert%27s_axioms), and so on. ...
2
votes
4answers
170 views

How does the Peano axiom of induction prevent S-loops?

First, let me state what I understand to be the first-order rendition of Peano's 5th axiom: the axiom of induction. For all natural numbers, for any relation/property/predicate $R$... $$(R(0) \land \...
0
votes
1answer
43 views

How do we prove there is no natural number between $a$ and its successor $a\texttt{+}\texttt{+}$?

Let $a,b$ be natural numbers. Then $a < b$ if and only if $a\texttt{+}\texttt{+}\leq b$. MY ATTEMPT If $a < b$, we may suppose by contradiction that $a\texttt{+}\texttt{+} > b$. Thus we ...
0
votes
0answers
28 views

For any natural numbers $a,b,c$,prove that associativity of the product $(a\times b)\times c = a\times(b\times c)$.

For any natural numbers $a,b,c$, we have that $(a\times b)\times c = a\times(b\times c)$. MY ATTEMPT We shall prove it by induction on $c$. For $c = 0$, one has that \begin{align*} (a\times b)\times ...
0
votes
0answers
27 views

Prove for natural numbers that $n\times m = 0$ if and only if at least one of $n,m$ is equal zero.

Let $n,m$ be natural numbers. Then $n\times m = 0$ if and only if at least one of $n,m$ is equal zero. In particular, if $n$ and $m$ are both positive, then $nm$ is also positive. MY ATTEMPT Suppose ...
1
vote
1answer
94 views

Let $m,n$ be natural numbers. Then prove the commutativity of the product $n\times m = m\times n$.

Let $m,n$ be natural numbers. Then $n\times m = m\times n$. MY ATTEMPT (EDIT) Lemma 1 We shall need first the following result: $m\times 0 = 0$. Let us prove it by induction on $m$. Indeed, one ...
2
votes
1answer
73 views

For any natural numbers $a,b,c$, prove the associativity property $(a + b) + c = a + (b + c)$.

For any natural numbers $a,b,c$, we have $(a + b) + c = a + (b + c)$. MY ATTEMPT We shall prove it by induction on $c$. For $c = 0$, we have that $(a + b) + 0 = a + b$ and $a + (b + 0) = a + b$. ...
1
vote
1answer
43 views

Can I do this instead to prove the Strong Principle of Induction (Tao 2.2.14)?

I have already read the following (this one and this one too) discussions on Stack Exchange and they have not answered my query. Proposition 2.2.14 asks the reader to prove that: Proposition $2.2.14$ ...
1
vote
1answer
33 views

Find all functions that compose with the successor function

In Mac Lane/Birkhoff's Algebra, they spend some time discussing the natural numbers and give the Peano Axioms, roughly (from memory) $\sigma$ is injective 0 is not the successor of any element the ...
2
votes
1answer
56 views

Prove the induction axiom via the induction rule

Consider the formal system $P'$ which is the same as $PA$, but without all the induction axioms and with an additional induction rule: If $\vdash A_x[0]$ and $\vdash A\to A_x[Sx]$, then $\vdash A$. ...
3
votes
2answers
84 views

Can proper elementarily equivalent end extensions ever be definable?

Suppose $M\models PA$. Can there be a tuple of formulas $\Psi$ (possibly with parameters from $M$) such that: $\Psi^M\equiv M$ (or more precisely, $\Psi$ is an interpretation of an $\{0,1,+,\cdot,<...
1
vote
1answer
90 views

Is my proof of lemma 2.2.10 (Analysis 1 Tao) correct?

I have recently begun self studying Real Analysis 1 by Tao. Such proofs are new to me and the solutions are not provided in the book. That is why I'm asking this question. Any feedback is welcome, ...
1
vote
1answer
57 views

Is my Peano Axiom proof correct?

I have recently begun reading Terry Tao's Real Analysis 1. The Peano Axiom proofs in the book are very new to me. Because of this, I have little intuition as to whether my proofs are correct. In ...
6
votes
1answer
134 views

Dedekind-infinite objects and NNO in an elementary topos

Let $\mathcal{E}$ be an elementary topos. Call an object $X\in \mathcal{E}$ Dedekind-infinite when it admits a monic but not epi endomorphism. I wonder if in an elementary topos the existence of ...
1
vote
1answer
35 views

How does one prove that Peano Arithmetic can represent all partially computable functions?

I'm interested in establishing that for any partially computable $k$-ary function $f$ there exists a formula $\Phi$ with $k+1$ free variables such that If $f(x_1, \dots, x_k) = y$, then $\Phi(x_1, \...
0
votes
2answers
26 views

Defining positional numeral systems without binary arithmetic operations

Given a totally ordered set of digits $\mathcal{D}$ with cardinality $b\in\mathbb{N}$, least element $d_{\operatorname{min}}\in\mathcal{D}$ and greatest element $d_{\operatorname{max}}\in\mathcal{D}$, ...
0
votes
1answer
46 views

Can this function be described by a formula?

Suppose $PA$ is Peano arithmetic. For $m \in \mathbb{N}$ define $\overline{m}$ as a term in the language of $PA$ using the following recurrence. $$\overline{0} = 0$$ $$\overline{m + 1} = S(\overline{...

1
2 3 4 5
14