Discrete mathematics

Find a transitive closure of the relation R on {a,b,c,d,e} given by R= {(a,b), (a,c), (a,e),(b,a), (b,c),(c,a), (c,b),(d,a,),(e,d)}

Discrete mathematics

(See attached file for full problem description) --- Let R1 and R2 be relations on a set A. represented by the matrices: M R1 0 1 0 M R2 0 1 0 1 1 1 0 1 1 1 0 0 1 1 1 find the matrices that represent ( show all work) a) R1 union R2 b) R1 interse ...continues

4 Problems

(See attached file for full problem description) --- 1. Show that if A and B are countable and disjoint, then A B is countable. 2. Show that any set, A, of cardinality c contains a subset, B, that is denumerable. 3. Show that the irrational numbers have a cardinality c. 4. Show that if A is equivalent to B and C i ...continues

2 Problems

6. Let (G, *) be a group. Show that each equation of either the form ax = b or the form xa = b has a unique solution in G. 7. Show that (R - {1}, *), where a * b = a + b + ab is a group

2 Problems

5. Let (A, *) be an algebraic structure, and suppose that A is associative, has an identity, e, and that has an inverse. Show that if ax = ay, then x = y. 8. Let G be a finite group with identity e, and let . Show that there is an with an = e (Hint: Consider the set {e, a, a2 , …, am }, where m is the number of element ...continues

Denumerable and Induction

1. Show that if A and > are denumerable disjoint sets then A u > is denumerable 2. Show that every set of cardinalty c contains a denumerable subset 3. Show by induction that 6 divides n^3 - n for all n in N

Sets

In each part of this problem, display an example of a set M with the specific property or properties. a) M does not equal R (R is the set of all real numbers), but M is bounded neither above nor below. b) M is bounded above but fails to contain its least upper bound. c) M is the set of integers that contains neither a s ...continues

Big O notation

i) Show that x^3 is O(x^4) but x^4 is not O(x^3) ii)Show that xlnx is O(x^2) but x^2 is not O(xlnx) iii)Show that a^x O(b^x) but b^x is not O(a^x) if 0 < a < b (0 = zero) iv)Show that 1^k + 2^k+...+n^k is O(n^(k+1)) for every positive integer k

Recursive algorithms

Write a recursice algorithm to find x^n mod m whenever n,x and m are positive integers based on the fact that : x^n mod m = (x^(x-1) mod m * x mod m)mod m

Congruences

Find all common solutions to the congruences (in the folowin notations the = is meant to be a congruence symbol) x=2(mod 3), x=1(mod 4), x=3(mod 5), x=4(mod 7)