Homework 6, Due Tuesday, October 31.
Prove the following set argument, by constructing a logical
argument related to these set properties (for instance
PS(x) may be the proposition (x is an element of set S).
For this problem "subseteq" includes the case where the two sets are
the same.

x is not an element of S
P subseteq S
x is an element of R
R subseteq (P union Q)
-------------------
x is an element of Q

Given two arbitrary sets A,B, prove that (A intersection B) union
(A intersection B-complement) equals A.  You may *not* use a venn
diagram.  You may define characteristic functions for A,B so that A =
{x | PA(x}), and B = {x | PB(x)}.

Let S be the set of ordered pairs of integers, defined recursively by
the rule:

(0,0) is in S
if (a,b) is in S, then (a+2,b+3) is in S and (a+3,b+2) are in S.

a) list 5 different elements of S
b) use some form of induction to prove that forall (a,b) in S, 5 | a + b.
    (you may induct on the number of times the recursive rule was applied to 
     produce the pair (a,b)).

One special kind of function is called a characteristic function.
A characteristic function f: U --> {T, F}, is a function that takes,
as input, an element from U and returns true or false.  One can define
A, a subset of the set U, as the set of all elements x of U such that
f(a) = T.

Prove or disprove the following:
(a) For every possible subset of U, the characteristic function
    defining that set is ONTO.

(b) If the set U has more than two elements, then no subset can have
    a characteristic function which is one-to-one.