Mathematics/Discrete Math/Relations and Functions: Difference between revisions
< Mathematics | Discrete Math
Jump to navigation
Jump to search
Brodriguez (talk | contribs) (Create page) |
Brodriguez (talk | contribs) (Add function properties) |
||
| Line 1: | Line 1: | ||
Recall from [[Discrete Math - Sets]] (basic set operations) that a '''Cartesian Product''' is a mapping of ordered pairs from sets A={a1, a2, ...} and B={b1, b2, ...} such that | 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 | ||
<code>A x B={(a1, b1), (a1, b2), ..., (a2, b1), (a2, b2), ...}</code>. | <code>A x B={(a1, b1), (a1, b2), ..., (a2, b1), (a2, b2), ...}</code>. | ||
Using this fact, we can define some terms: | Using this fact, we can define some terms: | ||
== Function Definitions == | |||
* '''Binary Relation''' - A subset of the cartesian product <code>A x B</code> for some arbitrary, non-zero sets ''A'' and ''B''. | * '''Binary Relation''' - A subset of the cartesian product <code>A x B</code> 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 <code>a R b</code>. | ** When an element ''a ∈ A'' is paired with an element ''b ∈ B'' through a binary relation, we can denote that they're related with <code>a R b</code>. | ||
* '''Function''' - A binary relation such that every element in ''A'' corresponds to, at most, one element in ''B''. | * '''Function''' - A binary relation such that every element in ''A'' corresponds to, at most, one element in ''B''. | ||
* '''Domain''' - Given all <code>{(a, b) ∈ f | a ∈ A, b ∈ B}</code>, the "domain" is the full set ''A''. | * '''Domain''' - Given all possible <code>{(a, b) ∈ f | a ∈ A, b ∈ B}</code>, the "domain" is the full set ''A''. | ||
* '''Codomain''' - Given all <code>{(a, b) ∈ f | a ∈ A, b ∈ B}</code>, the "codomain" is the full set ''B''. | * '''Codomain''' - Given all possible <code>{(a, b) ∈ f | a ∈ A, b ∈ B}</code>, the "codomain" is the full set ''B''. | ||
* '''Argument''' - Given all <code>{(a, b) ∈ f | a ∈ A, b ∈ B}</code>, each ''a'' can be considered an "argument". | * '''Argument''' - Given all possible <code>{(a, b) ∈ f | a ∈ A, b ∈ B}</code>, each ''a'' can be considered an "argument". | ||
* '''Value''' - Given all <code>{(a, b) ∈ f | a ∈ A, b ∈ B}</code>, each ''b'' can be considered a "value". | * '''Value''' - Given all possible <code>{(a, b) ∈ f | a ∈ A, b ∈ B}</code>, each ''b'' can be considered a "value". | ||
* '''Finite Sequence''' - A function that has at most ''n'' domain → codomain pairings. | * '''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. | ** In simpler terms, a function that has a limited/set number of a → b mappings. | ||
| Line 15: | Line 17: | ||
Note that two functions are considered equivalent if they have the same domain and codomain. | 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 <code>f^-1(b)=a iff f(a)=b</code> | |||
Revision as of 16: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 Bfor 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.
- When an element a ∈ A is paired with an element b ∈ B through a binary relation, we can denote that they're related with
- 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