Injectivity and distinct inputs

Mathematical statement

A total function f:A→B is injective if, for all x,y∈A, f(x)=f(y) implies x=y. Equivalently, distinct inputs have distinct outputs. Every fiber {x∈A:f(x)=b}, for b∈B, has at most one element.

Representative formula (exact TeX)

f:A\to B

Assumptions

• A, B, and the total function are explicit; every input in A has exactly one output in B.
• The exercises use finite integer-labeled function tables. Injectivity holds for an empty domain, and finite results do not settle other functions.

Symbol scope

• f — specified total function
• A — domain
• B — codomain

Intuition, definition, and misconceptions

First check that the table is total on A, then compare outputs of distinct inputs. Repeated copies of the same ordered pair are duplicate representations; one input paired with different outputs is not a total function.

An injection may miss codomain elements. Fibers may have size zero or one; a collision witnessing failure requires two distinct preimages of the same output.

Restriction to C⊆A compares only inputs in C. A noninjective function may become injective after restriction. For a finite first collision, use x<x′ and select the lexicographically first (x,x′); do not infer the property from a sketch or sample.

Common errors include reading injectivity as existence of a preimage for every codomain element, or omitting total-function eligibility.

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

• Function mapping — First validate total-function input and output eligibility.
• Quantifiers and explicit domains — Injectivity quantifies over two permitted inputs.

Verification boundary

Finite tables permit exhaustive injectivity and collision checks; no new formal Evidence for general injectivity theory is attached.

not_formalized

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

Next obligation

Bind Function.Injective, fiber cardinality, and domain restriction.

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.