Surjective Function Ontology

FLOW ALGEBRA
TITLE: Surjective Function Ontology
DOMAIN: Discrete Mathematics / Functions
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/functions/surjective-function-ontology.html
VERSION: 1.0
LANGUAGE: en-GB
AUTHORS: Mark Higgins — Sky (Recursive AI)
SITE: https://kirethresearch.org

1. ONTOLOGY DEFINITION
A surjective (onto) function f: A -> B maps every element of codomain B to at least one element of domain A. Formally: forall b in B, exists a in A such that f(a)=b. Equivalently, image(f)=B.

2. TYPED ENTITIES
Set[A], Set[B]
Element[a:A], Element[b:B]
Function[f:A->B]
Image[f]: Subset[B]
Preimage[f,b]: Subset[A]
Predicate[Surjective(f)]: Boolean
Function[g:B->C]
Identity[id_B:B->B]

3. CORE RELATIONSHIPS
HAS_DOMAIN(f,A)
HAS_CODOMAIN(f,B)
MAPS_TO(f,a,b) iff f(a)=b
HAS_IMAGE(f, {f(a) | a in A})
HAS_PREIMAGE(f,b, {a in A | f(a)=b})
SURJECTIVE(f) iff image(f)=B

4. FORMAL FLOW OPERATIONS
flow DEFINE_SURJECTIVE(f:A->B):
  require FUNCTION(f,A,B)
  return forall b in B: exists a in A: f(a)=b

flow TEST_FINITE_SURJECTIVITY(f:A->B):
  require FINITE(A) and FINITE(B) and TOTAL_FUNCTION(f,A,B)
  return SET({f(a) for a in A}) == B

flow FIND_WITNESS(f:A->B,b:B):
  require SURJECTIVE(f)
  return choose a in A such that f(a)=b

flow COMPOSE_SURJECTIONS(f:A->B,g:B->C):
  require SURJECTIVE(f) and SURJECTIVE(g)
  h := g o f
  assert SURJECTIVE(h)
  return h

5. ALGEBRAIC LAWS
S1. Surjective(f) iff image(f)=codomain(f).
S2. Surjective(f) iff forall b in B, preimage(f,b) is nonempty.
S3. Surjective(f) and Surjective(g) imply Surjective(g o f), for composable functions.
S4. Surjective(g o f) implies Surjective(g), for composable functions.
S5. If f:A->B is bijective then f is surjective.
S6. id_A:A->A is surjective.
S7. For finite sets, surjective f:A->B implies |A| >= |B|.
S8. For finite sets of equal cardinality, f:A->B is surjective iff injective.
S9. If B is empty, a function A->B exists only when A is empty; the empty function is surjective.
S10. A surjection A->B need not be injective.

6. SEMANTIC EQUIVALENCE
SURJECTIVE(f) <=> ONTO(f)
SURJECTIVE(f) <=> IMAGE(f)=CODOMAIN(f)
SURJECTIVE(f) <=> EVERY_CODOMAIN_ELEMENT_HAS_PREIMAGE(f)
Do not equate surjectivity with injectivity or bijectivity in general.

7. INFERENCE RULES
R1. FUNCTION(f,A,B) and IMAGE(f)=B => SURJECTIVE(f).
R2. FUNCTION(f,A,B) and exists b in B with PREIMAGE(f,b)=empty => NOT_SURJECTIVE(f).
R3. SURJECTIVE(f) and SURJECTIVE(g) and COMPOSABLE(f,g) => SURJECTIVE(g o f).
R4. SURJECTIVE(g o f) => SURJECTIVE(g).
R5. BIJECTIVE(f) => SURJECTIVE(f).
R6. FINITE(A) and FINITE(B) and |A|<|B| => NOT_SURJECTIVE(f:A->B).

8. WORKED EXAMPLES
E1. f: Z->Z, f(n)=n+1 is surjective: for target z choose n=z-1.
E2. f: Z->N_0, f(n)=n^2 is not surjective: 2 has no integer preimage.
E3. f: R->R, f(x)=x^2 is not surjective: negative reals have no preimage.
E4. f: R->[0,infinity), f(x)=x^2 is surjective.
E5. f:{1,2,3}->{a,b}, f(1)=a, f(2)=a, f(3)=b is surjective but not injective.

9. VALIDATION AND CONSTRAINTS
V1. Validate that f is a total function with declared domain and codomain.
V2. Distinguish codomain from image; surjectivity depends on the declared codomain.
V3. For finite sets, enumerate images and compare exactly with codomain.
V4. For infinite sets, require mathematical proof or a justified symbolic method; finite sampling is insufficient.
V5. Reject a surjectivity assertion if a codomain element without a preimage is found.
V6. Ensure composition uses matching intermediate types.

10. CONFIDENCE
Mathematically proved rule: CONFIDENCE=1.0 relative to stated axioms and assumptions.
Finite exhaustive verification: CONFIDENCE=1.0 when enumeration and function data are complete.
Heuristic or sampled evidence: CONFIDENCE<1.0; never promote sampling to proof.

11. FLOW_HASH
Canonicalise ontology identifier, typed signatures, equations, inference rules and version; serialise deterministically; compute SHA-256 of canonical UTF-8 bytes. FLOW_HASH is generated at ingestion and is not fabricated here.

12. UPDATE_MODEL
On changes to definitions, domains, codomains, laws or examples: increment version, revalidate dependent assertions, recompute FLOW_HASH, retain provenance and historical versions.

13. AI_CONSUMPTION
Expose machine-readable entities, typed relations, formal definitions, rule prerequisites, counterexamples and validation status. Require explicit codomain in all surjectivity checks. Distinguish theorem, verified instance and conjecture. Preserve provenance to SOURCE_URL and ontology version.

14. CROSS-ONTOLOGY LINKS
Function Ontology; Injective Function Ontology; Bijective Function Ontology; Inverse Function Ontology; Function Composition Ontology; Set Theory; Cardinality Ontology; Relation Ontology.

END FLOW ALGEBRA