**Next message:**Peter_Constable@sil.org: "Re: bijective (was re: An Absurdly Brief Introduction to Unicode (was"**Previous message:**Rick McGowan: "Re: Klingon silliness"**Maybe in reply to:**Peter_Constable@sil.org: "Re: bijective (was re: An Absurdly Brief Introduction to Unicode (was"**Next in thread:**Peter_Constable@sil.org: "Re: bijective (was re: An Absurdly Brief Introduction to Unicode (was"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]**Mail actions:**[ respond to this message ] [ mail a new topic ]

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>

**Next message:**Peter_Constable@sil.org: "Re: bijective (was re: An Absurdly Brief Introduction to Unicode (was"**Previous message:**Rick McGowan: "Re: Klingon silliness"**Maybe in reply to:**Peter_Constable@sil.org: "Re: bijective (was re: An Absurdly Brief Introduction to Unicode (was"**Next in thread:**Peter_Constable@sil.org: "Re: bijective (was re: An Absurdly Brief Introduction to Unicode (was"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]**Mail actions:**[ respond to this message ] [ mail a new topic ]

*
This archive was generated by hypermail 2.1.2
: Tue Jul 10 2001 - 17:21:19 EDT
*