Summary Discrete Mathematics I

A relation R on a set A is a subset of A×A. The domain of R, denoted dom(R), is the set of all x such that (x,y)∈R. The range of R, denoted ran(R), is the set of all y such that (x,y)∈R. Therefore ran(R) = {y∣∃x∈A s.t. (x,y)∈R}. If A is finite, A relation is a binary relation on the set A. A relation is a way to associate elements from two sets. A binary relation R is a set of ordered pairs. The first element of each pair is an element of the first set, and the second element is an element of the second set. A binary relation maps some, none, one, or more than one of the following properties. Let A be any nonempty set. A binary relation R on A is said to be: Reflexive if for all x∈A, (x,x)∈R. Irreflexive if for all x∈A, (x,x)∈ / R. Symmetric if for all x,y∈A, if (x,y)∈R, then (y,x)∈R. Asymmetric if for all x,y∈A, if (x,y)∈R, then (y,x)∈ / R. Antisymmetric if for all x,y∈A, if (x,y)∈R and (y,x)∈R, then x=y. Transitive if for all x,y,z∈A, if (x,y)∈R and (y,z)∈R, then (x,z)∈R. An equivalence relation is a relation that is reflexive, symmetric, and transitive. A partial order relation is a relation that is reflexive, antisymmetric, and transitive. For nonempty sets A,B, a function, or mapping, f from A to B, denoted f:A→B, is a relation from A to B such that every element of A appears exactly once as the first component of an ordered pair in the relation. For the function f:A→B, A is called the domain of f and B is the codomain of f. The range of f, denoted ran(f), is the set of all elements in B that appear as the second component of an ordered pair. The range of f is also denoted by f(A) because it is the set of images of the elements of A under f. A function f:A→B is called one-to-one, or injective, if each element of B appears at most once as the image of an element of A. A function f:A→B is called onto, or surjective, if f(A)=B, that is, if for all b∈B there is an a∈A s.t. f(a)=b. Let A,B,C be sets. Two functions, the composite function of g and f, denoted g∘f, is the set of all pairs defined as follows: g∘f={(a,c)∣∃b∈B such that (a,b)∈f and (b,c)∈g} The "or" operator is called the "function composition" operator, and it possesses the following properties: 1-to-one and g one-to-one implies g∘f is one-to-one. g∘f onto implies g is onto. The composition operator is associative: That is, if f:A→B, g:B→C, and h:C→D, then h∘(g∘f)=(h∘g)∘f. The inverse function of a function f is the function that satisfies the following: f∘f −1 =I A ​ where I A ​ is the identity function on A. The inverse of f is usually denoted f −1 . That is, g∘f=I A ​ . Corollary: If f is an injective function from A to B and ∣A∣=∣B∣, then f is a bijective function. The identity function on A is the function I A ​ :A→A such that I A ​ (x)=x for all x∈A. Theorem: If f:A→B and g:B→C are functions such that g∘f is a bijection, then f is an injection and g is a surjection. Quantifiers (Logic) Let P(x,y) be a statement. ∀xP(x,y): For all x, P(x,y) is true. ∃xP(x,y): There exists an x such that P(x,y) is true. ∀x∃yP(x,y): For all x, there exists a y such that P(x,y) is true. ∃x∀yP(x,y): There exists an x such that for all y, P(x,y) is true. ∀x∀yP(x,y): For all x and for all y, P(x,y) is true. ∃x∃yP(x,y): There exists an x and there exists a y such that P(x,y) is true. Conclusion Premises Justification 1. (P→R)∧(R→S) 1. ∀x(P(x)→R(x)) premise 2. P→S 2. R→S premise 3. (P→S)∧(S→R) 3. (P→S)∧(S→R) existential instantiation 4. P→R 4. P→S universal instantiation 5. P→S 5. P→Q modus ponens 6. Q→R 6. R→S modus tollens 7. S→T 7. S→T simplification 8. Q→S 8. Q→S conjunction 9. Q→¬S 9. Q→¬S addition 10. (P∧Q)→R 10. (P∧Q)→R disjunctive syllogism 11. P→(Q→R) 11. P→(Q→R) hypothetical syllogism 12. ¬Q→¬P 12. ¬Q→¬P existential generalization 13. (P↔Q)→(¬P∨Q) 13. (P↔Q)→(¬P∨Q) equivalence 14. (¬P∨Q)→(¬Q∨P) 14. (¬P∨Q)→(¬Q∨P) existential generalization (A ∪ B ∪ C) ∩ (D ∪ E) Provide only one set: P 1 ​ =B∩C∪D. No sets to provide. Let A,B,C,D be subsets of U. Then A∪B⊆C∪D. DeMorgan's Law for sets A,B⊆U can be generalized as follows: Let A 1 ​ ,A 2 ​ ,…,A n ​ be subsets of U. Then (∪ i=1 n ​ A i ​ ) c =∩ i=1 n ​ A i c ​ . Provide a proof of the general form of DeMorgan's Law. For each x∈U, x∈(∪ i=1 n ​ A i ​ ) c ⟺x∈ / ∪ i=1 n ​ A i ​ ⟺∀i(x∈ / A i ​ )⟺∀i(x∈A i c ​ )⟺x∈∩ i=1 n ​ A i c ​ . The inverse function of a function f is the function that satisfies the following: f∘f −1 =I A ​ The inverse of f is usually denoted f −1 . That is, g∘f=I A ​ . Corollary: If f is an injective function from A to B and ∣A∣=∣B∣, then f is a bijective function. One-to-one correspondence between their elements. That is, there is a one-to-one function f:A→B. Domain and Range (x,y) (x,y) (0,0) (0,0) (0,1) (0,1) (1,0) (1,0) (1,1) (1,1) Show that for any sets A, B, and C, if A⊆C and B⊆C, then A∪B⊆C. Case 1: x∈A. Since A⊆C, x∈C. Case 2: x∈B. Since B⊆C, x∈C. Therefore if x∈A∪B, then x∈C. So A∪B⊆C. Show that for any sets A, B, and C, if A⊆B and B⊆C, then A⊆C. Case 1: x∈A. Since A⊆B, x∈B. Since B⊆C, x∈C. Therefore if x∈A, then x∈C. So A⊆C. Therefore A∩B=∅. A, B, C are sets satisfying the following: Let A,B,C be sets. A∩B=∅. If x∈ / A, then x∈B. If x∈ / B, then x∈A. (A) f(x)=x 2 +2x+1 ANSWER: x 2 +2x+1 (B) f(x)= x−1 x 2 −1 ​ ANSWER: x+1 (C) f(x)= x 2 +2x+1 x 2 −1 ​ ANSWER: x+1 x−1 ​ (D) f(x)= x−2 x 2 −4 ​ ANSWER: x+2 (E) f(x)=x 2 −1 ANSWER: x 2 −1 Theorem: If g:B→C and f:A→B are functions, then: (I) If g∘f is one-to-one, then f is one-to-one. Assume g∘f is one-to-one. Suppose f(x 1 ​ )=f(x 2 ​ ) for x 1 ​ ,x 2 ​ ∈A. Then g(f(x 1 ​ ))=g(f(x 2 ​ )). So (g∘f)(x 1 ​ )=(g∘f)(x 2 ​ ). Since g∘f is one-to-one, x 1 ​ =x 2 ​ . Therefore f is one-to-one. (II) If g∘f is onto, then g is onto. Assume g∘f is onto. Let z∈C. Since g∘f is onto, there exists x∈A such that (g∘f)(x)=z. This means g(f(x))=z. Let y=f(x). Then y∈B. So g(y)=z. Therefore, for every z∈C, there exists y∈B such that g(y)=z. This means g is onto. (III) Let P(n) be the statement "n 2 ≤n". Show that P(n) is false for n=2. P(2):2 2 ≤2⟹4≤2, which is false. (IV) Show that P(n) is false for n=1. P(1):1 2 ≤1⟹1≤1, which is true. (The instruction seems to contradict the actual statement) It seems the question intended to say "n 2 ≤n" is false for some other values or the question text is a bit off for n=1. (V) Show that P(n) is true for all n∈Z + where Z + is the set of positive integers. This is false for n>1. (VI) Show that P(n) is true for all n∈{0,1}. P(0):0 2 ≤0⟹0≤0, which is true. P(1):1 2 ≤1⟹1≤1, which is true. So, P(n) is true for n∈{0,1}.