Functions and Their Properties

In discrete mathematics and computer science, functions serve as the foundational mechanism for mapping elements between sets. This guide explores the formal definitions, algebraic properties, and distinct classifications of functions that underpin computational models, cryptography, and relational database theories.

1. Formal Definition and Basic Terminology

Let $X$ and $Y$ be any two sets. A function (or mapping/transformation) $f$ from $X$ to $Y$ , denoted by $f: X \to Y$ , is an assignment of exactly one element $f(x) \in Y$ to each element $x \in X$ .

Mathematically, a function is a special type of relation. If $\langle x, y \rangle \in f$ (often written as $(x, y) \in f$ ), we say that $y$ is the image of $x$ under , and is a of under . We express this relationship via the classic equation:

$y = f(x)$

1.1 Structural Terminology

For any function $f: X \to Y$ :

Domain: The set $X$ is the domain of $f$ , denoted by $D_f$ .
Codomain: The set $Y$ is the codomain of $f$ , denoted by $R_f$ (or target set).

text

       DOMAIN (X)                  CODOMAIN (Y)
     +------------+              +------------+
     |   x1 *-----+------------->|* f(x1)     |
     |            |              |            |
     |   x2 *-----+-----\        |* f(x2)     |
     |            |      \------->|           |  <- RANGE (Subset of Y)
     |   x3 *-----+------------->|* f(x3)     |
     +------------+              |            |
                                 |   y4 *     |  <- Element in Codomain
                                 +------------+     but not in Range

1.2 Defining a Function Formally

We can rigorously define the condition for a mapping $f$ to be a function using first-order logic. The assertion " $f$ is a function" is logically equivalent to the following formulations:

No split mappings: $\neg \exists x, y_1, y_2 \left( (x, y_1) \in f \wedge (x, y_2) \in f \wedge y_1 \neq y_2 \right)$

1.3 Arithmetic of Functions

When functions map real numbers to real numbers ( $f, g: \mathbb{R} \to \mathbb{R}$ ), we can define their algebraic sum and product point-wise:

Addition: $(f+g)(x) = f(x) + g(x)$
Multiplication: $(f \times g)(x) = f(x) \times g(x)$

2. Special Real-Valued and Number-Theoretic Functions

Discrete mathematics frequently leverages specific integer-boundary functions over the real number domain, alongside fundamental inductive sequences.

2.1 The Floor Function

The floor function assigns to the real number $x$ the largest integer that is less than or equal to $x$ . It is denoted by $\lfloor x \rfloor$ .

$\lfloor x \rfloor = \max \{ n \in \mathbb{Z} \mid n \le x \}$

2.2 The Ceiling Function

The ceiling function assigns to the real number $x$ the smallest integer that is greater than or equal to $x$ . It is denoted by $\lceil x \rceil$ .

$\lceil x \rceil = \min \{ n \in \mathbb{Z} \mid n \ge x \}$

Key Structural Properties:

If $x \in \mathbb{Z}$ , then: $\lfloor x \rfloor = \lceil x \rceil = x$
If $x \notin \mathbb{Z}$ , the functions act asymmetric on negative numbers:

Examples:

$\lfloor 1.6 \rfloor = 1$ , whereas $\lceil 1.6 \rceil = 2$ .
$\lfloor -1.4 \rfloor = -2$ , whereas $\lceil -1.4 \rceil = -1$ .

2.3 Peano's Successor Function

Let $P$ be the set of all positive integers $\mathbb{Z}^+$ . The successor function $\sigma: P \to P$ is defined as:

$\sigma(n) = n + 1$

This function serves as the basis for Peano's Axioms, establishing the foundational arithmetic structure of natural numbers:

$\sigma(1) = 2$
$\sigma(2) = 3$
$\sigma(3) = 4$

3. Properties of Functions: Injectivity, Surjectivity, and Bijectivity

Functions are classified based on the uniqueness of their mappings and the coverage of their codomain.

3.1 Injective (One-to-One) Functions

A function $f: A \to B$ is injective (or an injection) if and only if no two distinct elements of the domain map to the same element of the codomain.

text

      INJECTIVE (1-1)                NON-INJECTIVE
    A               B              A               B
  +---+           +---+          +---+           +---+
  | 1*+---------->|*a |          | 1*+---------->|*a |
  |   |           |   |          |   |          /|   |
  | 2*+---------->|*b |          | 2*+---------/ |   |
  |   |           |   |          |   |           |   |
  | 3*+---------->|*c |          | 3*+---------->|*b |
  +---+           +---+          +---+           +---+

Formal Logic Definitions:

$\forall x, y \in A \left( x \neq y \implies f(x) \neq f(y) \right)$ Or, equivalent by contraposition:

If $f$ is injective, the cardinality of the domain $|A|$ must be less than or equal to the cardinality of the codomain $|B|$ ( $|A| \le |B|$ ).

3.2 Surjective (Onto) Functions

A function $f: A \to B$ is surjective (or a surjection) if and only if its range equals its codomain. This means every element in $B$ has at least one pre-image in $A$ .

text

      SURJECTIVE (ONTO)              NON-SURJECTIVE
    A               B              A               B
  +---+           +---+          +---+           +---+
  | 1*+---------->|*a |          | 1*+---------->|*a |
  |   |          /|   |          |   |           |   |
  | 2*+---------/ |   |          | 2*+---------->|*b |
  |   |           |   |          |   |           |   |
  | 3*+---------->|*b |          | 3*+---------->|*c | (unmapped)
  +---+           +---+          +---+           +---+

Formal Logic Definition:

$\forall b \in B, \exists a \in A \text{ such that } f(a) = b$

Analytic Example:

Consider functions over the real numbers $\mathbb{R}$ :

$f(x) = x^3$ is surjective because for every real number $y$ , there exists a real pre-image $x = \sqrt[3]{y}$ .

3.3 Bijective Functions

A function $f: A \to B$ is a bijection (or a one-to-one correspondence) if and only if it is simultaneously injective and surjective.

text

                 BIJECTIVE MAPPING (1-1 & ONTO)
                   A                   B
                 +---+               +---+
                 | 1*+-------------->|*a |
                 |   |               |   |
                 | 2*+-------------->|*b |
                 |   |               |   |
                 | 3*+-------------->|*c |
                 +---+               +---+

A bijection represents a perfect pairing between elements of $A$ and $B$ . If a bijection exists between two finite sets $A$ and $B$ , then $|A| = |B|$ .

4. Function Composition and Invertibility

Functions can be chain-linked together to form complex operations, and reversed if they meet strict structural criteria.

4.1 Composition of Functions

Let $g: A \to B$ and $f: B \to C$ be functions. The composition of $f$ and $g$ , denoted by $f$ , is a function from to defined by:

$(f \circ g)(x) = f(g(x))$

Note that the composition $f \circ g$ is only defined when the range of $g$ is a subset of the domain of $f$ .

text

       A                  B                  C
     +---+              +---+              +---+
     | x*+------------->|g(x|              |   |
     +---+      g       +---+-----\        |   |
                                   \------>|*  | f(g(x))
                                      f    +---+
     \_______________________________________/
                      f o g

4.2 The Identity Function

For any set $A$ , the identity function $I_A: A \to A$ is defined by:

$\forall a \in A, \quad I_A(a) = a$

The identity function acts as the identity element under the operation of function composition. It is trivial to show that $I_A$ is always bijective.

4.3 Inverse of a Function

If $f: A \to B$ is a bijection, there exists an inverse function $f^{-1}: B \to A$ that reverses the mapping of $f$ .

$f^{-1}(b) = a \iff f(a) = b$

text

                  f (Forward) ->
             A                      B
           +---+                  +---+
           | a*+----------------->|*b |
           +---+                  +---+
                 <- f^-1 (Inverse)

Properties of Inverses:

If $f: A \to B$ is bijective with inverse $f^{-1}: B \to A$ , then:

$(f^{-1} \circ f)(a) = I_A(a) = a$ for all $a \in A$ .

If a function is not bijective, its inverse relation is not a function because it will either map a single element to multiple pre-images (violating uniqueness) or fail to map some elements entirely.

5. From Relations to Functions

To understand the algebraic structure of functions, they must be situated within the broader framework of binary relations.

5.1 Binary Relations

A binary relation $R$ from set $A$ to set $B$ is any subset of the Cartesian product $A \times B$ :

$R \subseteq A \times B$

We write $aRb$ to denote that $(a, b) \in R$ .

Key Differences Between Relations and Functions:

Relations: An element $a \in A$ can map to multiple elements in $B$ , or to none at all.
Functions: Every element $a \in A$ must map to exactly one element $b \in B$ . Thus, functions are highly constrained generalizations of relations.

5.2 Equivalence Relations vs. Posets

While functions are directed, single-valued mappings, other relations structure sets in symmetric or hierarchical ways:

Equivalence Relation: A relation that is reflexive ( $aRa$ ), symmetric ( $aRb \implies bRa$ ), and transitive ( $aRb \wedge bRc \implies aRc$ ). It partitions a set into disjoint equivalence classes:

text

          Hasse Diagram of Divides relation on {2, 3, 6, 12, 18}:
          
                              12      18
                               \     /  \
                                6   /    \
                               / \ /      \
                              2   3        *

Summary

A function $f: X \to Y$ is a subset of $X \times Y$ such that every $x \in X$ is mapped to a unique $y \in Y$ .

Assessed progress

Functions and Their Properties

Functions and Their Properties

1. Formal Definition and Basic Terminology

1.1 Structural Terminology

1.2 Defining a Function Formally

1.3 Arithmetic of Functions

2. Special Real-Valued and Number-Theoretic Functions

2.1 The Floor Function

2.2 The Ceiling Function

Key Structural Properties:

Examples:

2.3 Peano's Successor Function

3. Properties of Functions: Injectivity, Surjectivity, and Bijectivity

3.1 Injective (One-to-One) Functions

Formal Logic Definitions:

3.2 Surjective (Onto) Functions

Formal Logic Definition:

Analytic Example:

3.3 Bijective Functions

4. Function Composition and Invertibility

4.1 Composition of Functions

4.2 The Identity Function

4.3 Inverse of a Function

Properties of Inverses:

5. From Relations to Functions

5.1 Binary Relations

Key Differences Between Relations and Functions:

5.2 Equivalence Relations vs. Posets

Summary

Key Concepts

Mathematical Function

Injective Function

Surjective Function

Bijective Function

Composition of Functions

Quick Check

Discrete Mathematical Structures

Discrete Mathematical Structures