Bijective Function Ontology

FLOW ALGEBRA
BIJECTIVE FUNCTION ONTOLOGY
Kireth Semantic Library | Mathematical Entities | Function and Mapping Entities
Source: https://kirethresearch.org/booksai-core/entity-graph/mathematical-entities/function-and-mapping-entities/bijective-function-ontology-2.html
Authors: Mark Higgins — Sky (Recursive AI)
Status: Formal mathematical specification based on established mathematics; source page not independently verified.
Version: 1.0 | Date: 2026-10-13

01. PURPOSE
flow "BijectiveFunctionOntology" v1.0
  intent: represent, classify, validate and reason about bijective functions
  domain: set theory, function theory, algebra, category theory, knowledge representation
  semantics: classical set-theoretic mathematics

02. ENTITY TYPES
  Set: collection of elements
  Function: total single-valued map f:A -> B
  Domain: A
  Codomain: B
  Image: f[A] subseteq B
  Fibre: f^{-1}[{b}] subseteq A
  InjectiveFunction: function with distinct outputs for distinct inputs
  SurjectiveFunction: function whose image equals its codomain
  BijectiveFunction: function both injective and surjective
  InverseFunction: unique map f^{-1}:B -> A when f is bijective
  IdentityFunction: id_A:A -> A, id_A(a)=a
  Permutation: bijection A -> A
  Isomorphism: bijection preserving the specified additional structure

03. SIGNATURE AND TYPING
  f: A -> B
  forall a in A, exists exactly one b in B: f(a)=b
  bijective(f) requires f be a well-defined total function
  empty-domain rule: empty function is bijective iff codomain is empty
  equality of functions: same domain, same codomain, same values on all inputs

04. CORE DEFINITION
  injective(f) <=> forall x,y in A: f(x)=f(y) => x=y
  surjective(f) <=> forall b in B, exists a in A: f(a)=b
  bijective(f) <=> injective(f) AND surjective(f)
  equivalent: forall b in B, exists exactly one a in A: f(a)=b

05. IMAGE AND FIBRE
  image(f)= {f(a) | a in A}
  surjective(f) <=> image(f)=B
  injective(f) <=> every fibre has at most one element
  bijective(f) <=> every fibre has exactly one element

06. INVERSE EXISTENCE
  bijective(f) <=> exists g:B -> A with g o f=id_A and f o g=id_B
  inverse(f)=g is unique
  forall a in A: f^{-1}(f(a))=a
  forall b in B: f(f^{-1}(b))=b
  inverse(inverse(f))=f

07. COMPOSITION
  given f:A -> B, g:B -> C
  bijective(f) AND bijective(g) => bijective(g o f)
  (g o f)^{-1}=f^{-1} o g^{-1}
  bijective(g o f) alone does not imply f and g are both bijective
  bijective(g o f) => f injective AND g surjective

08. IDENTITY AND PERMUTATIONS
  id_A is bijective for every set A
  bijections A -> A form the symmetric group Sym(A) under composition
  identity is neutral; inverses and associativity hold
  for finite |A|=n, number of permutations = n!

09. CARDINALITY
  bijection A -> B => |A|=|B|
  |A|=|B| means a bijection exists (definition of equipotence)
  finite A,B: bijection possible iff |A|=|B|
  finite equal-cardinality sets: injective iff surjective
  infinite sets: injectivity and surjectivity are not generally equivalent

10. EXAMPLES
  f:Z -> Z, f(n)=n+3 is bijective; inverse(b)=b-3
  f:R -> R, f(x)=2*x+1 is bijective; inverse(y)=(y-1)/2
  f:R -> R, f(x)=x^2 is not bijective
  f:[0,infinity) -> [0,infinity), f(x)=x^2 is bijective
  f:N -> N, f(n)=n+1 is not surjective when N={0,1,2,...}
  f:empty -> empty is bijective

11. NON-EXAMPLES AND DOMAIN SENSITIVITY
  f:R -> R, f(x)=exp(x) is injective but not surjective
  f:R -> (0,infinity), f(x)=exp(x) is bijective
  codomain must not be silently replaced by image
  changing domain or codomain can change bijectivity
  a multivalued relation is not a function without a single-valued rule

12. PROOF METHODS
  injectivity: assume f(x)=f(y), derive x=y
  surjectivity: take arbitrary b in B, construct a in A with f(a)=b
  inverse proof: construct g and verify both identity compositions
  finite sets: validate equal cardinalities plus injection or surjection
  counterexample: exhibit duplicate outputs or an unattained codomain element

13. FINITE VALIDATION ALGORITHM
  require function total and single-valued
  require each output belongs to B
  observed_outputs = {f(a): a in A}
  injective = count(observed_outputs) == count(A)
  surjective = observed_outputs == B
  bijective = injective AND surjective
  for infinite domains use symbolic proofs or sound theorem-specific procedures

14. STRUCTURE PRESERVATION
  bare bijection preserves only set cardinality
  bijection alone does not imply continuity, linearity, order preservation or homomorphism
  isomorphism requires bijection AND preservation of specified structure
  homeomorphism requires continuous bijection with continuous inverse
  linear isomorphism requires bijective linear map

15. KNOWLEDGE GRAPH SCHEMA
  nodes: Function, Domain, Codomain, Image, InverseFunction, Proof, Counterexample
  edges:
    HAS_DOMAIN(Function,Set)
    HAS_CODOMAIN(Function,Set)
    HAS_IMAGE(Function,Set)
    IS_INJECTIVE(Function,true|false)
    IS_SURJECTIVE(Function,true|false)
    IS_BIJECTIVE(Function,true|false)
    HAS_INVERSE(Function,InverseFunction)
    COMPOSES_WITH(Function,Function)
    PROVEN_BY(Claim,Proof)
  use scoped function identity: -expression + domain + codomain

16. SEMANTIC_EQUIVALENCE
  "bijective function" == "bijection" == "one-to-one correspondence"
  "one-to-one and onto" == "injective and surjective"
  do not treat "one-to-one" alone as unambiguously bijective
  inverse relation vs inverse function: inverse relation is functional exactly when f is injective; total on B exactly when f is surjective

17. INFERENCE RULES
  R1: Injective(f) AND Surjective(f) -> Bijective(f)
  R2: Bijective(f) -> Injective(f)
  R3: Bijective(f) -> Surjective(f)
  R4: Bijective(f) -> ExistsUniqueInverse(f)
  R5: Bijective(f) AND Bijective(g) AND composable(f,g) -> Bijective(g o f)
  R6: Bijective(f:A->B) -> Equipotent(A,B)
  R7: Bijective(f:A->A) -> Permutation(f,A)
  R8: Bijective(f) -> Bijective(inverse(f))
  guard all rules with validated function signatures

18. CONSTRAINTS AND INVARIANTS
  no undefined inputs in domain
  no outputs outside codomain
  no duplicated outputs across distinct inputs for injection
  no missing codomain elements for surjection
  inverse must be single-valued and total on B
  preserve typed domains and codomains across compositions

19. CONFIDENCE
  formal theorem or machine-checked proof: confidence=1.0 within stated axioms
  finite exhaustive verification: confidence=1.0 for enumerated sets and mapping
  unverified claim: confidence=unknown; do not infer proof from examples
  approximate numerical evidence cannot establish exact bijectivity

20. PROVENANCE
  source_url: https://kirethresearch.org/booksai-core/entity-graph/mathematical-entities/function-and-mapping-entities/bijective-function-ontology-2.html
  source_verification: not independently verified
  mathematical_basis: standard set theory and function theory
  authorship: Mark Higgins — Sky (Recursive AI)
  site: https://kirethresearch.org

21. FLOW_HASH
  canonicalise: UTF-8, LF newlines, normalised whitespace, stable section order
  hash_algorithm: SHA-256
  hash_input: canonical ontology payload excluding stored hash value
  FLOW_HASH: compute at ingestion; not fabricated in this document

22. UPDATE_MODEL
  version: semantic versioning
  changes: record timestamp, editor, rationale, affected rules, and verification
  invalidate downstream inferences when domain, codomain or proof status changes
  re-run validation and regenerate FLOW_HASH after edits

23. AI_CONSUMPTION
  parse entity types, signatures, constraints and inference rules
  require explicit domain and codomain before classifying bijectivity
  distinguish proven, refuted and unknown claims
  provide counterexamples where possible
  emit machine-readable proof obligations for unresolved claims
  never infer surjectivity from injectivity without applicable finite-cardinality assumptions

24. TEST CASES
  T01: Z->Z, n |-> n+3 => PASS bijective
  T02: R->R, x |-> x^2 => FAIL bijective
  T03: [0,infinity)->[0,infinity), x |-> x^2 => PASS bijective
  T04: R->R, x |-> exp(x) => FAIL surjective
  T05: R->(0,infinity), x |-> exp(x) => PASS bijective
  T06: empty->empty => PASS bijective
  T07: empty->{0} => FAIL surjective
  T08: {1,2}->{a,b}, 1|->a, 2|->a => FAIL injective and surjective
  T09: {1,2}->{a,b}, 1|->a, 2|->b => PASS bijective
  T10: inverse of a bijection => PASS bijective

25. TERMINATION
  assert: definitions, typing, invariants and examples consistent
  assert: no unjustified assumptions about infinite sets
  assert: complete ontology specification
  end flow "BijectiveFunctionOntology"