Section 4.4 Definitions:
Let S and T be sets. page 291
A function (mapping)
from S to T, f: S → T, is a subset of S X T where each
member of S appears exactly once as the first component of an ordered
pair.
S is the domain and
T
the codomain of the function.
If the
ordered pair (s,t) belongs to the function, then
t is denoted by f(s);
t is the image of s under f,
s is a preimage of t under f, and
f is said to map s to t.
For A Í S, f(A) denotes {f(a) | a Î A}.
The floor function x associates with each real number x, the
greatest integer less than or equal to x.
page
293
The ceiling function x
associates with each real number x, the smallest integer greater than or equal
to x. page 293
Two functions are equal if they have the same domain, the same codomain, and the same association of values of the codomain with values of the domain. page 295
A function
f: S → T is an onto, or surjective, function if the range of f equals the codomain of
f. page 296
A function
f: S → T is one-to-one, or injective, if
no member of T is the image under f of two distinct elements of S. page 296
A function
f: S → T is bijective (a bijection)
if it is both one-to-one and onto. page 297
Let f: S
→ T
and g: T
The
composition of two bijections is a bijection.
page
299
The
function that maps each element of a set S to itslef, that is, that leaves each
element of S unchanged is called the identity
function on S and denoted by iS. page 299
Let f be a
function, f: S → T.
If there
exists a function g: T → S, such that g ° f = iS and f ° g = iT , then g is
called the inverse function of f, denoted by f-1 page 300
Let f: S → T.
Then f is a bijection if and only if f-1 exists. page 300
_____________________________________________________________________________
For a
given set A, SA = { f | f: A → A and f is a
bijection}. SA is thus the
set of all bijections of a set A into (and therefore onto) itself; such functions
are called permutations of A. page 301
The permutation that maps each element of A to
itself is the identity function on A, iA, also called the identity permutation. page 302
A
permutation on a set that maps no element to itself is called a derangement. page 302
If |S| = m and |T| = n, then
1.
The
number of functions f : S →
T = nm
2. The number of one-to-one
functions f : S →
T, assuming m <= n is
n!
(n-m)!
3. The number of onto functions f :
S →
T, assuming m >= n is
nm
– C(n,1)(n-1)m + C(n,2)(n-2)m – C(n,3)(n-3)m+ ...
+ (-1)n-1C(n,n-1)(1)m page 304
A set S is
equivalent to a set T if there exists a bijection f : S →T. Two sets that are equivalent have the same cardinality. page 306
Cantor’s
Theorem For any set S, S and ρ (S) are not equivalent.
to do yet: Order of Magnitude...