CS 610讲解、讲解anti-symmetric、辅导Python，c++，Java编程语言

Assignment 1 (40 points)

CS 610 Spring 2019

Instructor : Ravi Varadarajan

Due : Jan 30,2019 in class

Problem 1. (5 points) A relation ρ on a set A is circular if (x, y) ∈ ρ∧(y, z) ∈ρ = (z, x) ∈ ρ for x, y, z ∈ A. Prove that a reflexive, circular relation is an

equivalence relation.

Problem 2. (5 points) Consider the function f : R → R where f(x) = x2. Is

f injective ? Is it surjective ? Explain your answer.

Problem 3. (12 points) A relation ≤ on a set S is called ”partial-order” if it

is (i) reflexive, (ii) transitive and (iii) anti-symmetric i.e a, b ∈ S, a ≤ b ∧ b ≤a = a = b.

(a) Let P(A) be the power set (i.e. set of all subsets) of a set A. Consider the

subset relation on P(A). Show that it is a ”partial order”.

(b) Let ≤ be a partial order defined on a set S. Given X S, an element

y ∈ X is a least element of X if y ≤ x, ?x ∈ X. Show that a least element

of X if it exists must be unique.

(c) Let A = {1, 2, 3} and let X = {{1}, {1, 3}, {1, 2}}. Does the least element

of X exist for the partial order ? If it exists, what is it ?

(d) What is the least element of P(A) for partial order ?

Problem 4. (10 points) Given two functions f : N → R+ and g : N → R+, we

say that f(n) is o(g(n)) if for all real constants c > 0, ?n0 > 0 such that for all

n ≥ n0, f(n) ≤ cg(n).

(a) Prove that f(n) is o(g(n)) iff limn→∞f(n)g(n) = 0.

(b) Prove that ln2

(n) is o(√n).

Problem 5. (8 points) Suppose there are n circles which intersect each other

at exactly 2 points. Prove by induction that they create n

2n + 2 regions.