December 10, 2017 17:57:44
Math
Go directly to jail. Do not pass Go, do not collect $200.
 .:  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

Hypotheses

Hypotheses and theorems related to functions.

Sibling topics:

Contents:

Hypothesis: Domain/codomain cardinality given a bijective function [tags: cardinality]
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 [tags: surjective injective bijective]
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 [tags: bijective surjective injective]
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.
  1. Assume by way of contradiction that `A=O/` but `f!=O/`. Then by the definition of a function, there is an element `(u,v) in A xx B`, but because `A=O/`, this cannot be the case. Therefore, if `A=O/`, then `B=O/`.
  2. Assume by way of contradiction that `A=O/` but `Im(f)!=O/`. Then, there exists an element `v` in the image set. By the definition of image set, there exists an element `u in A` such that `f(u)=v`. But since `A=O/`, that cannot be the case. Therefore, if `A=O/`, then `Im(f)=O/`.
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 [tags: injective]
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 [tags: surjective]
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 [tags: bijective]
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`.
Copyright 2003-2016 Adam Milazzo. Verbatim copying and redistribution of this entire page are permitted without royalty in any medium provided this notice is preserved.