A set is a collection of unique elements.
The definition of a specific set determines which elements
are members of the set.
Elements not specifically defined as members of a set are not
in the set.
The cardinality of a set is the count of the number of elements
in a set based on the sets definition. The cardinality may be
finite or infinite.
Cardinality example: The cardinality of the set of dwarfs in
the Snow White story is 7.
The cardinality of the set of integers is NOT the same as the
cardinality of the set of real numbers. Both are infinite.
A common way to define a set with property, p, is
S = { x | x has p } which reads
S is a set with all elements x such that x has the property p.
The set with no elements is denoted by the Greek letter Phi and
has a cardinality of zero.
Operations on sets:
Membership test:
is x an element of S
Cardinality:
|S| is the notation for the cardinality of the set S
Set union:
Let A and B be sets,
A union B = { x | x in A or x in B }
The union is all the elements of both A and B but no duplicates.
Set intersection:
A intersect B = { x | x in A and x in B }
The intersection is all elements that are in both sets.
Set complement:
The complement of set A = { x | x not in A }
The complement may be written as the set name with a bar over it.
The complement may be written as the set name with a superscript c.
The complement may be written as the set name preceded by - or ~.
A union -A = U the universal set.
A intersect -A = Phi the empty set.
Set difference:
A - B = { x | x in A and x not in B }
The set of elements that are in A but not in B.
Cartesian product or cross product:
Given sets A and B, A x B is the set of all possible
ordered pairs (x,y) such that x is in A and y is in B.
Subsets:
A is a subset of B if all elements in A are in B.
A = B means A is a subset of B and B is a subset of A.
A is a proper subset of B means A is not equal to B and
A is a subset of B.
Set of all subsets of a set:
The cardinality of the set of all subsets of A is 2**|A|.
The subsets include the empty set Phi,
the sets with exactly one element of A,
the sets with exactly two elements of A,
..
the sets with all except one element of A and
the set A.
Example: Given the set A = {a, b, c} the set of all subsets =
{ Phi,
{a}, {b}, {c},
{a, b}, {a, c}, {b, c},
{a, b, c}
}
which has cardinality 8 = 2**3
Laws that hold for sets where A, B and C are sets:
Idempotent:
A intersect A = A
A union A = A
Commutative:
A intersect B = B intersect A
A union B = B union A
Associative:
A intersect (B intersect C) = (A intersect B) intersect C
A union (B union C) = (A union B) union C
Absorption:
A intersect (A union B) = A union (A intersect B)
Identity:
A intersect Phi = Phi intersect A = Phi
A union Phi = Phi union A = A
A group is an algebraic system consisting of a set, an identity element,
one operation and its inverse operation.
A example group, G = ( S, O, I )
S is set of integers
O is the operation of addition, the inverse operation is subtraction
I is the identity element zero (0)
Another example group, G = ( S, O, I )
S is set of real numbers excluding zero
O is the operation of multiplication, the inverse operation is division
I is the identity element one (1)
The operation does not have to be addition or multiplication.
The set does not have to be numeric.
Group Axioms:
let a, b and c be elements of a group
G1: Closure.
The operation can be applied to any two elements of the group
and the result is an element of the group.
For all a, b and c O(a,b)=c
G2: Associative.
For all a, b and c (a+b)+c = a+(b+c) if operation is addition
(ab)c = a(bc) if operation is multiplication
G3: Identity element.
The identity element must be a member of the group and is
its own inverse. The identity element is provably unique,
there is exactly one identity element.
0+a=a+0=a if operation is addition
1a=a1=a if operation is multiplication
G4: Inverse.
Every element of the group has an inverse element in the group.
a+(-a) = (-a)+a = 0 if operation is addition
-1 -1
aa = a a = 1 if operation is multiplication
An Abelian Group or commutative group has an additional axiom
a+b = b+a if the operation is addition
ab = ba if the operation is multiplication
A Lie Group is a topological group with only countably many connected
components and an identity element that is open.
A theorem for a group with a multiplicative operator is:
The inverse of a product is the product of the inverses in reverse order.
-1 -1 -1 -1 -1 -1
(ab)(b a ) = a(bb )a = a1a = aa = 1
A Cyclic Group is a group that has elements that are all powers of one
of its elements.
link to more
A ring is an algebraic system consisting of a set, an identity element,
two operations and the inverse operation of the first operation.
A example ring, R = ( S, O1, O2, I )
S is set of real numbers
O1 is the operation of addition, the inverse operation is subtraction
O2 is the operation of multiplication
I is the identity element zero (0)
link to more
A field is an algebraic system consisting of a set, an identity
element for each operation, two operations and their respective inverse
operations.
A example field, F = ( S, O1, O2, I1, I2 )
S is set of
O1 is the operation of addition, the inverse operation is subtraction
O2 is the operation of multiplication
I1 is the identity element zero (0)
I2 is the identity element one (1)
link to more
An Ideal, I, is a subset of a Ring, R, with the properties: 1) I is a subgroup of the additive group of R and 2) for every i in I and every r in R, ir and ri are in I. Example: The set of all multiples of any integer is an Ideal.
A Principal Ideal is an Ideal that contains all multiples of one Ring element. A Principal Ideal Ring is a Ring in which every Ideal is a principal ideal. Example: The set of Integers is a Principal Ideal ring. link to more
GF(p) for any prime, p, this Galois Field has p elements which are the
residue classes of integers modulo p.
m
GF(p ) for any prime, p, and m greater than zero, this Galois Field
m
has p elements which is a Field of polynomials over GF(p) modulo
an irreducible polynomial of degree m.
m
GF(q) for q = p for nay prime, p, and m greater than zero,
this Galois Field has q elements of the vector space of dimension m
over GF(p).
Theorems:
Every finite field is isomorphic to some Galois Field.
link to more
A lattice is a partially ordered set where any two elements a and b have a least upper bound, LUB, a union b, or have a greatest lower bound, GLB, a intersect b. A partial ordering means some pairs elements of the set can not be compared.
An algebra is a set of elements and a set of laws that apply to the elements.
One way to define various types of algebras such as rings, fields, Galois
Fields and the like, is to list the possible laws (axioms, postulates, rules)
that might apply, then define each algebra in terms of which laws apply.
Note: The particular symbols and the particular operations are not important.
Addition and multiplication are commonly used for convenience, yet the
logical operations "and" and "or could be used, the set operations
union and intersection could be used, as well as many other pairs of
operations.
Closure Laws: A0. Addition is well defined, for every ordered pair
a, b in S, c = a+b implies c is a unique element in S.
M0. Multiplication is well defined, for every ordered pair
a, b in S, c = a*b implies c is a unique element in S.
Associative Laws: A1. (a+b)+c = a+(b+c) {we do not repeat the obvious
for all a, b, c in S, after this}
M1. (a*b)+c = a*(b*c)
Commutative Laws: A2. a+b = b+a
M2. a*b = b*a
Identity Laws: A3. 0 is in S and 0+a = a+0 = a
M3. 1 is in S and 1*a = a*1 = a
Inverse Laws: A4. for every a in S, -a is a unique element in S and
(-a)+a = a+(-a) = 0
M4. for every a in S except 0, a**-1 is a unique element in S
and (a**-1)*a = a*(a**-1) = 1
Distributive Laws: D1. a(b+c) = ab + ac
D2. (b+c)a = ba + ca
A mapping or function, f:A -> B is a mapping from the domain set A to
the range set B such that y = f(x), x in A and y in B.
A total function or mapping has some y for every x. The y's may not
be unique.
A partial function or mapping has some x for which there is no y.
A map or function is called injective if f(x) = f(y) implies x = y
also known as a 1 to 1 mapping.
A map or function is called surjective if for every y in B there
exists an x in A such that f(x) = y
also known as an onto mapping.
A map or function is bijective if it is injective and surjective
also know as 1 to 1 onto mapping.
-1
An inverse mapping f (y) = x may or may not exists for a function f.
Last updated 1/7/99