August 25

* Syllabus
* Topics in this course
  Basic theory needed for other CS courses
     sets, functions, relations
     predicate logic
     What is a computer?
     What functions can certain types of computers compute?
     What algorithms can certain types of computers perform?
     What algorithms can certain types of computers NOT perform?
     How quickly can computers compute certain functions?

* Next few classes - cover (review, for some) the fundamentals

* Sets

  A "set" is a collection of objects    +-------+
                                        |  b 1  |
                               L =  +---+       |
	 			    | a  3  c   |
	 			    +-----------+

  The objects in the set are the set "elements" or "members".
  We can list the elements of a set by
     1) listing all of the elements
	L = {b, 1, a, 3, c}

	We do not distinguish repetitions of the elements
	   {b, 3, a, b} = {b, 3, a}
	and order does not matter
	   = {a, b, 3}

     2) using dots to represent "rest" of elements in a set of infinite size
        N = {0, 1, 2, ...}

     3) writing a rule to describe all the elements of the set

	A = {x: x is either a, b, c, 1, or 3}
	W = {x: x is odd} which means W = {1, 3, 5, 7, ...}


* Special sets

   - empty set, {}, phi
     Sets with 1 or more elements are "nonempty"

   - singleton (set with one element)

   - Sets with an infinite number of elements are "infinite" sets
	  "" ""   finite    "" ""                 "finite" sets

   - natural numbers, "N", "Z"
     N = Z = {0, 1, 2, ...}
     N+ = Z+ = {1, 2, 3, ...}

   - rational numbers, "Q"
     Defined as integer
		-------
		integer

   - reals, "R"

   - complex numbers, "C"


* Set operations

   - e, "element of", "in"
     1 e N, a e {1, 2, a, b}
     1 is in N, N "contains" 1
   
   - U, v, "union" 
     A U B = set made up of all elements in A and all elements in B
     (no duplicates)
     If A = {1,2,3}, B = {1,3,5}, A U B = {1,2,3,5}
     Can find union of more than two sets
     vS, S is a collection of sets
     S = {{a,b}, {b,c}, {b,3}}
     vS = {a,b,c,3}

   - ^, "intersection"
     A ^ B = set made up of all elements in both A and B (no duplicates)
     A ^ B = {x: x in A and x in B}
     A ^ B = {1,3}
     Can find intersection of more than two sets
     ^S, S is a collection of sets
     S = {{a,b}, {b,c}, {b,3}}
     ^S = {b}
    
   - "-", "subtraction"
     A - B = set made up of all elements in A that are not in B
     A - B = {2}

   - "subset or equal"
     A <= B = set made up of some (or all) elements of B
     A "is included in" B
     {1,2} <= {1,2,3}
     {1,2,3} <= {1,2,3}

   - "proper subset"
     A <= B but NOT A = B

   - "=", "equal"
     A = B if A<=B and B<=A

   - "disjoint"
     A and B are disjoint if they have no elements in common
     A and B are disjoint if A^B is an empty set

*  Relations

   In sets, the order of elements does not matter
   Introduce a special notation in which order does matter
   An order pair is a group of two elements in which order matters
   (a, b) is an ordered pair, not equal to (b, a)

   Useful in expressing "relationships" between two elements

   "Earlier in alphabet" applies to (a, b), (c, z)

   - "x", "Cartesian Product"
     AxB = set of ordered pairs (each element of A paired in turn
	with each element of B)
     if A = {a,b}, B = {x,y}, then
     AxB = {(a,x),(a,y),(b,x),(b,y)}
     AxB not equal to BxA, because order matters inside ordered pairs

   - |A|, "cardinality"
     Size, or number of elements, in a set
     A = {a,b,c,1,3}, |A| = 5
     B = {x,y,z}      |B| = 3
     |AvB| = ?   |A^B| = ?   If |A|=m and |B|=n, then |AxB|=?

   - P(A), "power set", 2**A
      P(A) = all subsets of A
      If A = {a,2,z,Z} then
      P(A) = {{}, {a}, {2}, {z}, {Z}, {a,2}, {a,z}, {a,Z}, {2,z}, {2,Z}, {z,Z},
	      {a,2,z}, {a,2,Z}, {a,z,Z}, {2,z,Z}, {a,2,z,Z}}

      |P(A)| = ?
      The size of the power set is always twice as large as it would be for
      a set with one less element
      |P(A)| = 2*|P(B)|, where |B| = |A| - 1
      = 2 * 2 * |P(C)|, where |C| = |B| - 2
      = 2**|A|

   - "partition"
     A partition of a nonempty set A is a subset H of 2**A such that
     {} is not an element of H and each element of A is in one and only one
     set in H.
     H is a partition of A if H is a set of subsets of A such that
	1.  Each element of H is nonempty
	2.  Distinct members of H are disjoint;
	3.  vH = A

     If A = {a,b,c,1,3}, then two possible partitions are
	{{a}, {b,3}, {c,1}} and
	{{a}, {b}, {c}, {1,3}}
	   
* Binary relation
     A binary relation on two sets A and B is a subset of AxB.
     Binary signifies that this is a relation between two elements.
     The subset of AxB indicates all the pairs on which this relation holds.
     If A={a,b,c} and B={1,2,3,4}, then one binary relation could be
     {(a,1), (a, 4), (b,2)}.

     A "greater than or equal" relation on natural numbers is
     {(i,j): i,j in N and i>=j}

   We can generalize ordered pairs (ordered group of 2 elements) to
   "ordered n-tuple" (ordered group of n elements).
   If (a1, a2, ..., an) is an n-tuple, then ai is the "ith component" of
   the tuple.

   Two tuples are equal if number of elements are the same and each element
   is equal.

   Special cases:  n=3, "triple"
		   n=4, "quadruple"
		   n=5, "quintuple"
		   n=6, "sextuple"
   A "sequence" is an ordered n-tuple if n is not instantiated,
   n is the "length" of the sequence.

   An "n-ary relation" on sets A1, ..., An is a subset of A1 x ... x An
   n=1, "unary" relation
   n=2, "binary" relation
   n=3, "ternary" relation

* Set properties

  - Idempotency
    A v A = A
    A ^ A = A

  - Commutativity
    A v B = B v A
    A ^ B = B ^ A

  - Associativity
    (A v B) v C = A v (B v C)
    (A ^ B) ^ C = A ^ (B ^ C)

  - Distributivity
    A v (B ^ C) = (A v B) ^ (A v C)
    A ^ (B v C) = (A ^ B) v (A v C)

  - Absorption
    A ^ (A v B) = A
    A v (A ^ B) = A

  - DeMorgan's Laws
    A - (B v C) = (A - B) ^ (A - C)
    A - (B ^ C) = (A - B) v (A - C)

    Proof of first of DeMorgan's laws.  L = left-hand side, R = right-hand side
    Prove that L<=R and R<=L, thus L=R.

    1.  L<=R
	Let x be an element of L.  By definition of L, x is in A, but
	x is not in B AND x is not in C.  Thus x is an element of A-B AND
	x is an element of A-C, so x is an element of (A-B) ^ (A-C).
	This proves L <= R.

    2.  R<=L
	Let x be an element of R.  By definition or R, x is in both A-B and
	A-C, and is thus in A but neither in B nor in C.  Thus x in A but
	x not in BvC, so x is in L.  Thus R <= L.

    Q.E.D.