Cheatography

# A Cheat Sheet (DRAFT) by j24

Ajsickcjdiskdjjckzkaoxowkcjc

This is a draft cheat sheet. It is a work in progress and is not finished yet.

### Propos­itions

 Different Ways of Expressing p → q q unless ¬p, q if p, q whenever p, q follows from p, p only if q, q when p, p is sufficient for q, q is necessary for p. Propos­ition True/F­alse, with no variables. Ex) The sky is blue = Prop. n+1 is even Not prop bc n is unknown. Tautology a propos­ition which is always true. Ex) p ∨¬ p contra­diction a propos­ition which is always false. Ex) p ∧¬ p contin­gency a propos­ition which is neither a tautology nor a contra­dic­tion, such as p satisf­iable at least one truth table is true. p -> q Only false when p = T q = F. everthing else true. converse q -> p inverse -p -> -q contra­pos­itive -q -> -p p <-> q if and only if. true if and only if p and q have the same truth value ex) p = t q = t or p = f q = f Logically equivalent p≡q. all truth values have to be the equal aka same results. Negate Quanti­fiers ¬∀xP (x) ≡ ∃x ¬P (x). ¬∃xQ(x) ≡ ∀x ¬Q(x)

### Functions

 function from A to B. f: A -> B an assignment of exactly one element of B to each element of A domain of f the set A, where f is a function from A to B. ans is A codomain of f the set B, where f is a function from A to B. ans is B b is the image of a under f b = f (a). "what does this map to" a is a pre-image of b under f f (a) = b. "what values map to this". range values of codomain that were mapped to by domain. Injective Function (one to one) a function f is one-to-one if and only if f (a) =/= f (b) whenever a =/= b. each value in the range is mapped to exactly one element of domain. (each range value is mapped once). ∀a∀b(f (a) = f (b) → a = b) or equiva­lently ∀a∀b(a =/= b → f (a) =/= f (b)) Surjective function (onto) every element in codomain maps to at least one element in domain. (each element in codomain is mapped). if and only if for every element b ∈ B there is an element a ∈ A with f (a) = b To show that f is injective f(x1)=­f(x2) => x1=x2. x1=/=x2 => f(x1)=­/=f­(x2). ex) f(a) = f(b) => a=b. ex) f(x) = x+3. f(a) = 7, a+3=7, a=4. f(b)=7. b=4. f(a)=f(b) a=b, 1to1 To show that f is not injective Find particular elements x, y ∈ A such that x /= y and f (x) = f (y) To show that f is surjective solve in terms of x. pick 2 random ys, if x eqns comes back in domain, surjec­tive. domain matters, Z, R, N has to map x and y in same. ex) f(x)=x+3. f(4)=7, f(5)=8. always mapped, onto. To show that f is not surjective Find a particular y ∈ B such that f (x)  = y for all x ∈ A Bijective function all range is mapped to and mapped to once (injective and surjec­tive) Inverse has to be bijective. f^-1(y) = x if and only if f(x) = y. because this is both 1to1 and onto, its a bijection, therefore invert­ible. compos­ition of fns f(g(a)) or f o g(a) floor/­ceiling bracke­twi­thlow only/h­igh­only. round down/up to nearest integer. ex) -2.2 floor = -3. 5.5 ceil = 6. properties x floor = n if and only if n ≤ x < n + 1. x ciel = n if and only if n − 1 < x ≤ n. x floor = n if and only if x − 1 < n ≤ x. x ciel = n if and only if x ≤ n < x + 1. x − 1 < floorx ≤ x ≤ cielx < x + 1. floorx = −cielx. cielx = -floorx. ciel(x + n) = cielx + n. opp of last floor ex) let f(x) = floor(­(x^­2)/2). find f(S) if S={0,1­,2,3} f(0) = 0, f(1) = 0. f(2) = 2, f(3) = 4 equal functions Two functions are equal when they have the same domain, the same codomain and map each element of the domain to the same element of the codomain

### Proofs

 Direct Proof assume p is true, prove q. p => q. Always start with this then try contra­pos­ition. Proof by contra­pos­ition assume q is true, prove p. (q => p) equals (p => q) Vacuous proof if we can show that p is false, then we have a proof, called a vacuous proof, of the condit­ional statement p → q Proof by contra­diction Assume p is true, find contra­dic­tion, therefore p is true. prove that p is true if we can show that ¬p → (r ∧ ¬r) is true for some propos­ition r Counte­rex­ample to show that a statement of the form ∀xP (x) is false, we need only find a counte­rex­ample. Proof by exhuastion ex: Prove that (n + 1)3 ≥ 3n if n is a positive integer with n ≤ 4. Prove by doing n = 1,2,3,4 Proof by cases ex: Prove that if n is an integer, then n2 ≥ n. Case (i): When n = 0. Case (ii): When n ≥ 1. Case (iii): In this case n ≤ −1 Constr­uctive Existence Proof ∃xP(x). To find if P(x) exists, show an example P(c) = True Noncon­str­uctive Existence Proof Assume no values makes P(x) true. Then contra­dict. UNIQUENESS proof When asked for unique, prove exists, then unique. ex: x exists, x=/=y , so y doesnt have that property, therefore x is unique. without loss of generality an assumption in a proof that makes it possible to prove a theorem by reducing the number of cases to consider in the proof

### Sets

 Element of set a ∈ A, a ∈/ A roster method V = {a, e, i, o, u}, O = {1, 3, 5, 7, 9}. set builder notation ex: the set O of all odd positive integers less than 10 can be written as: O = {x ∈ Z+ | x is odd and x < 10}. ex) A = {𝑥|𝑥 ≥ −1 ∧ 𝑥 < 1}. ex) {x | P(x)| Interval Notation [-2,8) Natural numbers N N = {0, 1, 2, 3, . . .} Integers Z Z = {. . . , −2, −1, 0, 1, 2, . . .} Positive Integers Z+ Z+ = {1, 2, 3, . . .} Rational Numbers Q Q = {p/q | p ∈ Z, q ∈ Z, and q =/= 0} Real Numbers R All previous sets (N, Z, Q) R+ positive real numbers Complex numbers C {a+bi, ...} Equal Sets Two sets are equal if and only if they have the same elements. Therefore, if A and B are sets, then A and B are equal if and only if ∀x(x ∈ A ↔ x ∈ B). We write A = B if A and B are equal sets. Dont matter if its {1,3,3­,3,­2,2­,3,}, still {1,3,2}. Also dont matter order. Null/ Empty Set ∅, nothing. {}. {∅} 1 element Singleton set One element. Universal Set U Universe in context of statement. Example vowels in alphabet: U = {z,y,x,w, ...}, A = {a,e,i­,o,u} A is a subset of U. Subset ∀x(x ∈ A → x ∈ B). Ex) the set A is a subset of B if and only if every element of A is also an element of B. We use the notation A ⊆ B to indicate that A is a subset of the set B. Ex) A = {1,2,3}, B = {1,2,3,4}, A ⊆ B. Showing that A is a Subset of B To show that A ⊆ B, show that if x belongs to A then x also belongs to B. Showing that A is Not a Subset of B To show that A ⊆/ B, find a single x ∈ A such that x ∈/ B. Showing Two Sets are Equal To see if A = B, Show A ⊆ B and B ⊆ A proper subset ∀x(x ∈ A → x ∈ B) ∧ ∃x(x ∈ B ∧ x  ∈ A)A ⊆ B but A =/= B. B contains an element not in A. Ex) A = {1,2,3}, B= {1,2,3,4}. 4 makes it proper subset. Cardin­ality |A| Distinct elements of set. A = {1,2,3­,3,4,4} |A| = 4 Power Set the power set of S is the set of all subsets of the set S. The power set of S is denoted by P(S). Ex) A = {1,2,3}. P(A) = {∅, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}}. Ex) P({∅}) = {∅, {∅}} Cardin­ality of Power Set 2^n, n is elements. Tuple (a1,a2,a3, ..., an) Ordered. Ex) (5,2) =/= (2,5) Cartesian Product {(a, b) | a ∈ A ∧ b ∈ B}. The Cartesian product of A and B, denoted by A × B, is the set of all ordered pairs (a, b), where a ∈ A and b ∈ B. Ex) A = {0,1} B = {2,3,4}, A x B = {(0,2)­,(0­,3)­,(0­,4)­,(1­,2)­,(1­,3)­,(1,4)} Truth Set P(x): abs(x) = 3. Truth Set of P(x) = {3,-3}

### Set Operations

 Union A ∪ B = {x | x ∈ A ∨ x ∈ B}. Ex) A = {1,4,7} B = {4,5,6}. A ∪ B = {1,4,5­,6,7} Inters­ection A ∩ B = {x | x ∈ A ∧ x ∈ B}. Ex) A = {1,4,7} B = {4,5,6}. A ∩ B = {4}. disjoint If A ∩ B = nothing, A and B are disjoint. principle of inclus­ion­–ex­clusion |A ∪ B| = |A| + |B| − |A ∩ B| ex) A = {1,2,3­,4,5}, B ={4,5,­6,7,8}. }A u B| = |A| + |B| -|A n B} = 5 + 5 - 2 = 8 A − B, difference of A and B A - B = A ∩ B. {x | x ∈ A ∧ x /∈ B} Elements in A that are not in B. Ex) {1, 3, 5} − {1, 2, 3} = {5}. This is different from the difference of {1, 2, 3} and {1, 3, 5}, which is the set {2}. Complement of A, A^c {x ∈ U | x /∈ A} Everything in the universe context thats not in A. Ex) U = {1,2,3,4}. A = {2} B = {3}. A^c = {1,3,4} U = ℝ A = {𝑥|𝑥 ≥ −1 ∧ 𝑥 < 1}, B ={𝑥|𝑥 < 0 ∨ 𝑥 ≥ 2} 𝐴 ∪ 𝐵 = {𝑥|𝑥 < 1 ∨ 𝑥 ≥ 2}. 𝐴 ∩ 𝐵 = {𝑥|𝑥 < 0 ∧ 𝑥 ≥ −1}. 𝐴^c = {𝑥|𝑥 < −1 ∨ 𝑥 ≥ 1}. Identity, , , , , , , absorb­tion, A ∩ U = A. A ∪ ∅ = A. domination A ∪ U = U. A ∩ ∅ = ∅ idempotent A ∪ A = A. A ∩ A = A comple­men­tation (Ac)c = A commut­ative A ∪ B = B ∪ A. A ∩ B = B ∩ A associ­ative A ∪ (B ∪ C) = (A ∪ B) ∪ C. A ∩ (B ∩ C) = (A ∩ B) ∩ C distri­butive A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C). A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) de morgans (A n b)c = Ac u Bc. (A U B)c = Ac n Bc absorption A ∪ (A ∩ B) = A. A ∩ (A ∪ B) = A. complement A ∪ Ac = U. A ∩ Ac = ∅. countable a set that either is finite or can be placed in one-to-one corres­pon­dence with the set of positive integers. To be countable, there must exist a 1-1 and onto (bijec­tion) between the set and ℕ! (i.e. ℤ+) Ex) Show that the set of positive even integers E is countable set. Let f(x) = 2x. Then f is a bijection from N to E since f is both one-to-one and onto. To show that it is one-to­-one, suppose that f( n) = f( m). Then 2 n = 2 m, and so n = m. To see that it is onto, suppose that t is an even positive integer. Then t = 2k for some positive integer k and f(k) = t