A brief intro to some algebra terminology (I'm drafting these from memory,
but I don't think there are any oversights as in one of my earlier posts):
I will assume the definition of "set" is understood. Examples will assume
the sets K = { 1, 2, 3 }, L = { a, b}, M = { a, b, c, d }, N = { a, b, c }
Given a pair of sets A and B:
The product A x B is the set { (x, y) | x belongs to A, y belongs to B }.
- e.g. K x N = { (1, a), (1, b), (1, c), (2, a), (2, b), (2, c), (3, a),
(3, b), (3, c) } (let's call this P in subsequent examples)
- e.g. K x M = { (1, a), (1, b), (1, c), (1, d), (2, a), (2, b), (2, c),
(2, d), (3, a), (3, b), (3, c), (3, d) }
- e.g. K x L = { (1, a), (1, b), (2, a), (2, b), (3, a), (3, b) }
A relation between A and B is a subset of the product A x B
- e.g. a relation between K and N would be some subset of P, such as one of
the following:
Q = { (1, b), (3, a) }
R = { (1, a), (3, b), (1, b), (2, c) }
S = { (3, c), (1, c), (2, b) }
T = { (2, a), (1, c), (3, b) }
- e.g. the following are relations between K and L:
U = { (1, b), (2, a), (3, a) }
- e.g. the following is a relation between K and M:
V = { (1, a), (2, c), (3, d) }
A function f: A -> B is a relation between A (the "domain") and B (the
"range" or "codomain") that satisfies two properties:
1. for every x in A, there is some y in B such that (x, y) is in f (every
element of the domain maps to something)
2. if (x, y) is in f, and (x, z) is in f, then y = z (every element of the
domain maps to a single element of the range)
- e.g. from the previous examples, S and T are functions from K to N; U is
a function from K to L. V is a function from K to M. Q is not a function
because it does not satisfy criterion 1; R is not a function because it
does not satisfy criterion 2.
A function f: A -> B is injective if the following is true: if the function
contains (w, y) and (x, y), then w = x (no distinct elements in the domain
map to the same element in the range).
- e.g. T and V are injective; S is not since 1 and 3 both map to c; U is
not since both 2 and 3 map to a.
A function f: A -> B is surjective if for every y in B there is some x in A
such that (x, y) is in f (every element in the range is mapped into by some
element in the domain).
- e.g. T and U are surjective; S is not since nothing in K maps to a; V is
not since nothing in K maps to b.
A function f: A -> B is bijective if it is both injective and surjective.
(This means that there is a 1:1 mapping.)
- e.g. T is bijective
Note that for a bijective function, both A and B have to have the same
cardinality (the same number of elements).
The definition of set products can be extended for n-tuples (e.g. Z x N x Z
x Q), and this can be used in extending the other definitions to allow for
functions and relations with multiple arguments (e.g. f: A x B -> C), or
that map onto complex ranges (e.g. f: A -> B x C). (It's easy to see how
this can be if either set A or set B in the initial definition were a set
of pairs, such as the example set P.)
- Peter
---------------------------------------------------------------------------
Peter Constable
Non-Roman Script Initiative, SIL International
7500 W. Camp Wisdom Rd., Dallas, TX 75236, USA
Tel: +1 972 708 7485
E-mail: <peter_constable@sil.org>
This archive was generated by hypermail 2.1.2 : Tue Jul 10 2001 - 17:21:19 EDT