Sets and Functions

Date: 2025-11-22

A set is defined by the objects that belong to it, which can include other sets. The notations {a, b, c} and {b, c, a} are considered equivalent because they define a set with the exact same elements.

There are two primary ways to define a set:

    Listing its elements - {1, 2, 3}

    Specifying a condition that its elements must satisfy.

A function is denoted as follows:
Name: Set ⇾ Set
This means that the function assigns to each element from the first set (the domain) exactly one element from the second set (the codomain). This is the formal definition of a function.

Let's define two sets:
    A: {a, b, c, d}
    B: {0, 1}

Now, define a function f: A ⇾ B such that:
    a ⇾ 1
    b ⇾ 0
    c ⇾ 1
    d ⇾ 1

The set A is called the domain of the function f, and the set B is called its codomain.
Function Application

Let the notation "function object" mean applying the function to an object. Then, the expressions "f c" and "1" are equivalent because f has the property of mapping c from set A to 1 in set B.
A Second Function

Now, consider a function g: {0, 1} ⇾ {a, b, c, d}, defined as:
    0 ⇾ a
    1 ⇾ d

Let's evaluate function g. To do this, we substitute the value and replace it according to the arrow. This process is called function application, or evaluation:

We introduce the symbol '=>' to express the transition of an expression to its reduced form (evaluation).
    g 0 => a
    g 1 => d

Function Composition

Function composition creates a new function that is equivalent to applying multiple functions in sequence.

Composition is denoted by the symbol ∘. Thus, the composition of functions f and g is written as f ∘ g.

Composition is only possible if the codomain of the first function is the domain of the second function.

In our case:
    f: {a, b, c, d} ⇾ {0, 1} has codomain {0, 1}
    g: {0, 1} ⇾ {a, b, c, d} has domain {0, 1}

Therefore, the composition g ∘ f: A ⇾ A is valid.

Evaluating a Composition
The notation g f b means we first compute f b and then substitute the result into the function g. In other words, evaluation proceeds from right to left.

Let's compute (g ∘ f) b:
    f b ⇾ 0
    Substitute 0 into g: g 0 ⇾ a

The result is a sequential transformation: b ⇾ 0 ⇾ a, or simply b ⇾ a.

The composition f ∘ g is also possible in this case, resulting in a function {0, 1} ⇾ {0, 1}.

Let's compute f ∘ g 0:
    g 0 ⇾ a
    Substitute a into f: f a ⇾ 1

Evaluating process of the f ∘ g 0:
"f∘g 0" => "f a" => "1"