## Fall 2020

Warning: This quiz is as long as the actual Quiz 4. However, it  does not cover all of the materials of the actual Quiz 4.

1 .(5 minutes) Prove that the function f : Z Z with f(x) = 2x + 3 is one-to-one.

2 .(5 minutes) Prove for any relation R on a set A, if R = R1 , then R is symmetric.

3. (8 minutes) Prove or provide a counterexample to the proposition be-low:

The relation R on Z given by R = {(a, b) : a = b} is symmetric and transitive.

4. (10 minutes)

Prove or provide a counterexample to the propositions below:  离散结构quiz代写

The relation R on S = {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} given by R ={(a, b) S × S : a|b} is

(a) Reflexive

(b) Antisymmetric

(c) Transitive

(d) Is R a strict order on S (Yes/No)?

(e) Is R a partial order on S or a total order? If R is a partial order,draw its Hasse Diagram. If R is a total order, which element(s)would need to be removed so that R would be a partial order?

For each question, provide detailed proofs/justifications.

### 5.(15 minutes) Let A = {0, 1, 2, 3, 4, 5} and B = {0, 1, 2, 3}

(a) There is no possible function f : A B that is one-to-one. (True/False)

(b) There is no possible function f : A B that is onto. (True/False)

(c) g = {(0, 0),(1, 2),(2, 1),(4, 3),(5, 3)} is a function from A to B.(True/False)

(d) Let R be a relation with domain B and codomain B, and R ={(0, 1),(1, 2),(2, 3),(3, 3),(3, 0)}:

i.Is R Transitive? (Yes/No)

ii.Is R Antisymmetric? (Yes/No)

iii. Is R Reflexive? (Yes/No)

iv.Is R R antisymmetric? (Yes/No)

(e) Let R be a relation with domain A and codomain A where (x, y) R if x mod 3 = y. Is R Antisymmetric? (Yes/No)

6.(6 minutes) Let f : R R, where f(x) = x 2 .

(a) Prove f is one-to-one, or provide a counterexample:

(b) Prove f is onto, or provide a counterexample:

(c) Is f a one-to-one correspondence? (Yes/No)

For each question, provide detailed proofs/justifications.

### 7.(10 minutes) Consider the relation R on P({x, y, z}) given by R ={(A, B) : A ∪ B = {x, y, z}}.  离散结构quiz代写

[(a)]

(a) Prove R is reflexive, or provide a counterexample.

(b) Prove R is symmetric, or provide a counterexample.

(c) Prove R is transitive, or provide a counterexample.

(d) Is R an equivalence relation? (Yes/No)

For each question, provide detailed proofs/justifications.

8.(10 minutes) Let A = {1, 2, 3, 4}. Functions f and g are defined as below.

f : A (A × A) with the rule f(a) = (a, a)

g : (A × A) A with the rule g(x, y) = x

Are f and g inverses of each other? (Yes/No)

Provide a detailed proof of your decision.

Hint: checking f g and g f.

### 9. (10 minutes) Let A = {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}, and let a relation R on A be defined with the rule:  离散结构quiz代写

R = {(a, b) A2 : a and b have the same set of prime factors}.

For example, 2 and 8 have the same set of prime factors: {2}.

2 and 12 do not have the same set of prime factors; the prime factors of 12 are {2, 3}.

Prove R is an equivalence relation on A, or give a counterexample. If R is an equivalence relation, what is the partition of A induced by R?

Basic Algebra Cheatsheet1

1 Resources:http://tutorial.math.lamar.edu/pdf/Algebra_Cheat_Sheet.pdf