Mathematics/Discrete Math/Relations and Functions: Difference between revisions

From Dev Wiki
Jump to navigation Jump to search
(Add function properties)
(Create equivalence relations section)
Line 29: Line 29:


A function has an '''inverse'' iff it's bijective. We can then define the inverse as <code>f^-1(b)=a iff f(a)=b</code>
A function has an '''inverse'' iff it's bijective. We can then define the inverse as <code>f^-1(b)=a iff f(a)=b</code>
== Equivalence Relations ==
The following definitions refer to some <code>a, b, c ∈ S</code> for some arbitrary set S.
Also recall that, fore each paring (a, b), we can denote that they're related with <code>a R b</code>.
* '''Reflexive Relation''' - Defined as <code>a = a</code>.
** Effectively, what this means is that every element is has a relation/paring to itself.
** Ex: For <code>a, b, c ∈ S</code>, we must have some <code>(a, a), (b, b), and (c, c)</code> to be reflexive.
** Ex: The statements "is married to" or "is a coworker of".
* '''Symmetric Relation''' - If <code>a = b</code>, then <code>b = a</code>.
** Ex: For <code>a, b, c ∈ S</code>, if we have have some <code>(a, b)</code>, then we must also have <code>(b, a)</code> to be symmetric.
** Ex: The numbers 3 and 8 when applied to a modulus of 5.
* '''Transitive Relation''' - If <code>a = b</code> and <code>b = c</code>, then <code>a = c</code>.
** Ex: For <code>a, b, c ∈ S</code>, if we have some <code>(a, b) and (b, c)</code>, then we must also have <code>(a, c)</code> 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.

Revision as of 17:30, 10 September 2019

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.