Sets, Groups, Rings and Algebras

Note: Definitions build on previous definitions

Contents

  • Set
  • Group
  • Ring
  • Field
  • Ideal
  • Principal Ideal
  • Galois Field
  • Lattice
  • Algebra
  • Mapping
  • Other links
  • Set

      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
    

    Group

      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
    

    Ring

      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
    

    Field

      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
    

    Ideal

      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.
     
    

    Principal 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
    

    Galois Field

     
    
      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
    

    Lattice

      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.
    

    Algebra

    
    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
    
    

    Mapping

      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.
    
    

    Other links

    Go to Top

    Last updated 1/7/99