Show Menu
Cheatography

A Cheat Sheet (DRAFT) by

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