Skip to main content

Functions Are Behavior on a Domain

What This Concept Is​

A function $f : A \rightarrow B$ assigns to each element of the domain $A$ exactly one element of the codomain $B$. Formally, $f$ is a subset of the Cartesian product $A \times B$ satisfying:

  • totality: for every $a \in A$, there exists at least one $b \in B$ with $(a, b) \in f$;
  • functionality (single-valuedness): for every $a \in A$, at most one $b \in B$ has $(a, b) \in f$.

The critical conceptual shift beginners must make: a function is identified by its behavior on the domain, not by the formula used to describe it. Two different formulas that agree on every input of a shared domain define the same function. One formula over two different domains defines two different functions.

Key components to name explicitly each time:

  • domain $A$ (the set of allowed inputs);
  • codomain $B$ (the declared output set);
  • rule $f(a)$ (how outputs are computed);
  • range (or image of $A$): ${f(a) : a \in A}$, the set of values actually achieved -- a subset of $B$, possibly a proper subset.

Partial function terminology: if the rule is only defined on some $A' \subsetneq A$, the function is partial on $A$. Some authors use $f : A \rightharpoonup B$ for this case; whether you treat a partial function as a function on the reduced domain $A'$ or as a different kind of object is a convention to fix early.

Why It Matters Here​

Later modules rely on function reasoning for graph maps ($V \to V$), state transitions ($S \times \Sigma \to S$), relations ($A \to {0, 1}$ indicator functions), algorithm definitions ($\text{input} \to \text{output}$), and recursive specifications. If you think a function is "just a formula," you miss domain restrictions, partiality, codomain vs range distinctions, and equality-of-functions arguments.

Functions are also the only way to state most theorems of later modules crisply. "There is a bijection between finite subsets of $\mathbb{N}$ and finite sequences of naturals" is a single sentence that encodes an entire combinatorial equivalence. Without fluent function language, the same statement balloons into prose that cannot be checked step by step.

The discipline of naming the domain also catches a class of bugs that no amount of algebra catches. "2 divided by 0" is undefined; "the function $f(x) = 1/x$" is ambiguous until you fix the domain to $\mathbb{R} \setminus {0}$. Once the domain is stated, the function is well-defined; without it, every correctness argument is contingent on which inputs a reader assumes.

This same discipline is why strongly typed languages feel "safer": the type signature forces the programmer to commit to a domain and a codomain before writing a single line of rule-body. The function-as-behavior perspective is exactly the compiler's view.

In engineering, the same rigor shows up as function signatures in typed languages, API contracts (domain = request shapes, codomain = response shapes), and pure-function discipline in functional programming. A student who can read "$f : A \to B$" fluently can read a Rust or Haskell signature fluently; the skill transfers directly.

Another pragmatic payoff: specifications, tests, and proofs all use function equality as their natural equivalence. "The implementation behaves the same as the spec on every valid input" is a function-equality claim. Getting this right early means later chapters on correctness, refinement, and equivalence of programs land naturally.

Concrete Examples​

Example 1 -- same rule, different domains, different functions.

Let $f(x) = x^2$ on $\mathbb{R}$ and $g(x) = x^2$ on $\mathbb{Z}$. These are different functions. They agree where both are defined, but their graphs as subsets of different products ($\mathbb{R} \times \mathbb{R}$ vs $\mathbb{Z} \times \mathbb{Z}$) differ, and questions like "is the function surjective?" have different answers ($f$ is not surjective onto $\mathbb{R}$; $g$ is not surjective onto $\mathbb{Z}$).

Example 2 -- same domain, different formulas, same function.

Let $h_1(x) = (x + 1)^2$ and $h_2(x) = x^2 + 2x + 1$ on $\mathbb{R}$. The formulas differ; the functions are equal because $h_1(x) = h_2(x)$ for every $x \in \mathbb{R}$ (by the distributive law). Function equality is pointwise equality on the shared domain.

Example 3 -- codomain vs range.

Let $s : \mathbb{Z} \to \mathbb{Z}$ be $s(n) = n^2$. The codomain is $\mathbb{Z}$; the range is ${0, 1, 4, 9, 16, \ldots} = \mathbb{Z}{\ge 0} \cap {k^2 : k \in \mathbb{Z}{\ge 0}}$ -- a proper subset of the codomain. The claim "$s$ maps $\mathbb{Z}$ onto $\mathbb{Z}$" (surjectivity) is false; the claim "$s$ has range a subset of $\mathbb{Z}$" is trivially true.

Example 4 -- the subtle case of "is this actually a function?"

Proposed rule: $r : \mathbb{Q} \to \mathbb{Z}$ defined by $r(p/q) = p$ where $p/q$ is written as a fraction.

This fails functionality: $1/2$ and $2/4$ are the same rational, so $r(1/2) = 1$ and $r(2/4) = 2$, contradicting single-valuedness. The correct move is to declare that $r$ is well-defined only on a canonical representation -- and then it is a function on that representation set, not on $\mathbb{Q}$ as an equivalence class. Functions respect equality of inputs; if two names for the same input give different outputs, you do not have a function.

Example 5 -- function equality as a proof obligation.

To prove two functions $f, g : A \to B$ are equal, the formal obligation is to show $\forall a \in A,\ f(a) = g(a)$. That is a universal statement, so the canonical proof is "let $a \in A$ be arbitrary; show $f(a) = g(a)$." This is called function extensionality and is the fundamental move underlying equational reasoning in every later chapter on algebraic structures and program correctness.

Concretely, to show $h_1 = h_2$ from Example 2: let $x \in \mathbb{R}$. Then $h_1(x) = (x+1)^2 = x^2 + 2x + 1 = h_2(x)$ by the distributive law. Since $x$ was arbitrary, $h_1 = h_2$. This three-line proof is the template.

Common Confusion / Misconceptions​

  1. Range confused with codomain. The range is the set of values actually achieved; the codomain is the declared output set. Surjectivity is precisely range = codomain. Using "range" to mean "codomain" loses an important distinction and often causes surjectivity errors.
  2. "Function = formula." Many functions cannot be written as a single closed-form formula (e.g., the characteristic function of the primes), but they are still functions. Conversely, two different formulas can denote the same function.
  3. Partial function called a function without qualification. $f(x) = 1/x$ on $\mathbb{R}$ is not a function in the strict sense (it is undefined at $0$). Either restrict the domain to $\mathbb{R} \setminus {0}$ or label the object a partial function.
  4. Ignoring well-definedness. When defining a function on equivalence classes (concept 14) or quotient structures, you must prove the rule does not depend on the representative chosen. Example 4 above is the warning case.
  5. Confusing a function with its graph. The graph is the subset of $A \times B$; the function is the behavior. In most treatments they are identified, but conceptually the function is the data of "what does $f$ do to each input."
  6. "Surjective" as a property of the formula. Surjectivity depends on both domain and codomain. The same rule $f(x) = 2x$ is surjective as $\mathbb{Z} \to 2\mathbb{Z}$ but not as $\mathbb{Z} \to \mathbb{Z}$. Changing either side can flip the answer.
  7. Assuming uniqueness of output from uniqueness of derivation. A rule that uses a specific representative (e.g., "reduce to lowest terms, then take numerator") is single-valued on equivalence classes because the representative is canonical. Dropping the canonical choice breaks single-valuedness.

How To Use It​

Whenever a function $f$ appears in a definition or proof, do the following before proceeding:

  1. Identify the domain $A$ explicitly.
  2. Identify the codomain $B$ explicitly.
  3. Understand the rule that computes $f(a)$ for arbitrary $a \in A$.
  4. Verify the rule is total on $A$ (every input has an output) and single-valued (each input has exactly one output).
  5. If defining by cases or by a canonical representative, prove well-definedness.
  6. For comparing two functions, check they share domain, codomain, and pointwise behavior.
  7. For claims about injectivity/surjectivity, use the domain and codomain explicitly -- these properties are relative to them.
  8. If restricting or extending a function, name the new domain/codomain: $f|_{A'} : A' \to B$ is a different object than $f : A \to B$.

Transfer / Where This Shows Up Later​

  • Semester 2 (algorithms). An algorithm is a computable function from inputs to outputs. Correctness proofs establish the algorithm-function equals the specification-function on the domain of valid inputs.
  • Semester 3 (software design). Type signatures in OO and functional languages are function signatures; method dispatch is selecting the right function based on input type. Purity of a function means its behavior depends only on its domain input.
  • Semester 4 (systems). System calls are functions with structured domains (arguments, file descriptors) and codomains (return values, error codes). Their contracts are domain/codomain specifications.
  • Semester 6 (databases). A database query is a function from database states to result sets. Schema migrations are functions on the space of schemas.
  • Semester 7 (architecture). Bounded-context translation is a function from one context's concepts to another's. Anti-corruption layers are explicit function objects.
  • Semester 9+ (PL/verification). Denotational semantics maps programs to mathematical functions; the domain/codomain discipline is the bedrock on which every later formal method (Hoare logic, refinement types, separation logic) is built.

Check Yourself​

  1. Can two functions with the same formula be different objects? Construct an example with different domains.
  2. Why is the domain part of the definition of a function? What goes wrong if it is omitted?
  3. Distinguish codomain from range with a concrete example where they differ.
  4. What are the two conditions a subset $f \subseteq A \times B$ must satisfy to be a function?
  5. Why must a function on an equivalence class be proven "well-defined"?
  6. Is the empty function $\emptyset : \emptyset \to B$ a valid function? For any $B$? Justify.
  7. State function extensionality as a proof obligation and give the shape of a proof that two functions are equal.

Mini Drill or Application​

For each function description, list the domain, codomain, whether the rule is total, and whether the rule is single-valued on the given domain. If the rule fails a condition, explain how to fix it:

  1. $f(x) = 1/x$ on $\mathbb{R}$
  2. $g(n) = n \bmod 2$ from $\mathbb{Z}$ to ${0, 1}$
  3. $h(S) = |S|$ from finite subsets of $\mathbb{Z}$ to $\mathbb{Z}_{\ge 0}$
  4. $r(p/q) = p + q$ on $\mathbb{Q}$ (as fractions in lowest terms? as arbitrary fractions?)
  5. $s(x) = \sqrt{x}$ on $\mathbb{R}$ to $\mathbb{R}$
  6. $t(A) = A \cup {0}$ from $\mathcal{P}(\mathbb{Z})$ to $\mathcal{P}(\mathbb{Z})$

Also: compare the functions $u(x) = (x+1)(x-1)$ and $v(x) = x^2 - 1$ on $\mathbb{R}$. Are they the same function? Justify.

For at least two of the examples above, identify the range explicitly and decide whether the stated codomain equals the range.

Read This Only If Stuck​

Closing Note​

The single habit that pays off most here is writing every function as the triple $(A, B, \text{rule})$ -- domain, codomain, and rule -- even when it looks redundant. Most function-level bugs in both proofs and code come from an implicit or shifting domain.

Your own working notes should literally spell out $A$, $B$, and the rule at the top of each definition. That paragraph of housekeeping often catches the bug before the proof begins.

When you see f : A -> B in later chapters, read it as "behavior assigning each element of $A$ exactly one element of $B$," not as "the formula $f$." This small reframing generalises directly to type signatures, API contracts, and specification-based reasoning in every later semester. Functions are the lingua franca of formal specification, and getting the domain/codomain discipline right at this level pays compounding dividends thereafter.