Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Each of the ten problems is worth 10 points, for a total of 100. You must justify all your answers.

1.  Consider  two  functions  i  and j  that  map  English  words  of 2  or  more  letters  to  the  set {a, b, . . . , z} by the following rule: the value of i is the first letter of the word, and the value of j is the second letter of the word.  For example, i(example) = e and j(example) = x.  Is it true that i-1 (a) \ j -1 (b) = {answer} ?

2. Let T  =  {a, b, c, d} and P  =  2T.   Consider the relation < defined on P by the following rule:  A < B if and only if A n (T \ B) C {c}.  Is this relation (a) reflexive, (b) symmetric, (c) antisymmetric?

3.  Give a binary relation R on an n-element set such that R  ∅ and IR · R-1 I = n2 o IR-1 · RI.

4. A tree contains, for each d e {3, 9, 10, 11, 12}, exactly one vertex of degree d. All other vertices have degrees 1 and 2. How many vertices have degree 1?

5.   (a)  Prove that if a directed graph G has a cycle, then this G cannot be a Hasse diagram of any partial order.

(b) Find a directed graph that has 5 or fewer vertices, has no loops, parallel edges, or cycles,

and is not a Hasse diagram of any partial order.

6. Find a logical flaw in the following ‘proof’ of the claim that every connected undirected graph G = (V, E) with IV I = IEI + 1 is acyclic:

“Induction on IV I. Base case: if IV I = 1, then G has a single vertex and no edges, so the statement holds.  Inductive step: let us assume the claim holds for every graph G = (V, E) on n vertices. We prove that it also holds for a graph G/ = (V/ , E/ ) that arises from G by adding a new vertex.  In order for the assumption IV/ I = IE/ I + 1 to hold for G/ , we also add one new edge. Since G/  is assumed to be connected, this edge must connect the new vertex to some vertex in V .  Therefore, the new vertex has degree 1 and so it cannot belong to a cycle.  The inductive hypothesis already ensures that G has no cycle, so in fact neither has G/ .”

7. If x1 , x2 , . . . , xn  e Q, prove that Ix1 I + Ix2 I + . . . + IxnI > Ix1 + x2 + . . . + xnI.

8.  Prove that the set M = {x e R : x2  = 2a 3b, a e N, b e N} is countably infinite. Your solution should either give a bijective function f : N 二 M or give pseudo-code of a program that prints all the values of such a function, in the following format (in this case you don’t have to define f explicitly, but need to also show the first five lines of output):

0: element of M

1: another element of M

2: yet another element of M

. . .

9. Let X be any set. Let 0 denote, as usual, the number zero. Prove that X \ {0} is countable if and only if X is countable.  (If needed: use facts/conventions from our lectures only.)

10.  Denote, for every finite set A C Z, by s(A) the number I{(x, y, z) e A3 : 5x _ 6y + 7z = 0}I.

(a) Is it true or false that s(A) < IAI2  for every finite A C Z ?

(b)  Give a nonempty finite set A C Z such that s(A) = IAI2  or prove that no such A exists.