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

Equivalence Relations

The following definitions refer to some a, b, c ∈ S for some arbitrary set S.

Also recall that, fore each paring (a, b), we can denote that they're related with a R b.

• Reflexive Relation - Defined as a = a.
  • Effectively, what this means is that every element is has a relation/paring to itself.
  • Ex: For a, b, c ∈ S, we must have some (a, a), (b, b), and (c, c) to be reflexive.
  • Ex: The statements "is married to" or "is a coworker of".
• Symmetric Relation - If a = b, then b = a.
  • Ex: For a, b, c ∈ S, if we have have some (a, b), then we must also have (b, a) to be symmetric.
  • Ex: The numbers 3 and 8 when applied to a modulus of 5.
• Transitive Relation - If a = b and b = c, then a = c.
  • Ex: For a, b, c ∈ S, if we have some (a, b) and (b, c), then we must also have (a, c) to be transitive.
• Equivalence Relation - A binary relation that is reflexive, symmetric, and transitive all at once.
• Irreflexive/Anti-Reflexive - A binary relation in which no elements relate to themselves.