Homework 6, Due Tuesday, November 1.

Prove the following, constructing a logical argument by defining
propositions related to these set properties (for instance S(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.

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


Let S(x) be: "x is an element of S", and the same for P,Q,R

Then we can translate the above into:

1. ~S(x)
2.  forall y, P(y) --> (S(y))
3.  R(x)
4.  forall y, R(y) --> (P(y) v Q(y))
-------------------------
 Q(x)

Proof:

5. P(x) --> S(x),       4 univ. instantiation
6. ~P(x)                1,5, modus tollens
7. R(x) --> P(x) v Q(x) 4, univ. instantiation
8. P(x) v Q(x)          3,7, modus ponens
9. Q(x)                 6,8 disjuntive syllogism



Given two arbitrary sets A,B, prove that 
(A intersection B) union (A intersection B-complement) equals A.

Let A(x) be x is an element of A, and B(x) be x is an element of B.

Our expression on sets can then be written in logical terms:
(A(x) ^ B(x)) v (A(x) ^ ~B(x)) <--> A(x)
To prove this equivalence, we start with the left side, and derive the right side:

(A(x) ^ B(x)) v (A(x) ^ ~B(x)) <-->
A(x) ^ (B(x) v ~B(x)) <-->
A(x) ^ T <-->
A(x).

q.e.d.


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

(0,0), (2,3), (3,2), (4,6), (6,4), (7,8)


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)).

Base case: 0 applications of the inductive rule: so the number is (a,b).
           a+b = 0, so 5 | a + b.

Inductive step: Assume that for any pair (a,b) formed with n
           applications of the inductive rule, that 5 | a+b.

Prove that for a pair (a,b) formed with n+1 applications of the
           inductive rule, 5|a+b...
	   
	   Let (a,b) be a pair formed with n+1 applications of the
	   inductive rule.  Then, there must exist an a', b' formed
	   with n applications of the rule such that:
	   
	   a = a' + 3, and b = b' + 2,   
                      or
	   a = a' + 2, and b = b' + 3.
	
	We try these cases seperately:
	Case 1: a = a' + 3, b = b' + 2.
	        then a + b = a' + b' + 5
                           = ( 5k )  + 5         (by inductive hypothesis)
			   = 5 (k + 1) 
                   so 5 | a+b

        Case 2: a = a' + 2, b = b' + 3 (you could say, "this case is
                                        symmetric and be done, because every
					remaining line of the proof is the same!)
	        then a + b = a' + b' + 5
                           = ( 5k )  + 5         (by inductive hypothesis)
			   = 5 (k + 1) 
                   so 5 | 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.

This is false.  The empty set is a subset of any sets (so, whatever U
is, it must have the subset as the empty set...) and the empty set has
a characteristic function that is always false.  This function is not
onto for the co-domain {True, False}, because nothing is mapped to
false.

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

A one to one function must have a co-domain that is larger than or
equal to the domain.  If U has more than two elements, then the co-domain
is smaller, so no one to one function exists.