Term
|
Definition
A set is "a collection of elements"
x∈X x is an element/member of X
x∉X x is not in X
A⊆X A is a subset of X (A is a set and all elements of A are in X)
A is a proper set if A≠X
A⊂X |
|
|
Term
|
Definition
| X∪Y, a union is a set whose members are either elements of X or Y |
|
|
Term
|
Definition
| X∩Y, an intersection is a set whose members are in both X and Y |
|
|
Term
|
Definition
| X∖Y, the complement of Y in X is the set of elements of X not contained in Y |
|
|
Term
|
Definition
1. Z∖(X∪Y)=(Z∖X)∩(Z∖Y)
2. Z∖(X∩Y)=(Z∖X)∪(Z∖Y) |
|
|
Term
|
Definition
| A function f from X to Y, f:X→Y, is "a rule which assigns to every element of x∈X an element of Y" |
|
|
Term
|
Definition
| f is injective (one-to-one) if f(x1)=f(x2)⇒x1=x2
or
x1≠x2⇒f(x1)≠f(x2) |
|
|
Term
|
Definition
| f is surjective (onto) if ∀y∈Y, ∃x∈X s.t. f(x)=Y (at least one) |
|
|
Term
|
Definition
| f is bijective if it is both injective and surjective |
|
|
Term
|
Definition
| f is invertible if there is g:Y→X s.t. g∘f=idx and f∘g=idy
The inverse of f is g=f-1 |
|
|
Term
| Fact about invertible functions and bijections |
|
Definition
| f is invertible iff f is a bijection |
|
|
Term
|
Definition
Prove a base case. (n=1)
Assume statement holds for n. Show it holds for n+1. (Use base case) |
|
|
Term
|
Definition
Check that P(1) holds (base case)
If P(1), P(2),...P(n) all hold, show that P(n+1) holds. |
|
|
Term
|
Definition
| A set X is finite if ∃n∈ℤ≥0, X has n elements |
|
|
Term
|
Definition
X is infinite if it is not finite
ℕ, ℤ, ℚ, ℝ all infinite |
|
|
Term
|
Definition
| If there is a bijection from X to a set of n elements and another bijection from X to a set of k elements, the n=k. |
|
|
Term
| Thm: Union and Complement |
|
Definition
1) If X and n elements and Y has k elements and X∩Y=∅, then X∪Y has n+k elements.
2) If Z⊆X, X has n elements Z has k elements then X∖Z has n-k elements |
|
|
Term
|
Definition
| If Z⊆X, X is infinite and Z has n elements, then X∖Z is infinite |
|
|
Term
| Thm: Z⊆X (finite and infinite) |
|
Definition
1) if X is finite, so is Z
2) if Z is infinite, so is X |
|
|
Term
|
Definition
| If there is a bij between set X and ℕ, X is denumberable or countably infinite. |
|
|
Term
|
Definition
| X is Countable if it is denumerable of finite |
|
|
Term
|
Definition
| X is uncountable if it is not countable |
|
|
Term
| Union of two countable sets... |
|
Definition
|
|
Term
| Thm: Z⊆X (countable and uncountable) |
|
Definition
1) if Z is uncountable⇒so is X
2) if X is countable⇒so is Z |
|
|
Term
|
Definition
The following are equivalent:
1)X is countable
2)There is a surjection ℕ->X
3) There is an injection X->ℕ |
|
|
Term
| ℚ countable or uncountable? |
|
Definition
|
|
Term
|
Definition
| There is a subset ℙ⊆ℝ (postive) satisfying
1)a,b∈ℙ, then a+b∈ℙ
2)a,b∈ℙ, then ab∈ℙ
3)(Trichotemy) ∀aℝ, exactly one of the following is true: a∈ℙ or a=0 or -a∈ℙ |
|
|
Term
|
Definition
| i)If a≠0, then a2>0
ii) 1>0 |
|
|
Term
|
Definition
The absolute value of x∈ℝ is
|x|={x if x≥0, -x if x<0} |
|
|
Term
|
Definition
|a+b|≤|a|+|b|
Equivalent:
|a-b|≤|a|+|b|
||a|-|b||≤|a-b| |
|
|
Term
|
Definition
|
|
Term
|
Definition
|
|
Term
|
Definition
Let S be nonempty.
1) An Upperbound for S is u∈ℝ s.t. s≤u ∀s∈S
If S has an upperbound, say S is bounded above.
2) A lowerbound for S is l∈ℝ s.t. l≤s ∀s∈S
If S has a lower bound, say S is bounded below
S is bounded if bounded above and below |
|
|
Term
|
Definition
Let S be nonempty.
Say x is a supremum (least upper bound) if
1)x is an upperbound
2)if u is another upperbound, x≤u
Say y is an infimum (greatest lower bound) if
1)y is a lower bound
2)if l is another lowerbound, y≥l |
|
|
Term
|
Definition
Let S be nonempty. Then u=supS iff
1)u≥s s∈S
2)If v less than u then s∈S s.t. s>v |
|
|
Term
|
Definition
Let S be nonempty.
Then u=supS⇔∀ε>0 there is some s∈S s.t. s>u-ε |
|
|
Term
|
Definition
| If ∅≠S⊆ℝ and S is bounded above the supS exists in ℝ. |
|
|
Term
| Archimedean Property of ℕ |
|
Definition
| Given any x∈ℝ, there is some n∈ℕ s.t. n>x |
|
|
Term
|
Definition
|
|
Term
| Characterization of Intervals |
|
Definition
| Let S⊆ℝ have at least 2 points. Suppose if xThen S is an interval |
|
|
Term
| Thm: Nested Intervals Property |
|
Definition
| Let I1⊇I2⊇I3... be nested, nonempty, closed intervals.
Then
1)∩nIn≠∅
2) If In=[an,bn] and infn{bn-an}=0, Then ∩nIn contains a single point |
|
|
Term
| Thm: ℝ countable or uncountable |
|
Definition
|
|
Term
|
Definition
| A sequence in ℝ is just a function ℕ->ℝ
ex: (1/n)=1/1, 1/2, 1/3,...
((-1)n)=-1,1,-1,1,-1,... |
|
|
Term
|
Definition
| A seq (xn) converges to a∈ℝ if for every ε>0, there is Kε∈ℕ s.t. ∀n>Kε, |xn-a|<ε
We say seq converges if it converges to some a.
If seq doesnt converge to any a, then it diverges
Alt: lim(n→oo) xna |
|
|
Term
|
Definition
| Given K∈ℕ, the elements xn for n>K form a "tail" of the seq. |
|
|
Term
|
Definition
| If (xn) converges, then it is bounded. |
|
|
Term
|
Definition
| (xn)+(yn)=(xn+yn)
(xn)*(yn)=(xn*yn) |
|
|
Term
|
Definition
| Suppose (xn)→x and (yn)→y
Then:
1) (xn)+(yn)→x+y
2) (xn)*(yn)→x*y
3) (xn)/(yn)→x/y |
|
|
Term
| Prop: less than/greater than |
|
Definition
| If (xn)→x, (yn)→y and xn≤yn, then x≤y |
|
|
Term
|
Definition
| Suppose xn≤yn≤zn, (xn)→x, zn→z and z=x.
Then yn→x |
|
|
Term
|
Definition
| Let xn>0 ∀n
Suppose lim xn+1/xn=L<1
Then xn→0 |
|
|
