Cost Monotone Multiplicative Power Pow Eq

The power rule

In number theory, a function on the positive integers is called completely multiplicative if it satisfies f(mn) = f(m)f(n) for all m and n. The identity f(n) = n and the constant function f(n) = 1 are the two simplest examples. A classical theorem of Erdős says that if such a function is also nondecreasing, then it must be a power: there is a real exponent c ≥ 0 with f(n) = n^c. The constant function is the case c = 0, and the identity is c = 1.

The declaration pow_eq establishes one step of that theorem: for any such function f, the value at a power equals the power of the value, f(m^j) = f(m)^j for every base m ≥ 1 and every exponent j. The proof is a short induction on j. The base case j = 0 uses the condition f(1) = 1. The induction step applies the multiplicative property to split f(m^(j+1)) into f(m^j) · f(m), then uses the induction hypothesis. This is the only form of complete multiplicativity that the later squeeze argument needs.

In Recognition Science, this lemma appears in the cost ledger, a discrete record of recognition events, where the cost function is forced to satisfy the same monotone multiplicative conditions. The lemma itself is a purely arithmetic fact: it does not depend on the ledger or on any special cost function. It is a general statement about any function with the two stated properties.

The theorem does not claim that the exponent c is unique, nor that every completely multiplicative nondecreasing function is a power. That stronger conclusion is a separate theorem, also in the same file, proved by a squeeze argument on logarithms. The lemma pow_eq only gives the power behavior for a single base at a time.

What the lemma does give is a clean algebraic identity that holds for every completely multiplicative nondecreasing function, with no regularity assumptions beyond monotonicity. It is the kind of small, exactly stated step that a machine-checked proof can use without hidden side conditions.

/-- Complete multiplicativity on powers, which is the only form the squeeze uses. -/
theorem pow_eq (hf : MonotoneMultiplicative f) {m : ℕ} (hm : 1 ≤ m) (j : ℕ) :
    f (m ^ j) = f m ^ j := by
  induction j with
  | zero => simpa using hf.unit
  | succ j ih =>
      have hmj : 1 ≤ m ^ j := Nat.one_le_pow j m hm
      rw [pow_succ, hf.mul _ _ hmj hm, ih, pow_succ]

What this page does not claim

The lemma does not prove that every completely multiplicative nondecreasing function is a power, only the single-base power identity. The lemma does not identify the exponent c or show uniqueness. The lemma does not depend on any Recognition Science axiom; it is a general arithmetic fact.

Verify this page

Every tagged claim above names its theorem. To check one yourself rather than trust this page, elaborate the source module with Lean 4 and audit its axiom basis:

$ lake env lean IndisputableMonolith/Cost/MonotoneMultiplicativePower.lean
expected axiom basis: [propext, Classical.choice, Quot.sound] (the Lean kernel's standard three; no RS-specific axioms)

A page whose claims cannot be reproduced this way does not ship. In production, every anchor links to the exact declaration in the public source release, and this block carries the build receipt for the page itself.

Derived articles

This page is generated by a question-recursion engine: the questions its answers raise become the next pages. The current agenda, with open targets marked red: