Correspondences and Applications: Sets and Functions

Posted on Mar 4, 2025 in Technology

Correspondences and Applications

Given two sets, A and B, a correspondence, denoted as f: A → B, is any rule or criterion that associates elements of set A with elements of set B. If an element x ∈ A is associated with an element y ∈ B, we say that “y is the image of x under the correspondence f” or that “x is the original element of y”. This is expressed as y = f(x).

In any correspondence f: A → B, we distinguish the following concepts:

  • Initial set of f: Set A.
  • Final set of f: Set B.
  • Original set of f: The set of all elements in A that have an image in B under f. Formally, Or. f = {x ∈ A | ∃ y ∈ B, y = f(x)} ⊆ A.
  • Image set of f: The set of all elements in B that are images of some element in A under f. Formally, Im f = {y ∈ B | ∃ x ∈ A, y = f(x)} ⊆ B.

Types of Correspondences

  • Inverse Correspondence: Given f: A → B, the inverse correspondence, f-1: B → A, associates each element of B with the element of A that was its original under f. That is, f-1(y) = x, where y = f(x).
  • Univocal Correspondence: A correspondence where each element of the initial set is associated with at most one element of the final set. Elements with an image have only one.
  • One-to-one Correspondence: A correspondence where elements of the initial set with an image have only one, and elements of the final set that are originals have only one. Both the correspondence and its inverse are univocal.

Functions

A function is a univocal correspondence between numerical sets.

  • Domain of f: The original set of f.
  • Range of f: The image set of f.

Applications

Given two sets A and B, an application f between A and B, denoted as f: A → B, is any correspondence in which every element of the initial set has a unique image. The original set coincides with the initial set. Symbolically: ∀x ∈ A, ∃! y ∈ B, y = f(x).

Types of Applications

  • Injective: If different elements always have different images. x ≠ y ⇒ [f(x) ≠ f(y)] or equivalently [f(x) = f(y)] ⇒ [x = y].
  • Surjective: An application f: A → B is surjective if every element of the final set has at least one original element. ∀y ∈ B, ∃ x ∈ A, f(x) = y <=> Im f = B.
  • Bijective: An application is bijective if it is both injective and surjective (same number of elements in A and B).

Composition of Applications

Given two applications f: A → B and g: B → C, the composition of f with g, denoted as g o f, is an application g o f: A → C defined as: ∀x ∈ A, (g o f)(x) = g(f(x)).

It is not always possible to compose two applications. A sufficient condition for composing f with g is that the final set of f is included in the initial set of g. A necessary and sufficient condition is that the image set of f is included in the original set of g.

Properties of Composition

  1. Not generally commutative: g o f ≠ f o g.
  2. Associative: If f: A → B, g: B → C, and h: C → D, then h o (g o f) = (h o g) o f.
  3. The composition of two injective applications is always another injective application.
  4. The composition of two surjective applications is always another surjective application.
  5. The composition of two bijective applications is always another bijective application.

Inverse Application

Given a bijective application f: A → B, the inverse application of f, denoted as f-1: B → A, associates each element y ∈ B with the element x ∈ A that was its original under f. That is, f-1(y) = x, where y = f(x).

Properties of the Inverse Application

  1. The inverse of a bijective application is always another bijective application.
  2. If f: A → B is a bijective application, then (f-1)-1 = f.
  3. If f: A → B and g: B → C are two bijective applications, then (g o f)-1 = f-1 o g-1.