Mathematics/Discrete Math/Relations and Functions

Recall from Discrete Math - Sets (basic set operations) that a Cartesian Product is a mapping of all possible ordered pairs from sets A={a1, a2, ...} and B={b1, b2, ...} such that A x B={(a1, b1), (a1, b2), ..., (a2, b1), (a2, b2), ...}.

Using this fact, we can define some terms:

Function Definitions

• Binary Relation - A subset of the cartesian product A x B for some arbitrary, non-zero sets A and B.
  • When an element a ∈ A is paired with an element b ∈ B through a binary relation, we can denote that they're related with a R b.
• Function - A binary relation such that every element in A corresponds to, at most, one element in B.
• Domain - Given all possible {(a, b) ∈ f | a ∈ A, b ∈ B}, the "domain" is the full set A.
• Codomain - Given all possible {(a, b) ∈ f | a ∈ A, b ∈ B}, the "codomain" is the full set B.
• Argument - Given all possible {(a, b) ∈ f | a ∈ A, b ∈ B}, each a can be considered an "argument".
• Value - Given all possible {(a, b) ∈ f | a ∈ A, b ∈ B}, each b can be considered a "value".
• Finite Sequence - A function that has at most n domain → codomain pairings.
  • In simpler terms, a function that has a limited/set number of a → b mappings.
• Infinite Sequence - A function that has a non-terminating/infinitely extending number of domain → codomain pairings.

Note that two functions are considered equivalent if they have the same domain and codomain.

Function Properties

• Image - The set of all output values a function may have.
• Preimage/Inverse Image - The set of all elements in a domain that map to the codomain.
• Injection - "One-to-one". Aka, a function where each element in the codomain is mapped to by, at most, one element of the domain.
  • To put it another way, each input provides exactly one output.
• Surjection - "Onto". Aka, a function where each element of the codomain is mapped to by, at least, one element of the domain.
  • To put it another way, each possible output corresponds to at least one input.
• Bijection - "One-to-one Correspondence". Aka, a function that is both Injective and Surjective at the same time.
  • Aka, each input relates to exactly one output, all possible outputs correspond to exactly one input each.

A function has an 'inverse iff it's bijective. We can then define the inverse as f^-1(b)=a iff f(a)=b