1.(10) Find functions f : R → R and g : R → R such that f ◦ g has the rule
f ◦ g(x) = ⌊x2 + 7⌋.
2.(10) Define A = Z+ × Z+. Let R be a relation on A such that (a,b)R(c,d) if
a + d = b + c, for all (a, b), (c, d) ∈ A.
(a) Is R reflexive? (b) Is R symmetric?
(c) Is R antisymmetric? (d) Is R transitive?
3.(10) Determine the truth value of ∃x∀y(x ≤ y2) if the domain for x and y is
(a) positive real numbers (b) integers
(c) nonzero real numbers
4.(15) Let A, B, and C be sets. Prove or disprove that
(a) IfA∪C=B∪C,thenA=B
(b) IfA∪C=B∪CandB∩C=A∩C,thenA=B
(c) If(A−C)∪(C−A)=(B−C)∪(C−B),thenA=B
5.(10) How many strings of all the first seven letters of the alphabet (A,B,C,D,E,F,G)
are there that contain no repeated letters and begin or end with a vowel (A or E)?
6.(10) Suppose that S is the set of finite subsets of positive integers. Define f : Z+ → S such that f(n) = the set of all the positive divisors of n. For example, f (10) = {1, 2, 5, 10}. Prove or disprove
• f is one-to-one • f is onto
7.(10) How many pairs of integers (a,b) must be chosen to guarantee that there are two pairs (a1,b1) and (a2,b2) such that
a1 mod7=a2 mod7 and b1 mod7=b2 mod7? Justify your solution.
8.(10) Let a, b be real with a > b > 0. Use mathematical induction to show that for integer m ≥ 1
am − bm ≤ mam−1(a − b).
9.(10) Let a,b,c,d, and m be integers with m ≥ 2. Suppose that a ≡ b (mod m)
and c≡d (mod m). Prove or disprove a−c≡b−d (mod m). 1
11. (15) Prove that for any real number x, ⌊3x⌋=⌊x⌋+⌊x+1/3 ⌋+⌊x+2/3⌋
10. (10) A partition P1 is said to be a refinement of the partition P2 if every set in P1 is a subset of some set in P2. Let R1 and R2 be equivalence relations on a set A. Also let P1 and P2 be the partitions induced by R1 and R2, respectively. Prove that R1 ⊆R2 if and only if P1 is a refinement of P2.
12. (10) Let f be a function from the set A to the set B. Define the function Sf from
2A to 2B by
Sf(X) = f(X)
for each subset X of A. Prove or disprove the following
• If f is one-to-one, then Sf is one-to-one from 2A to 2B.
•If f is onto,then Sf is onto from 2A to 2B.
13.(10) Suppose that R1 and R2 are equivalence relations on a set A. Prove that the
relation R1 ∩ R2 is also an equivalence relation on A.
14.(10) Use Mathematical Induction to prove that 2n + 3 ≤ 2n for all n ≥ 4.
0 comments