Discrete Mathematics

Let A be the set odd positive integers less than 10. Then cardinality of A, ∣A∣ is

(i) 5
(ii) 9
(iii) 6
(iv) 4

If m is the number of objects (pigeons) and n is the number of boxes (pigeonholes), then the function is both one-to-one and onto if
(i) m<n
(ii) m=n
(iii) m>n
(iv) none of these

Which of the following statements regarding sets is false?

(i) $A \cap A = A$
(ii) $A \cup A = A$
(iii) $A - (B \cap C) = (A - B) \cup (A - C)$
(iv) $(A \cup B)' = A' \cup B'$

If $f(x) = \cos x$ and $g(x) = x^3$ then $(f \circ g)(x)$ is
(i) $(\cos x)^3$
(ii) $\cos 3x$
(iii) $x^{(\cos x)^3}$
(iv) $\cos x^3$

The number of distinguishable permutations of the letters in the word BANANA are
(i) 60
(ii) 36
(iii) 20
(iv) 10

Which of the following two sets are equal?

(i) $A = \{1, 2\}$ and $B = \{1\}$
(ii) $A = \{1, 2\}$ and $B = \{1, 2, 3\}$
(iii) $A = \{1, 2, 3\}$ and $B = \{2, 1, 3\}$
(iv) $A = \{1, 2, 4\}$ and $B = \{1, 2, 3\}$

Let $N = \{1,2,3,......\}$ be ordered by divisibility, which of the following subset is totally ordered
(i) $\{2, 6, 24\}$
(ii) $\{3, 5, 15\}$
(iii) $\{2, 9, 16\}$
(iv) $\{4, 15, 30\}$

a) Let $A = B = \{x | -1 \leq x \leq 1\}$ for each of the following functions state where it is injective, surjective or bijective
i) $g(x) = \sin \pi x$
ii) $h(x) = \frac{2x}{3}$

(a) Let
$D = \{-48, -14, -8, 0, 1, 3, 16, 23, 26, 32, 36\}$

Determine which of the following statements are true and which are false. Provide counterexamples for those statements that are false.

(i) $\forall x \in D$, if $x$ is odd, then $x > 0$
(ii) $\forall x \in D$, if $x$ is less than 0, then $x$ is even
(iii) $\forall x \in D$, if $x$ is even, then $x \le 0$

Let $f(x) = x+2$, $g(x) = x-2$, $h(x) = 3x$ find
(i) $f \circ g$
(ii) $f \circ g \circ h$

Use Cantor's diagonal argument to prove that set F of all functions $f: (0,1) \rightarrow R$ has larger Cardinality than $|R|$.

(b) Indicate which of the following statements are true and which are false. Justify your answers as best you can:

(i) $\forall x \in \mathbf{Z}^+, \exists y \in \mathbf{Z}^+$ such that $x = y+1$
(ii) $\forall x \in \mathbf{Z}, \exists y \in \mathbf{Z}$ such that $x = y+1$
(iii) $\exists x \in \mathbf{R}$ such that $\forall y \in \mathbf{R}, x = y+1$
(iv) $\forall x \in \mathbf{R}^+, \exists y \in \mathbf{R}^+$ such that $xy = 1$
(v) $\forall x \in \mathbf{R}, \exists y \in \mathbf{R}$ such that $xy = 1$
(vi) $\forall x \in \mathbf{Z}^+ \text{ and } \forall y \in \mathbf{Z}^+, \exists z \in \mathbf{Z}^+ \text{ such that } z = x-y$
(vii) $\forall x \in \mathbf{Z} \text{ and } \forall y \in \mathbf{Z}, \exists z \in \mathbf{Z} \text{ such that } z = x-y$
(viii) $\exists u \in \mathbf{R}^+ \text{ such that } \forall v \in \mathbf{R}^+, uv < v$

a.) find the power set of each of these sets
i) $\{a, b\}$
ii) $\{\emptyset, \{\emptyset\}\}$

Determine if the sets are countable or uncountable
a.) the set A of all function $g: Z_+ \rightarrow Z_+$
b.) The set B of all functions $f: Z_+ \rightarrow \{0,1\}$

Let $G=(V, E)$ be a simple graph. Let $R$ be the relation on $V$ consisting of pairs of vertices $(u,v)$ such that there is a path from $u$ to $v$ or such that $u=v$. Show that $R$ is an equivalence relation.

If $A$ and $B$ are two nonempty sets having $n$ elements in common, then $A \times B$ and $B \times A$ will have how many elements in common?
(i) $2^n$
(ii) $n^2$
(iii) $n^4$
(iv) $2n$

If a set A have n elements, then how many relations will be there on set A?
(i) n^2
(ii) 2^(n^2)
(iii) 2^n
(iv) 2n

(e) If P(Φ) represents the power set of Φ, then n(P(P(P(Φ)))) equal to
(i) 1
(ii) 2
(iii) 3
(iv) 4

(f) For the poset [{3, 5, 9, 15, 24, 45}]; divisor of | the bus of {3, 5} is
(i) 3
(ii) 5
(iii) 15
(iv) 45

(g) If (S, *) is a monoid, where S = {1, 2, 3, 6} and * is defined by a * b = lcm(a, b), where a, b ∈ S, then the identity element is
(i) 1
(ii) 2
(iii) 3
(iv) 6

(h) The total number of subgroups of group G of prime order is
(i) 1
(ii) 2
(iii) 3
(iv) 4

(i) The number of edges in a bipartite graph with n vertices is at most (i) n^2/2 (ii) n^2/4 (iii) n^2 (iv) 2n

For any sets A and B, prove that
(i) (A ∪ B)' = A' ∩ B'
(ii) (A ∩ B)' = A' ∪ B'

If two sets A and B have n elements in common, then show that the sets A × B and B × A will have 2^n elements in common.