Mathematical Prerequisites: Answers
    1. True
    2. False
    3. True
    4. True
    5. True
    6. True
    7. False
    8. True
    9. False

    1. {1,3,5,7}
    2. Æ
    3. Æ
    4. {{8},{7,8}.{8,9},{7,8,9}}
    5. {Æ}
    6. {<1,1,1>,<1,1,2>,<1,1,3>,<1,2,1>,<1,2,2>,<1,2,3>}
    7. Æ
    8. {<Æ,1>,<Æ,2>,<{1},1>,<{1},2>,<{2},1>,<{2},2>,<{1,2},1>,<{1,2},2>}

    1. This will be the case if g(f(A)) = C
    2. This will be the case if a ¹ b implies g(f(a)) ¹ g(f(b))
    3. This will be the case if both of the above conditions are satisfied.

    Note: It is possible for h to be surjective without f being surjective, and it is also possible for h to be injective without g being injective.

    For example: let A={a}, B={b,b'}, C={c} and f(a) = b, g(b) = c, g(b') = c
     

    1. Because the three sets are countable, we can list their elements:


      2. First set: a00 a01 a02...
      Second set: a10 a11 a12...
      Third set: a20 a21 a22...

      We can list all the elements of the union of these three sets (with possible repetitions) as follows:

      a00 a10 a20 a01 a11 a21 a02 a12 a22 ...

      Therefore, this set is countable. Since the union of the three sets is a subset of this, it must also be countable.
       

    2. The finite subsets of N may be arranged as follows:


      3. First row: all the singleton subsets of N, i.e., {1}, {2}, {3}, ...,
      Second row: all 2-element subsets of N, i.e., {1,2} , {1,3}, {2,3}, {1,4}, {2,4}, {3,4}, {1,5}, ...,
      Third row: all 3-element subsets of N, i.e., {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}, {1,2,5}, {1,3,5}, {1,4,5}, {2,3,5}, {2,4,5}, {3,4,5}, etc.
      and so on, enumerating all subsets of N by set size.

      We may then enumerate the complete set using a dovetailing approach by visiting the sets in the corresponding array of sets in a diagonal fashion.


    1. f(n) = 2n+1
    2. f(n) = (n+1)/2, if n is odd
     = -n/2,    if n is even
    3. We define an ordering on triples as follows:


      4. 1,y1,z1> < 2,y2,z2>, if x1 + y1 + z1 < x2 + y2 + z2
      1,y1,z1> < 2,y2,z2>, if x1 + y1 + z1 = x2 + y2 + z2 and x1 < x2
      1,y1,z1> < 2,y2,z2>, if x1 + y1 + z1 = x2 + y2 + z2 and x1 = x2 and y1 < y2

      This gives us the following ordering:

      <0,0,0> <0,0,1> <0,1,0> <1,0,0> <0,0,2> <0,1,1> <0,2,0> <1,0,1> <1,1,0> <2,0,0> ...

      We can now define a bijection f between N and this set as follows:

      f(0) = (0,0,0), f(1) = (0,0,1), f(2) = (0,1,0), f(3) = (1,0,0), ...


    1. Æ Î C (by 1)

      2. Therefore {Æ,Æ} = {Æ} Î C (by 2)
      Therefore {Æ,{Æ}} Î C (by 2)
       
    2. C does not contain any infinite sets because all its elements must be constructed by a finite number of applications of rules 1, 2 and 3. However, C does contain an infinite number of sets.

      3.  
    3. C is countable. We can list the elements of C as follows:


      4. Apply rule 1, and then repeatedly apply rules 2 and 3 for all pairs of elements already listed.

  7. Base Case (n=1)


    8. RHS = 1 ´ 2 ´ 3 ´ 4/4
    = 1 ´ 2 ´ 3
    = LHS

    Inductive Hypothesis: Assume true for n:

    1 ´ 2 ´ 3 + 2 ´ 3 ´ 4 + ... + n(n+1)(n+2) = n(n+1)(n+2)(n+3)/4

    Inductive Case: Show that it is true for n+1:

    LHS = 1 ´ 2 ´ 3 + 2 ´ 3 ´ 4 + ... + n(n+1)(n+2) + (n+1)(n+2)(n+3)
    = n(n+1)(n+2)(n+3)/4 + (n+1)(n+2)(n+3) (by inductive hypothesis)
    = n(n+1)(n+2)(n+3)/4 + 4(n+1)(n+2)(n+3)/4
    = (n+1)(n+2)(n+3)(n+4)/4
    = RHS
     

  8. Base Case (n=0)


    9. n3+2n = 0 (which is divisible by 3)

    Inductive Hypothesis: Assume true for n:

    n3+2n is divisible by 3

    Inductive Case: Show that it is true for n+1:

    (n+1)3+2(n+1)
    = n3 +3n2 + 3n + 1 + 2n + 2
    = (n3+2n) + 3n2 + 3n + 3
    = (n3+2n) + 3(n2 + n + 1)
    Each of these terms is obviously divisible by 3 (the first by the inductive hypothesis)
    Therefore the predicate is true for all n
     

  9. The sets {...,-3,-2,-1,0} and {0,1,2,3,...} are both countably infinite. Their intersection {0} is finite.


    10. The sets Z (integers) and Z+ (positive integers) are both countably infinite. Their intersection (Z+) is countably infinite.

    The sets of real numbers in the intervals [-1,0] and [0,1] are both uncountable. Their intersection {0} is finite.

    The sets R+ È N (positive reals and naturals), and R- È N (negative reals and naturals) are both uncountable. Their intersection (N) is countably infinite.

    The sets R (reals) and R+ (positive reals) are both uncountable. Their intersection (R+) is uncountable.
     

  10. Assume we have an uncountable set S and a countable set T.


    11. S Ç T is countable, since it is a subset of T.

    If S-T were countable, then (S-T) È (S Ç T) = S would be also.