Assume is true, then show that must also be true.
proof of contrapositive
Assume is false, then show that must also be false.
proof by contradiction
Assume is true and is false. Then show that this leads to a contradiction.
a statement is a sentence that is either true or false.
[see the comp182 logic section]
Disjoined conclusions §
[see the comp182 logic section]
[see the comp182 sets section]
Indexed families of sets §
[see the comp182 induction section]
Real vs Rational numbers §
Upper and lower bounds §
A number is an upper bound of if for any , . We say that is bounded from above.
Supremum: least upper bound.
If is the supremum of and , is the maximum of .
A number is a lower bound of if for any , . We say that is bounded from below.
Infimum: greatest lower bound.
If is the infimum of and , is the minimum of .
Let and let be an upper bound of . is the supremum of iff:
- is the maximum of or
- for every there is an element of such that is less than that element
Least upper bound property (aka completeness property): Every non-empty subset of the real numbers that is bounded from above has a least upper bound that is a real number.
Bounded and nested intervals §
Archimedian property: For every real number , there exists a natural number such that .
Successor axiom: If , exists and is a natural number.
A family of sets indexed by the natural numbers is nested iff .
Nested intervals property: If is a nested family of non-empty, closed, bounded intervals in , then is non-empty.
Bounded Infinite sets have cluster points §
Neighbourhoods: Given and , the -neigbourhood is the open interval .
A real number ix a cluster point  of a set if contains a non- element of for all .
Cluster points of a set need not be elements of the set.
Bolsano-Weierstrass Theorem: Every bounded, infinite set of real numbers has a cluster point.
Given sets and , a function from to is denoted , and it is a relation between and such that every has exactly one such that .
is the domain and is the co-domain of .
iff they have the same domain and for all in their domain.
Let , and . The restriction of to is the function defined by .
Let be a function. Given , the image of under is the subset given by .
Open sets §
A set is open if for every , there exists such that .
The intersection of any finite family of open sets is open.
Closed sets §
A set is closed if contains all of its cluster points.
If a set has no cluster points, it is closed.
- the union of open sets is open
- the intersection of finitely many open sets is open
- the intersection of closed sets is closed
- the union of finitely many closed sets is closed
is continuous if and only if for every in the domain: for every , there exists such that for all , if , then .
A function is continuous if for every open set in the codomain of , its pre-image is also open.
a sequence is a function .
a sequence converges to a real number if for every -neighbourhood of , the sequence eventually remains in the -neighbourhood.
a sequence can have at most one limit.
Squeeze theorem: if , , and , then .
- for any constant
A real number is a cluster point of a set of real numbers iff there exists a sequence of elements of , all different from , that converges to .
A set is closed iff for an arbitrary convergent sequence in , the limit is an element of .
A sequence is monotone if it is either weakly increasing, or weakly decreasing.
Every bounded, monotone sequence of real numbers converges.
Given a sequence , a subsequence is a sequence defined by for some choice of natural numbers .
Bolzano-Weierstrass Theorem: Every bounded sequence of real numbers has a convergent subsequence.
A sequence is a cauchy sequence if the terms of the sequence are “eventually” close to each other.
A sequence of real numbers is convergent if and only if it is a Cauchy sequence.
A set is disconnected if there exist sets such that:
- and are open in
Given , if is continuous, then the image of any connected set is continuous.
Extreme value theorem: Suppose is continuous. Then has a maximum and a minimum.
A set is compact if it is closed and bounded.
Given , if is continuous, then the image of every compact set is compact.
Covering property (aka Heine-Borel theorem)" is closed and bounded if and only if every open cover of has a finite subcover.
from above and from below ↩︎
aka “accumulation point” or “limit point” ↩︎