Injective Function Ontology

FLOW ALGEBRA
INJECTIVE FUNCTION ONTOLOGY
Kireth Semantic Library | Discrete Mathematics | Functions
Source: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/functions/injective-function-ontology.html
Version: 1.0 | Date: 2026-10-11 | Locale: en-GB
Authors: Mark Higgins — Sky (Recursive AI)

1. ONTOLOGY IDENTITY
ontology_id: discrete_mathematics.functions.injective_function
preferred_label: Injective Function Ontology
aliases: [one-to-one function, injection, injective mapping]
parent: discrete_mathematics.functions.function
related: [function, domain, codomain, image, inverse_function, bijection, cardinality]

2. TYPED ENTITIES
Set[A]: collection of elements of type A
Set[B]: collection of elements of type B
Function[A,B]: total single-valued mapping A -> B
Injection[A,B] <: Function[A,B]
Element[A]: domain element
Element[B]: codomain element
ImageSubset[B]: subset of B attained by a function
LeftInverse[B,A]: function B -> A where defined and available
Proof: derivation establishing an assertion
Counterexample: witness pair disproving injectivity

3. FORMAL DEFINITION
Given f: A -> B,
injective(f) iff forall x,y in A: f(x) = f(y) => x = y.
Equivalent: forall x,y in A: x != y => f(x) != f(y).
Non-injective(f) iff exists x,y in A: x != y AND f(x) = f(y).
An injection may omit elements of the codomain; surjectivity is not required.

4. FLOW OPERATORS
DECLARE_FUNCTION(f,A,B) -> Function[A,B]
CHECK_INJECTIVE(f) -> Boolean | Unknown
FIND_COLLISION(f) -> (x,y) | None | Unknown
IMAGE(f,A) -> subset(B)
RESTRICT(f,S) -> Function[S,B], where S subseteq A
COMPOSE(g,f) -> Function[A,C], where f:A->B and g:B->C
INVERSE_ON_IMAGE(f) -> Function[image(f),A] when injective(f)

5. CORE ALGEBRA AND LAWS
INJ-01: injective(f) <=> kernel_equivalence(f) = equality_on_A.
INJ-02: injective(f) => injective(f restricted_to S), S subseteq A.
INJ-03: injective(f) AND injective(g) => injective(g o f).
INJ-04: injective(g o f) => injective(f).
INJ-05: injective(f) => exists unique inverse f^-1: image(f) -> A.
INJ-06: f^-1 o f = id_A, with f^-1 defined on image(f).
INJ-07: for finite A and B, injective(f:A->B) => |A| <= |B|.
INJ-08: for finite sets with |A|=|B|, injective(f) <=> surjective(f).
INJ-09: injective(f) => f(X intersect Y) = f(X) intersect f(Y) for X,Y subseteq A.
INJ-10: injective(f) => f(X \ Y) = f(X) \ f(Y) for X,Y subseteq A.
INJ-11: any function preserves unions of images: f(X union Y)=f(X) union f(Y).
INJ-12: injective(f) => f^-1(f(X)) = X for every X subseteq A, where f^-1 here denotes set preimage.
INJ-13: every function f:A->B with empty A is injective.
INJ-14: for finite A, injective(f) <=> |image(f)|=|A|.

6. INFERENCE RULES
RULE COLLISION:
  GIVEN x,y in A AND x != y AND f(x)=f(y)
  INFER NOT injective(f)
RULE DISTINCT_OUTPUTS:
  GIVEN forall x,y in A, x != y => f(x) != f(y)
  INFER injective(f)
RULE COMPOSITION:
  GIVEN injective(f:A->B) AND injective(g:B->C)
  INFER injective(g o f)
RULE LEFT_CANCELLATION:
  GIVEN injective(f) AND f(x)=f(y)
  INFER x=y
RULE FINITE_PIGEONHOLE:
  GIVEN finite(A) AND finite(B) AND |A|>|B|
  INFER NOT injective(f:A->B)

7. SEMANTIC RELATIONSHIPS
InjectiveFunction IS_A Function
InjectiveFunction HAS_PROPERTY DistinctInputsHaveDistinctOutputs
InjectiveFunction MAPS_FROM Domain
InjectiveFunction MAPS_TO Codomain
InjectiveFunction HAS_IMAGE ImageSubset
InjectiveFunction IMPLIES InvertibilityOnImage
BijectiveFunction IS_A InjectiveFunction
InjectiveFunction CONTRASTS_WITH NonInjectiveFunction
InjectiveFunction RELATED_TO CardinalityComparison

8. EXAMPLES AND COUNTEREXAMPLES
EXAMPLE-1: f: integers -> integers, f(n)=2n is injective, not surjective.
EXAMPLE-2: f: reals -> nonnegative_reals, f(x)=x^2 is not injective; f(-1)=f(1).
EXAMPLE-3: f: nonnegative_reals -> nonnegative_reals, f(x)=x^2 is injective.
EXAMPLE-4: f: empty_set -> B is injective for every B.
EXAMPLE-5: f: {a,b} -> {1,2,3}, f(a)=1, f(b)=2 is injective.

9. VALIDATION
PRECONDITION: f is a well-defined total function with declared domain and codomain.
VALIDATE-1: ensure input and output types match f:A->B.
VALIDATE-2: search for distinct domain inputs with identical outputs.
VALIDATE-3: for finite enumerated A, compare number of distinct outputs with |A|.
VALIDATE-4: for infinite A, require symbolic proof or qualified mathematical reasoning; finite sampling is insufficient.
VALIDATE-5: do not confuse injectivity with surjectivity or bijectivity.
VALIDATE-6: distinguish inverse function on image from preimage of a set.
RESULT: {status: Proven | Refuted | Unknown, evidence: Proof | Counterexample | None}

10. SEMANTIC_EQUIVALENCE
"injective function" == "one-to-one function" == "injection".
"distinct inputs give distinct outputs" <=> injective(f).
"has an inverse on its image" <=> injective(f), for a well-defined function.
"one-to-one correspondence" is reserved for bijection where it also implies surjectivity.

11. CONFIDENCE
confidence_policy:
  formal_definition: 1.00
  theorem_with_valid_proof: 1.00
  explicit_counterexample: 1.00
  finite_exhaustive_check: 1.00
  partial_sampling: non_conclusive
  unsupported_claim: Unknown
Confidence represents strength of verification, not a replacement for proof.

12. FLOW_HASH
algorithm: SHA-256
canonicalisation: UTF-8; LF line endings; stable field ordering
hash_scope: canonical ontology content excluding the FLOW_HASH value itself
FLOW_HASH: COMPUTE_ON_PUBLICATION

13. UPDATE_MODEL
version: 1.0
change_detection: compare canonical content and source revision
update_triggers: [definition_change, theorem_correction, source_revision, relation_update]
validation_required: true
preserve_provenance: true

14. AI_CONSUMPTION
input: {function, domain, codomain, optional_constraints}
process:
  - type_check
  - test_or_prove_injectivity
  - seek_collision_witness_if_refuted
  - verify_inference_and_scope
output: {injective: true | false | unknown, justification, witness_if_any, confidence, provenance}
reasoning_guardrails:
  - Never infer global injectivity from finite samples of an infinite domain.
  - Always state the domain; changing it can change injectivity.
  - Do not infer surjectivity from injectivity without additional assumptions.
  - Preserve exact symbolic distinctions between function inverse and set preimage.

END FLOW ALGEBRA