Many-one reduction

Mathematical statement

Finite families declare complete source and target carriers, both decision predicates and an aligned mapping table. Qualify totality, then check both directions of membership equivalence for every x; yes-only checks are insufficient. Composition preserves direction: A≤mB and B≤mC give A≤mC. If A≤mB and B is decidable, compute f then run the B decider to decide A; the reverse implication is not supplied. Partial maps, reversed transfer and conflation with Turing reduction must be rejected. A finite table certifies only its declared finite domain; an infinite domain still needs a complete computable algorithm and termination argument.

Representative formula (exact TeX)

R(A,B,f)=1

Assumptions

• Exact families use declared bounded finite carriers and complete mapping arrays.
• Decider transfer uses complete finite truth tables or an explicitly total terminating computation.

Symbol scope

• R — many-one-reduction predicate
• A — source decision problem
• B — target decision problem
• f — total computable map

Intuition, definition, and misconceptions

Total-map qualification precedes reduction status.

Membership equivalence requires both yes and no directions.

Composition and decider transfer both preserve direction.

Yes-only checks or a partial map do not certify a reduction, and decidability of A does not transfer backwards to B.

Adopted derivation guide

The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.

Prerequisites

• Decision problem — Use yes/no predicates.
• Function mapping — Require a complete total map.
• Function composition — Compose reductions in order.
• Turing-machine decision model — Keep decider and termination boundaries explicit.

Verification boundary

Finite tables do not prove infinite-domain computability and are not Turing reductions.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.

Next obligation

Add undecidability reductions and recognizability boundaries.

Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.