Def, lemma, and prop from Foundations of Mathematics
Archimedes' Condition
Given a positive real number$ \varepsilon, there exists a positive integer n such that
$ \frac{1}{10^n} \lt \varepsilon .
Lemma 2.1
If m/n and r/s are rational, with r/s is not 0, then m/n + (r/2)*sqrt(2) is irrational.
$ \frac{m}{n} \in \mathbb{Q} \land \frac{r}{s} \in \mathbb{Q} \land \frac{r}{s} \neq 0 \rightarrow \frac{m}{n} + (\frac{r}{s})\sqrt2 \notin \mathbb{Q}
Proposition 2.2
Between any two distinct rational numbers, there exists an irrational number.
Proposition 2.3
Between any two distinct irrational numbers, there exists a rational number.
Proposition 2.6 - Triangle Inequality
If x and y are real numbers, then
$ |x + y| \leq |x| + |y|
Definition 2.7 Limit
A sequence$ (a_n)of real numbers tends to a limit l if, given any $ \varepsilon \gt 0 , there is a natural number N such that
$ |a_n - l| \lt \varepsilonfor all $ n \gt N.
To say 'the sequence$ (a_n)tends to the limit l', we write
$ \lim_{n \to \infty} a_n = l,
or
$ a_n \rightarrow las$ n \rightarrow \infty
Definition 2.9 Convergent
A sequence$ (a_n)which tends to a limit l is called convergent. If no limit exists, it is said to be divergent.
Definition 2.10 Increasing sequence
A sequence$ (a_n) is increasing if each $ a_n\leq a_{n+1}, so that
$ a_1 \leq a_2 \leq a_3 \leq \ldots
Definition 2.11 Bounded sequence
If there exists a real number k such that $ \forall n \in \mathbb{N} (a_n \lt k), we say that $ (a_n)is bounded above.
Definition 2.12
A sequence$ (a_n) is decreasing if$ a_n\geq a_{n+1}for all n.
If it satisfies$ a_n \geq k for all n, then k is a lower bound and the sequence is bounded below.
Definition 2.14
The value of an infinite decimal $ a_0.a_1 a_2 a_3 ...a_n... is the limit l of the sequence (dn) of decimals to n decimal places , where $ d_n = a_0.a_1 a_2...a_n.
Definition 2.15
A non-empty subset$ S \subseteq Ris bounded above by$ k \in Rif$ \forall s\in S(s \le k). The number k is called an upper bound for S.
Definition 2.16
A subset$ S\subseteq Rhas a least upper bound$ \lambda \in \mathbb{R} if
1. $ \lambda is an upper bound for S,
2. if$ k \in \mathbb{R} is any other upper bound for S, then $ \lambda \le k.
Definition 2.18
A subset S is bounded below if there exists$ k\in \mathbb{R}with$ \forall s\in S (k\le s), and k is then called a lower bound. The number$ \mu \in \mathbb{R}is a greatest lower bound for S if
1. $ \muis a lower bound for S,
2. if k is another lower bound for S, then $ \mu \le k.
Definition 3.1
A predicate is a sentence involving a symbol x so that when we substitute an element$ a \in Yfor x, the resultant statement is clearly either true or false. We say that the predicate is valid for the set Y if every element $ a \in Y is either true or false.
Proposition 3.3
Let A and B be sets. Then,
$ A = B \leftrightarrow A \subseteq B \land B \subseteq A.
Proposition 3.4
Let A, B, and C be sets.
$ A \subseteq B \land B \subseteq C \rightarrow A \subseteq C
Definition 3.5
A set is empty if it has no member.
Definition 3.6
The union of two sets A and B is
$ A \cup B = \{x\mid x\in A \lor x\in B \}.
Definition 3.7
The intersection of two sets A and B is
$ A \cap B = \{x\mid x\in A \land x\in B \}.
Proposition 3.8
$ A \cup \emptyset = A
$ A \cup A = A
$ A \cup B = B \cup A
$ (A \cup B) \cup C = A \cup (B \cup C)
Proposition 3.9
$ A \cap \emptyset = \emptyset
$ A \cap A = A
$ A \cap B = B \cap A
$ (A \cap B) \cap C = A \cap (B \cap C)
Proposition 3.10
$ A \cup (B \cap C) = (A\cup B)\cap (A \cup C)
$ A \cap (B \cup C) = (A\cap B)\cup (A \cap C)
Proposition 3.11
If A and B are sets, the following are equivalent:
$ A \subseteq B
$ A \cap B = A
$ A \cup B = B
Definition 3.12
The set-theoretic difference is
$ A \setminus B = \{x\in A \mid x\notin B \}.
If B is a subset of A, then we call$ A\setminus Bthe complement of B relative to A.
Definition 3.13
Having agreed upon U, we define the complement$ B^{c}of every subset B of U by
$ B^{c} = U \setminus B.
Proposition 3.14
If A and B are subsets of the universal set U, then
$ \emptyset^{c} = U
$ U^c = \emptyset
$ (A^c)^{c} = A
$ A \subseteq B \rightarrow B^{c} \subseteq A^{c}
Proposition 3.15
If A and B are subsets of the universal set U, then
$ (A \cup B)^c = A^c \cap B^c
$ (A \cap B)^c = A^c \cup B^c
Theorem 3.16 De Morgan Duality Principle
If in any valid set-theoretic identity involving only the operations$ \capand$ \cupthe operations$ \capand$ \cupare interchanged throughout, the result is another valid identity.
The ordered pair property
(x, y) = (u, v) if and only if x = u and y = v.
Definition4.1(Kuratowski)
The ordered pair (x,y) of two elements x, y is defined to be the set
$ (x, y) = \{ \{ x \}, \{ x, y \} \} .
This expresses how we get the ordered pair by first selecting x and then select y.
Proposition 4.4
$ (A \cup B) \times C = (A \times C) \cup (B \times C)
$ (A \cap B) \times C = (A \times C) \cap (B \times C)
$ A \times (B \cup C) = (A \times B) \cup (A \times C)
$ A \times (B \cap C) = (A \times B) \cap (A \times C)
Proposition 4.5
For all sets A, B, C, D,
$ (A \times B) \cap (C \times D) = (A \cap C) \times (B \cap D)
Definition 4.6
Let A and B be sets. A relation between A and B is a subset R of$ A \times B.
Definition 4.7
A relation R on a set X is an equivalence relation if it has the following properties:
For $ x,y,z \in X
1. $ \forall x \in X (xRx) R is reflexive,
2. $ \forall x \in X \forall y \in X (xRy \rightarrow yRx) R is symmetric,
3. $ \forall x \in X \forall y \in X \forall z \in X (xRy \land yRz \rightarrow xRz) R is transitive.
Definition 4.8
A partition of a set X is a set P whose members are non-empty subsets of X, subject to the following conditions
1. $ \forall x \in X \exists Y \in P (x \in Y) \Leftrightarrow \cup P = X
2. $ \forall X \in P \forall Y \in P( X \neq Y \rightarrow X \cap Y = \emptyset)
Definition
Given an equivalence relation R on X, we define the equivalence class (with respect to R) of$ x\in Xto be the set
$ E_x = \{y\in X \mid x R y \} .
Definition 4.12
A relation R on a set A is a weak order if
1. $ aRb \land bRc \rightarrow aRc
2. $ aRb \lor bRa
3. $ aRb \land bRa \rightarrow a = b.
Proposition 4.16
A strict order S on a set A satisfies:
1. $ aSb \land bSc \rightarrow aSc
2. Given $ a, b \in A, then precisely one of the following hold (and not the other two):
$ aSb, bSa, a = b.
Definition 5.2
We call A the domain of f and B the codomain. We write
$ f: A \rightarrow B
to mean f is a function with domain A and codomain B.
Definition 5.3
Let A and B be sets. A function$ f: A \rightarrow Bis a subset f of$ A \times Bsuch that
$ \forall x \in A \exist ! y (x, y)\in f.
A function is also called a map or mapping.
Definition 5.6
If $ f: A \rightarrow Bis a function, then the image of f is the subset of B such that
$ f(A) = \{ f(x) \mid x\in A \}.
Another common notation is im(f).
It needs not to be the whole codomain.
Definition 5.7
A function $ f: A \rightarrow Bis a surjection (to B) or is onto B if
$ \forall b \in B \exists a \in A (f(a) = b).
Definition 5.8
A function $ f: A \rightarrow Bis an injection or one-to-one if
$ \forall x \in A \forall y \in A(f(x) = f(y) \rightarrow x = y).
Definition 5.11
A function$ f: A \rightarrow Bis a bijection if it is both an injection and a surjection (to B).
Definition 5.12
The identity function$ i_A : A \rightarrow Ais defined by
$ \forall a\in A (i_A(a) = a).
It is obviously a bijection.
Definition 5.13
If$ f: A \rightarrow Band$ g: C \rightarrow Dare functions and$ f(A) \subseteq C,
the composition$ g \circ fis the function
$ g \circ f: A \rightarrow D
for which
$ g\circ f (x) = g(f(x)).
Proposition 5.14
Let $ f:A\rightarrow B, g:C\rightarrow D, h:E\rightarrow Fbe functions such that the image of f is a subset of C and the image of g is a subset of E. Then the two functions
$ h \circ (g \circ f): A\rightarrow F
$ (h \circ g) \circ f: A\rightarrow F
are equal.
Proposition 5.15
If $ f:A\rightarrow Bis a function, then
$ f \circ i_A = f, \ \ i_B \circ f = f.
Definition 5.16
Let$ f: A\rightarrow Bbe a function. Then a function$ g:B\rightarrow Ais called a
left inverse for f if $ \forall x\in A (g(f(x)) = x),
right inverse for f if $ \forall y\in B (f(g(y)) = y),
inverse for f if it is both a left and right inverse for f.
In equivalent terms,
left inverse if $ g\circ f = i_A,
right inverse if $ f\circ g = i_B,
inverse if $ g\circ f = i_Aand$ f\circ g = i_B.
Theorem 5.17
A function $ f:A\rightarrow Bhas a:
left inverse if and only if it is injective
right inverse if and only if it is surjective
inverse if and only if it is bijective.