Coursify

Primitive Recursiveness of the Sum Function f(x,y)=x+yf(x,y)=x+y

Primitive Recursiveness of the Sum Function f(x,y)=x+yf(x,y)=x+y

Verified Sources
Sep 12, 2026

In primitive recursion theory (over N\mathbb{N}), one proves that a target function is primitive recursive by expressing it using the initial functions (like zero, successor, and projections) and closing operations such as composition and primitive recursion.2

For addition, the standard Peano-style equations are:

x+0=x,x+(y+1)=(x+y)+1.x+0=x,\qquad x+(y+1)=(x+y)+1.

Equivalently, writing SS for successor:

0+y=y,S(x)+y=S(x+y).0+y=y,\qquad S(x)+y=S(x+y).

A function satisfying such defining equations can be encoded as a primitive-recursive term using the primitive recursion operator ρ\rho. In particular, the addition function is primitive recursive.2

Key learning terms: primitive recursive; primitive recursion operator; projection function; successor function; composition.

Footnotes

  1. Primitive recursion and primitive recursive starting functions (Open Logic Project Builds, Recursive Functions) - Defines initial functions (zero, succ, projections) and closure under primitive recursion. ↩

  2. Proposition rec.4 addition is primitive recursive (Open Logic Project Builds, Recursive Functions) - Explicitly states and proves addition add(x,y)=x+yadd(x,y)=x+y is primitive recursive. ↩ ↩2

  3. Primitive recursive function — Addition section (Wikipedia) - Gives equations for addition and notes it can be defined using the primitive recursion operator ρ\rho. ↩ ↩2

Primitive Recursive Arithmetic (Addition by Primitive Recursion)

Goal

Show that the 2-ary sum function

f(x,y)=x+yf(x,y)=x+y

is primitive recursive. Concretely, we will exhibit a primitive-recursive definition (a term built from the primitive recursion scheme applied to already-primitive-recursive pieces). The relevant closure/definition facts are standard: primitive recursive functions start with 00, successor SS, and projections, and are closed under composition and primitive recursion.2

Footnotes

  1. Primitive recursion and primitive recursive starting functions (Open Logic Project Builds, Recursive Functions) - Defines initial functions (zero, succ, projections) and closure under primitive recursion. ↩

  2. Proposition rec.4 addition is primitive recursive (Open Logic Project Builds, Recursive Functions) - Explicitly states and proves addition add(x,y)=x+yadd(x,y)=x+y is primitive recursive. ↩

Constructing $f(x,y)=x+y$ using primitive recursion

  1. 1
    Step 1

    Use the scheme: given ff and gg that are already primitive recursive, define h(x,0)=f(x)h(x,0)=f(x) and h(x,y+1)=g(x,y,h(x,y))h(x,y+1)=g(x,y,h(x,y)). This yields hh primitive recursive by the closure property of primitive recursion.

    Footnotes

    1. Primitive recursion and primitive recursive starting functions (Open Logic Project Builds, Recursive Functions) - Defines initial functions (zero, succ, projections) and closure under primitive recursion. ↩

  2. 2
    Step 2

    Set h(x,0)=xh(x,0)=x, so take f(x)=xf(x)=x. In terms of projections, x=P11(x)x=P_1^1(x), which is primitive recursive.

    Footnotes

    1. Proposition rec.4 addition is primitive recursive (Open Logic Project Builds, Recursive Functions) - Explicitly states and proves addition add(x,y)=x+yadd(x,y)=x+y is primitive recursive. ↩

  3. 3
    Step 3

    We want h(x,y+1)=h(x,y)+1=S(h(x,y))h(x,y+1)=h(x,y)+1=S(h(x,y)). So define g(x,y,z)=S(z)g(x,y,z)=S(z), i.e., apply successor to the recursive result zz. Successor is primitive recursive, hence gg is primitive recursive.2

    Footnotes

    1. Primitive recursion and primitive recursive starting functions (Open Logic Project Builds, Recursive Functions) - Defines initial functions (zero, succ, projections) and closure under primitive recursion. ↩

    2. Proposition rec.4 addition is primitive recursive (Open Logic Project Builds, Recursive Functions) - Explicitly states and proves addition add(x,y)=x+yadd(x,y)=x+y is primitive recursive. ↩

  4. 4
    Step 4

    Let h=addh=\mathrm{add} be defined by primitive recursion with the chosen ff and gg: add(x,0)=x\mathrm{add}(x,0)=x and add(x,y+1)=S(add(x,y))\mathrm{add}(x,y+1)=S(\mathrm{add}(x,y)). Then add(x,y)=x+y\mathrm{add}(x,y)=x+y by the usual induction on yy for Peano addition.

  5. 5
    Step 5

    Since the base and step functions used in the primitive recursion are primitive recursive, the closure of primitive recursion implies add(x,y)\mathrm{add}(x,y) is primitive recursive.2 This is exactly f(x,y)=x+yf(x,y)=x+y.

    Footnotes

    1. Primitive recursion and primitive recursive starting functions (Open Logic Project Builds, Recursive Functions) - Defines initial functions (zero, succ, projections) and closure under primitive recursion. ↩

    2. Proposition rec.4 addition is primitive recursive (Open Logic Project Builds, Recursive Functions) - Explicitly states and proves addition add(x,y)=x+yadd(x,y)=x+y is primitive recursive. ↩

Formal match with the standard addition definition

Many presentations state the addition function directly as a primitive recursive function obtained via ρ\rho using equations

Add(0,y)=y,Add(S(x),y)=S(Add(x,y)).\mathrm{Add}(0,y)=y,\qquad \mathrm{Add}(S(x),y)=S(\mathrm{Add}(x,y)).

This yields a primitive-recursive term for addition (and thus for x+yx+y).

Also, standard references explicitly list: the addition function add(x,y)=x+yadd(x,y)=x+y is primitive recursive and give a primitive recursion proof based on the definition-by-equations method.

Key definitions/claims (with citations):

  • Primitive recursive functions arise from initial functions via composition and primitive recursion.2
  • Addition can be obtained using the primitive recursion operator ρ\rho from the standard equations for 0+y0+y and S(x)+yS(x)+y.
  • Addition is explicitly proven primitive recursive in standard treatments.

Footnotes

  1. Proposition rec.4 addition is primitive recursive (Open Logic Project Builds, Recursive Functions) - Explicitly states and proves addition add(x,y)=x+yadd(x,y)=x+y is primitive recursive. ↩ ↩2 ↩3

  2. Primitive recursion and primitive recursive starting functions (Open Logic Project Builds, Recursive Functions) - Defines initial functions (zero, succ, projections) and closure under primitive recursion. ↩

  3. Primitive recursive function — Addition section (Wikipedia) - Gives equations for addition and notes it can be defined using the primitive recursion operator ρ\rho. ↩

type="tip" title="Pro Tip" content="When proving a specific arithmetic function is primitive recursive, try to match it to a defining scheme of the form h(x,0)=f(x)h(x,0)=f(x) and h(x,y+1)=g(x,y,h(x,y))h(x,y+1)=g(x,y,h(x,y)). If ff and gg are primitive recursive and gg only uses previously-computed h(x,y)h(x,y), you can apply the closure of primitive recursion."

Footnotes

  1. Primitive recursion and primitive recursive starting functions (Open Logic Project Builds, Recursive Functions) - Defines initial functions (zero, succ, projections) and closure under primitive recursion. ↩

type="warning" title="Common pitfall" content="Do not confuse ordinary recursive definitions with primitive recursion. Primitive recursion requires the recursive occurrence to be exactly on the immediately preceding value (e.g., h(x,y)h(x,y) for defining h(x,y+1)h(x,y+1)), and the allowed building blocks must be primitive recursive."

Footnotes

  1. Primitive recursion and primitive recursive starting functions (Open Logic Project Builds, Recursive Functions) - Defines initial functions (zero, succ, projections) and closure under primitive recursion. ↩

How the proof builds up

Choose primitives

Stage 0 (initial functions)

Use zero/successor and projection functions as primitive recursive starting points.2"

Footnotes

  1. Primitive recursion and primitive recursive starting functions (Open Logic Project Builds, Recursive Functions) - Defines initial functions (zero, succ, projections) and closure under primitive recursion. ↩

  2. Proposition rec.4 addition is primitive recursive (Open Logic Project Builds, Recursive Functions) - Explicitly states and proves addition add(x,y)=x+yadd(x,y)=x+y is primitive recursive. ↩

Select the primitive-recursion template

Stage 1

Identify the right recursion variable (here yy) and specify h(x,0)h(x,0) and h(x,y+1)h(x,y+1)."

Footnotes

  1. Primitive recursion and primitive recursive starting functions (Open Logic Project Builds, Recursive Functions) - Defines initial functions (zero, succ, projections) and closure under primitive recursion. ↩

Instantiate base + step

Stage 2

Base: h(x,0)=xh(x,0)=x via projection; Step: h(x,y+1)=S(h(x,y))h(x,y+1)=S(h(x,y)) via successor.2"

Footnotes

  1. Primitive recursion and primitive recursive starting functions (Open Logic Project Builds, Recursive Functions) - Defines initial functions (zero, succ, projections) and closure under primitive recursion. ↩

  2. Proposition rec.4 addition is primitive recursive (Open Logic Project Builds, Recursive Functions) - Explicitly states and proves addition add(x,y)=x+yadd(x,y)=x+y is primitive recursive. ↩

Apply closure

Stage 3

Conclude the resulting h(x,y)h(x,y) is primitive recursive, hence x+yx+y is primitive recursive."

Footnotes

  1. Proposition rec.4 addition is primitive recursive (Open Logic Project Builds, Recursive Functions) - Explicitly states and proves addition add(x,y)=x+yadd(x,y)=x+y is primitive recursive. ↩

Primitive-recursive proof structure for addition

Which building blocks are used for each part of the definition.

Why this exactly computes $x+y$

Knowledge Check

Question 1 of 3
Q1Single choice

In the primitive recursion scheme for defining h(x,y)h(x,y), which equation form is required for the step case?

Explore Related Topics

1

Resolution in First-Order Logic (FOL): Resolution Refutation from a Simple Knowledge Base

2

Functional Dependencies and Candidate Keys in $R(A,B,C)$

In R(A,B,C)R(A,B,C) with functional dependencies A→BA\rightarrow B and B→AB\rightarrow A, neither single attribute determines all three attributes, so AA and BB are not keys; the minimal candidate keys are {A,C}\{A,C\} and {B,C}\{B,C\}.

  • A+={A,B}A^{+}= \{A,B\} and B+={A,B}B^{+}= \{A,B\}, both missing CC → not superkeys.
  • Adding CC yields (AC)+=(BC)+={A,B,C}(AC)^{+}= (BC)^{+}= \{A,B,C\}, making ACAC and BCBC candidate keys.
  • Mutual determination (A↔BA\leftrightarrow B) does not imply key status without covering the whole schema.
  • A common exam trap is assuming AA or BB are keys because they determine each other.
  • Heuristic: any attribute not derivable from others (here CC) must appear in every candidate key.
3

Solving the Recurrence $T(n)=T(n-1)+n$ by Substitution Method

The course shows how to solve the decrease‑by‑one recurrence (T(n)=T(n-1)+n) (with (T(1)=1)) using the substitution method.

  • Repeatedly substitute (T(n-i)=T(n-i-1)+(n-i)) until reaching the base case, yielding (T(n)=T(1)+2+3+\dots+n).
  • The resulting sum is the triangular number (\frac{n(n+1)}{2}).
  • The dominant term (\frac{1}{2}n^{2}) gives a tight asymptotic bound (\Theta(n^{2})).
  • For recurrences of the form (T(n)=T(n-1)+f(n)), expanding to a summation quickly reveals the closed form.
Browse all research articles