Question

Show (i) PA \(\vdash \forall x(0 \leq x)\) (use induction on \(\mathrm{x}\) ), (ii) \(\quad \mathbf{P A} \vdash \forall x(x=0 \vee \exists y(x=S y)\) ) (use induction on \(\mathrm{x}\) ), (iii) \(\quad \mathbf{P A} \vdash \forall x y(x+y=y+x)\), (iv) \(\quad \mathbf{P A} \vdash \forall y(x

Short answer

Induction proves all given propositions under PA.

Step-by-step solution

Show PA ⊢ ∀x(0 ≤ x)

We use mathematical induction on the variable \(x\) to prove this statement. Base case: We need to show \(0 \leq 0\), which is vacuously true since equality implies the lesser or equivalence sign. Inductive step: Assume \(0 \leq n\) holds for some natural number \(n\). We need to show \(0 \leq S(n)\). By definition of successor, \(S(n) > n\), thus \(0 \leq n\) ensures \(0 \leq S(n)\) is also true. Therefore, by induction, \(\forall x(0 \leq x)\) is proven.

Show PA ⊢ ∀x(x=0 ∨ ∃y(x=Sy))

We apply induction on \(x\) for this proof. **Base Case:** For \(x = 0\), the statement holds as \(0 = 0\). **Inductive Step:** Assume \(n = 0 \vee \exists y(n = S y)\) is true for some natural number \(n\). We need to show \(S(n) = 0 \vee \exists y(S(n) = S y)\). Clearly, \(S(n) eq 0\). Therefore, \(S(n) = S(n)\) with \(y = n\), confirming the existence of such \(y\). Hence, \(\forall x(x=0 \vee \exists y(x=Sy))\) holds.

Show PA ⊢ ∀x y(x+y=y+x)

Base Case: For \(x = 0\), show \(0 + y = y + 0\). Both compute to \(y\). Inductive Step: Assume \(n + y = y + n\) holds for some \(n\). We need \(S(n) + y = y + S(n)\). By definition, \(S(n) + y = S(n + y)\). Using the inductive hypothesis, \(S(n + y) = S(y + n)\), and by properties of addition, \(S(y + n) = y + S(n)\). Therefore, \(\forall x y(x+y=y+x)\) is true by induction.

Show PA ⊢ ∀y(x

Base case: For \(y = 0\), the statement \(x < 0 \rightarrow S x \leq 0\) is vacuously true because there is no \(x < 0\) in \(\mathbb{N}\). Inductive step: Assume the statement holds for \(y = n\), i.e., \(x < n \rightarrow S x \leq n\). We must show \(x < S(n) \rightarrow S x \leq S(n)\). If \(x < S(n)\), then \(x \leq n\), and by the inductive hypothesis, \(S x \leq n\) or \(S x = n\) leading to \(S x \leq S(n)\). Therefore, this property holds by induction.

Show PA ⊢ ∀x y(x

Base Case: For \(x=0\), we prove \(0<y\vee 0=y\vee y<0\) which holds as either \(0=y\) or \(0<y\) for any natural \(y\). Inductive Step: Assume \(n<y\vee n=y\vee y<n\) for some \(n\). We need to show \(S(n)<y\vee S(n)=y\vee y<S(n)\). If \(n<y\), then \(S(n)\leq y\) by Step 4, leading to \(S(n)<y\vee S(n)=y\). Hence by induction, the statement is true.

Show PA ⊢ ∀y ¬∃x(y

Observe that \(y < x\) implies \(x \geq S y\). Hence, \(x < S y\) contradicts \(x \geq S y\). Assume there exists such \(x\), hence \(y < x\) but this directly implies \(x \geq S y\). Thus, \(¬(x < S y)\) for \(x > y\), ensuring \(\forall y eg \exists x(y<x \wedge x<S y)\).

Key concepts

Mathematical Induction

Mathematical induction is a powerful method used to prove statements about natural numbers. The process involves two main steps:

• Base Case: Verify the statement for the initial natural number, often zero.
• Inductive Step: Assume the statement is true for a given number, say \(n\), and use this assumption to prove it for \(S(n)\), the successor of \(n\). This is known as the inductive hypothesis.

The beauty of mathematical induction lies in its ability to extend the validity of a statement from one number to all natural numbers. It's similar to domino effect, where knocking one down leads to all the following dominoes falling as well. Let's see how this method applies in Peano Arithmetic (PA).

Peano Arithmetic

Peano Arithmetic is a set of axioms designed to capture the basic properties of natural numbers using first-order logic. It formalizes how numbers work by defining:

• Zero \(0\) as a natural number.
• The successor \(S(x)\) of any natural number \(x\) is also a natural number.
• No natural number has zero as its successor: \(eg \exists x(S(x) = 0)\).
• Different numbers have different successors: \(x = y \rightarrow S(x) = S(y)\).
• Mathematical induction can be used to prove properties of all natural numbers.

This logical framework helps in rigorously proving statements such as the basic properties of inequality and addition within PA.

Successor Function

The successor function, denoted \(S(x)\), is a fundamental concept in Peano Arithmetic. It describes the next number in the sequence of natural numbers. For example, the successor of \(0\) is \(1\), represented as \(S(0)\), and the successor of \(1\) is \(2\), represented as \(S(S(0))\).

• The successor function demonstrates the progression from one natural number to the next.
• It assists in defining and proving recursive properties within natural numbers.
• This function plays a key role in defining addition whereby \(x + S(y) = S(x + y)\).

Understanding the successor function is crucial for working with properties of numbers in a formal arithmetic setting, as it underpins the structure of natural numbers.

Properties of Inequality

Inequalities in Peano Arithmetic establish relationships between different natural numbers. Important properties include:

• For any natural number \(x\), \(0 \leq x\) which is proven by induction.
• The successor function helps prove that \(x < y\) implies \(S(x) \leq y\).
• Every pair of natural numbers \(x\) and \(y\) satisfies \(x < y\), \(x = y\), or \(y < x\), ensuring a complete comparison.

These properties help indicate how numbers can be ordered and compared, supporting various arithmetic operations and logical deductions.

Properties of Addition

Addition within Peano Arithmetic follows simple yet important rules that align with the intuitive understanding of combining numbers. Some key properties are:

• Addition is commutative, meaning \(x + y = y + x\) for any natural numbers \(x\) and \(y\).
• Addition is associative, so \((x + y) + z = x + (y + z)\).
• Adding zero to any number does not change the number: \(x + 0 = x\).
• The successor property in addition states \(x + S(y) = S(x + y)\), which builds on the idea of the successor function.

These properties ensure the consistency and predictability of addition, which is essential for building more complex mathematical proofs and operations.