Mathematics for AI Engineers

1. Total Domain Coverage:
   Every element in the domain A must be assigned an output in B.
   ∀a ∈ A, ∃b ∈ B such that (a, b) ∈ f.

2. Uniqueness (Single-Valuedness):
   No element in A can map to more than one distinct element in B.
   ∀a ∈ A, ∀b₁, b₂ ∈ B, ((a, b₁) ∈ f ∧ (a, b₂) ∈ f) ⟹ b₁ = b₂.

Valid Function (Every input has exactly 1 output):
  Domain A          Codomain B
   [ 1 ] -----------> [ x ]
   [ 2 ] -----------> [ y ]
   [ 3 ] -----------> [ y ]    (Two inputs can share an output!)

INVALID Relations (NOT Functions):
Case A (Unassigned input):     Case B (Multiple outputs for 1 input):
   [ 1 ] ----> [ x ]              [ 1 ] ----> [ x ]
   [ 2 ] (no arrow!)              [ 1 ] ----> [ y ] (Ambiguous!)
   [ 3 ] ----> [ y ]              [ 2 ] ----> [ z ]

Formal Definition:
∀a₁, a₂ ∈ A, a₁ ≠ a₂ ⟹ f(a₁) ≠ f(a₂)

Equivalent Contrapositive (Used for Direct Proofs):
∀a₁, a₂ ∈ A, f(a₁) = f(a₂) ⟹ a₁ = a₂

   INJECTIVE (1-to-1):             NOT INJECTIVE:
  Domain A      Codomain B       Domain A      Codomain B
   [ 1 ] ---------> [ a ]         [ 1 ] -----\
   [ 2 ] ---------> [ b ]         [ 2 ] -----> [ a ]  (Collision!)
   [ 3 ] ---------> [ c ]         [ 3 ] -----> [ b ]
                    [ d ]

Formal Definition:
∀b ∈ B, ∃a ∈ A such that f(a) = b

Range-Based Definition:
Range(f) = Codomain(B)

   SURJECTIVE (Onto):              NOT SURJECTIVE:
  Domain A      Codomain B       Domain A      Codomain B
   [ 1 ] ---------> [ x ]         [ 1 ] ---------> [ x ]
   [ 2 ] ---------> [ y ]         [ 2 ] ---------> [ y ]
   [ 3 ] ---------/               [ 3 ] ---------/ [ z ] (Uncovered!)
   (All of B is covered!)                          (z has no pre-image)

   BIJECTIVE (1-to-1 and Onto):
  Domain A             Codomain B
   [ a₁ ] -------------> [ b₁ ]
   [ a₂ ] -------------> [ b₂ ]
   [ a₃ ] -------------> [ b₃ ]
   [ a₄ ] -------------> [ b₄ ]
  - Every element in A maps to a unique element in B.
  - Every element in B is mapped to by exactly one element in A.

+-----------------------+------------------------+---------------------------------------------+
| Function              | Notation / Formula     | Key Properties & CS Applications            |
+-----------------------+------------------------+---------------------------------------------+
| Identity Function     | I_A(x) = x             | Bijection; neutral element for composition  |
| Constant Function     | f(x) = c               | Non-injective (for |A| > 1); range is {c}   |
| Floor Function        | ⌊x⌋                    | Largest integer ≤ x (Array index, buckets)  |
| Ceiling Function      | ⌈x⌉                    | Smallest integer ≥ x (Tree height, packets) |
| Fractional Part       | {x} = x - ⌊x⌋          | Range [0, 1); PRNGs, hashing routines       |
| Indicator Function    | χ_S(x) ∈ {0, 1}        | Membership filter in databases & bitsets    |
| Modulo Function       | mod_m(n) = n mod m     | Periodic hash mapping into [0, m-1]         |
+-----------------------+------------------------+---------------------------------------------+

Domain A            Codomain B            Codomain C
 [ x ] ---- f ----> [ f(x) ] ---- g ----> [ g(f(x)) ]
   |                                            ^
   \------------------ (g ∘ f) -----------------/

1. If (g ∘ f) is INJECTIVE ⟹ f MUST be INJECTIVE.
   (g is NOT required to be injective!)

2. If (g ∘ f) is SURJECTIVE ⟹ g MUST be SURJECTIVE.
   (f is NOT required to be surjective!)

3. If (g ∘ f) is BIJECTIVE ⟹ f is INJECTIVE and g is SURJECTIVE.

   Function f: A ⟶ B              Inverse Function f⁻¹: B ⟶ A
  Domain A      Codomain B       Domain B      Codomain A
   [ a₁ ] --------> [ b₁ ]        [ b₁ ] --------> [ a₁ ]
   [ a₂ ] --------> [ b₂ ]        [ b₂ ] --------> [ a₂ ]
   [ a₃ ] --------> [ b₃ ]        [ b₃ ] --------> [ a₃ ]

Intuition:
Putting on socks (f), then putting on shoes (g):  (g ∘ f)
To undo: Take off shoes FIRST (g⁻¹), then take off socks (f⁻¹):  (f⁻¹ ∘ g⁻¹)

+------------------------------+---------------------------------------+-----------------------------+
| Type of Function             | General Formula                       | Condition                   |
+------------------------------+---------------------------------------+-----------------------------+
| Total Functions              | nᵐ                                   | Always valid                |
| Injective Functions (1-to-1) | P(n, m) = n! / (n - m)!               | m ≤ n (0 if m > n)          |
| Surjective Functions (Onto)  | n! × S(m, n)                          | m ≥ n (0 if m < n)          |
|                              | = ∑(k=0 to n) (-1)ᵏ C(n, k) (n-k)ᵐ   |                             |
| Bijective Functions          | n!                                    | m = n (0 if m ≠ n)          |
| Strictly Increasing (A ⊆ B)  | C(n, m)                               | Ordered sets, m ≤ n         |
| Non-Decreasing (A ⊆ B)       | C(n + m - 1, m)                       | Stars and bars allocation   |
+------------------------------+---------------------------------------+-----------------------------+

Stirling Numbers Triangle (Values of S(m, n)):
m \ n |  1    2    3    4    5
------+------------------------
  1   |  1
  2   |  1    1
  3   |  1    3    1
  4   |  1    7    6    1
  5   |  1   15   25   10    1
  6   |  1   31   90   65   15    1

import math
from itertools import product
from typing import Set, Dict, Any, Tuple, Optional

class DiscreteFunction:
    """
    Represents and analyzes a discrete function f: domain -> codomain.
    """
    def __init__(self, domain: Set[Any], codomain: Set[Any], mapping: Dict[Any, Any]):
        self.domain = domain
        self.codomain = codomain
        self.mapping = mapping
        self._validate()

    def _validate(self):
        # 1. Every domain element must have an assignment
        if set(self.mapping.keys()) != self.domain:
            raise ValueError("Invalid function: Domain mismatch or unassigned inputs.")
        # 2. Every mapped value must belong to codomain
        for val in self.mapping.values():
            if val not in self.codomain:
                raise ValueError(f"Value {val} not in codomain {self.codomain}.")

    def range(self) -> Set[Any]:
        return set(self.mapping.values())

    def is_injective(self) -> bool:
        # Check if all output values are unique
        return len(self.mapping.values()) == len(set(self.mapping.values()))

    def is_surjective(self) -> bool:
        # Check if range equals codomain
        return self.range() == self.codomain

    def is_bijective(self) -> bool:
        return self.is_injective() and self.is_surjective()

    def inverse(self) -> Optional['DiscreteFunction']:
        if not self.is_bijective():
            return None
        inv_mapping = {v: k for k, v in self.mapping.items()}
        return DiscreteFunction(self.codomain, self.domain, inv_mapping)

    def compose(self, g: 'DiscreteFunction') -> 'DiscreteFunction':
        """Computes (g ∘ self), applying self first, then g."""
        if not self.range().issubset(g.domain):
            raise ValueError("Cannot compose: Range of f is not subset of domain of g.")
        comp_mapping = {x: g.mapping[self.mapping[x]] for x in self.domain}
        return DiscreteFunction(self.domain, g.codomain, comp_mapping)

# -------------------------------------------------------------
# Function Counting Formulas
# -------------------------------------------------------------
def stirling_second(m: int, n: int) -> int:
    """Calculates S(m, n) using dynamic programming."""
    if n == 0 or n > m:
        return 0
    if n == 1 or n == m:
        return 1
    
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, min(i, n) + 1):
            if j == 1 or j == i:
                dp[i][j] = 1
            else:
                dp[i][j] = dp[i-1][j-1] + j * dp[i-1][j]
    return dp[m][n]

def count_onto_functions(m: int, n: int) -> int:
    """Counts total surjective functions from m elements to n elements."""
    if m < n:
        return 0
    return math.factorial(n) * stirling_second(m, n)

# -------------------------------------------------------------
# Verification & Demonstration
# -------------------------------------------------------------
if __name__ == "__main__":
    A = {1, 2, 3}
    B = {'a', 'b', 'c'}
    f_map = {1: 'a', 2: 'b', 3: 'c'}
    f = DiscreteFunction(A, B, f_map)

    print(f"f is Injective:  {f.is_injective()}")   # True
    print(f"f is Surjective: {f.is_surjective()}")  # True
    print(f"f is Bijective:  {f.is_bijective()}")   # True

    inv_f = f.inverse()
    print(f"f⁻¹ mapping:     {inv_f.mapping}")       # {'a': 1, 'b': 2, 'c': 3}

    # Counting Example: m = 4, n = 3
    total_fns = 3 ** 4
    injective_fns = 0  # since 4 > 3
    onto_fns = count_onto_functions(4, 3)
    
    print(f"\nCounting for |A|=4, |B|=3:")
    print(f"  Total Functions:     {total_fns}")      # 81
    print(f"  Injective Functions: {injective_fns}")  # 0
    print(f"  Surjective (Onto):   {onto_fns}")        # 36