|
.: Math Note: If you cannot view some of the math on this page, you may need to add MathML support to your browser. If you have Mozilla/Firefox, go here and install the fonts. If you have Internet Explorer, go here and install the MathPlayer plugin. Math
> Functions
> Hypotheses
HypothesesHypotheses and theorems related to functions.Sibling topics:Contents:
Hypothesis: Domain/codomain cardinality given a bijective function
If there exists a bijective function from `A` to `B`, then `|A|=|B|`.
Hypothesis: Surjectivity implies injectivity and vice versa for finite, equal domains and codomains
Given `f:A->B` where `A=B` and `A` and `B` are finite, any surjective or
injective function must be bijective.
Corollary (of
Bijectivity in finite, equal domains/codomains):
Surjectivity does not imply injectivity and vice versa in infinite, equal domains and codomains
Given `f:A->A` where `A` is infinite, there exist functions that are injective but not
surjective and vice versa.
Theorem: Empty codomain implies empty domain Given `f:A->B`, if `B=O/`, then `A=O/`. Proof: Assume by way of contradiction that `B=O/` but `A!=O/`. Then there is an element `u in A`. By the
the definition of
a function, there exists an element `v in B` such that
`(u,v) in A xx B`. But `B=O/` so there can be no such element. Therefore, if `B=O/`, then `A=O/`.Theorem: Empty domain implies empty function and image set Given `f:A->B`, if `A=O/`, then `f=O/ and Im(f)=O/`. Proof: This theorem is really two theorems in one, so we'll address each separately.
Hypothesis: Number of distinct functions for a finite domain and codomain
The number of distinct functions from a finite domain `A` to a finite codomain `B` is given by
`|B|^|A|`. This is the number of distinct lists of length `|A|` that can formed using elements
from `B`.
Hypothesis: Number of distinct injective functions for a finite domain and codomain
The number of distinct injective functions from a finite domain `A` to a finite domain `B` is
given by `{(0,if |A|>|B|),((|B|!)/((|B|-|A|)!),otherwise):}}`. This is equal to the number of
permutations of `B` containing `|A|` elements.
Hypothesis: Number of distinct surjective functions for a finite domain and codomain
The number of distinct surjective functions from a finite domain `A` to a finite domain `B`
is given by `{(0,if |A|<|B|),(|B|^(|A|-|B|)xx|B|!,otherwise):}}`. This is equal to the number of
permutations of `B` times the number of unique lists of length `|A|-|B|`
that can be formed using elements from `B`.
Hypothesis: Number of distinct bijective functions for a finite domain and codomain
The number of distinct injective functions from a finite domain `A` to a finite domain `B` is
given by `{(0,if |A|!=|B|),(|B|!,otherwise):}}`. This is equal to the number of permutations of `B`.
|