Definitions from How to Prove it
1.3.4 Truth set 1
The truth set of a statement $ P(x) is the set of all values of$ xthat make the statement $ P(x)true. In other words, it is the set defined by using the statement $ P(x) as an elementhood test:
Truth set of$ P(x) = \{ x \mid P(x) \}
1.4.1 Intersection, union, and difference
Intersection: $ A \cap B = \{ x \mid x \in A \land x \in B \}
Union: $ A \cup B = \{ x \mid x \in A \lor x \in B \}
Difference: $ A \setminus B = \{ x \mid x \in A \land x \notin B \}
1.4.5 Subset and disjoint
Subset: $ A \subseteq B \Leftrightarrow \forall x ( x \in A \rightarrow x \in B)
Disjoint: $ A \cap B = \emptyset \Leftrightarrow \lnot \exists x (x \in A \land x \in B)
2.3.2 Power set
The power set of A is the set whose elements are all the subsets of A. $ \emptyset is always an element of the power set.
$ \mathcal{P} (A) = \{ x \mid x \subseteq A \}
2.3.5 Intersection and union of a family of sets
$ \cap\mathcal{F} = \{ x \mid \forall A \in \mathcal{F}(x \in A) \} = \{ x \mid \forall A (A \in \mathcal{F} \rightarrow x \in A) \}
$ \cup\mathcal{F} = \{x\mid\exists A\in\mathcal{F}(x\in A)\} = \{x\mid\exists A(A\in\mathcal{F}\land x\in A) \}
Some mathematicians consider $ \cap\mathcal{F} to be undefined if $ \mathcal{F} = \emptyset.
In case of an indexed family,
$ \cap\mathcal{F} = \cap_{i\in I}A_i = \{x\mid\forall i\in I(x\in A_i) \}
$ \cup\mathcal{F} = \cup_{i\in I}A_i = \{x\mid\exist i\in I(x\in A_i) \}
4.1.1 Cartesian product
$ A \times B = \{(a, b) \mid a \in A \land b \in B \}
The Cartesian product of A and B, denoted A × B, is the set of all ordered pairs in which the first coordinate is an element of A and the second is an element of B.
4.1.5 Truth set 2
The truth set of a statement $ P(x, y)is the subset of $ A \times Bconsisting of those assignments that make the statement come out true, that is, truth set of$ P(x, y) = \{(a, b) \in A \times B \mid P(a, b) \}
4.2.1 Relation
Suppose A and B are sets. Then a set $ R \subseteq A \times Bis called a relation from A to B. It does't mention any truth set. Any subet of $ A \times B is called a relation from A to B.
4.2.3 Domain, range, inverse, and composition
Suppose R is a relation from A to B, and S is a relation from B to C.
The domain of R is the set
$ Dom(R) = \{a\in A\mid \exist b \in B ( (a, b) \in R ) \}.
The range of R is the set
$ Ran(R) = \{b\in B\mid \exist a \in A ( (a, b) \in R ) \}.
The inverse of R is the set
$ R^{-1} = \{(b, a)\in B \times A \mid (a, b) \in R \}.
The composition of S and R is the relation from A to C
$ S \circ R = \{(a, c) \in A \times C \mid \exist b \in B ( (a, b) \in R \land (b, c) \in S )\}.
4.3.2 Reflexive, symmetric, and transitive
Suppose R is a relation on A.
R is said to be reflexive if $ \forall x \in A (xRx), in other words, $ \forall x\in A ((x, x) \in R)
R is reflexive iff $ i_A \subseteq R where $ i_Ais the identity relation(=) on A.
R is symmetric if $ \forall x \in A \forall y \in A(xRy \rightarrow yRx)
R is symmetric iff $ R = R^{-1}
R is transitive if $ \forall x\in A \forall y\in A \forall z\in Z((xRy \land yRz) \rightarrow xRz)
R is transitive iff $ R \circ R \subseteq R
4.4.1 Antisymmetric
Suppose R is a relation on a set A. Then R is said to be antisymmetric if
$ \forall x \in A \forall y \in A ( (xRy \land yRx) \rightarrow x = y )
4.4.2 Partial order and total order
Suppose R is a relation on A. Then R is called a partial order on A if it is reflexive, transitive, and antisymmetric. It is called a total order on A if it is a partial order, and in addition it has the following property,
$ \forall x \in A \forall y \in A (xRy \lor yRx)
, where we can compare any two objects in a total order with a relation.
4.4.4 Smallest and minimal
Suppose R is a partial order on a set A, $ B \subseteq A, and $ b \in B.
Then b is called an R-smallest element of B if $ \forall x \in B (bRx).
It is called an R-minimal element if $ \lnot \exist x \in B (xRb \land x \neq b).
4.4.8 Lower bound
Suppose R is a partial order on a set A, $ B \subseteq A, and $ a \in A.
Then a is called a lower bound for B if
$ \forall x \in B (aRx)
Note that a lower bound for B need not be an element of B. That is the only difference between lower bounds and smallest elements. The largest element in lower bounds is called the greatest lower bound.
Similarly, it is an upper bound for B if
$ \forall x \in B (xRa)
4.4.9 Least upper bound and greatest lower bound
Suppose R is a partial order on a set A, $ B \subseteq A. Let U be the set of all upper bounds for B, and let L be the set of all lower bounds for B.
The smallest element in U is the least upper bound (l.u.b.)
The largest element in L is the greatest lower bound (g.l.b.)
4.5.1 Reflexive closure
Suppose R is a relation on a set A. Then reflexive closure of R is the smallest set $ S \subseteq A \times Asuch that $ R \subseteq Sand S is reflexive. In other words, a relation $ S \subseteq A \times A is the reflexive closure of R if it has the following three properties:
1. $ R \subseteq S
2. S is reflexive
3. $ \forall T \subseteq A \times A (R \subseteq T \land T\,is\,reflexive \rightarrow S \subseteq T)]
In other words, the reflexive closure of R is R plus reflexive relation pairs, and nothing more.
4.5.3 Strict partial order and strict total order
Suppose R is a relation on A. Then R is said to be irreflexive if $ \forall x \in A ((x, x) \notin R). R is called a strict partial order if it is irreflexive and transitive. It is called a strict total order if it is a strict partial order with the following property: $ \forall x\in A \forall y\in A(xRy \lor yRx \lor x = y).
** a strict partial order is actually not partial order since it is not reflexive!
4.5.4 Symmetric closure and transitive closure
Suppose R is a relation on A. The symmetric closure of R is the smallest set $ S\subseteq A \times Asuch that $ R \subseteq Sand S is symmetric. In other words, a relation $ S\subseteq A \times Ais the symmetric closure of R if it has the following three properties:
1. $ R \subseteq S
2. S is symmetric
3. $ \forall T \subseteq A\times A (R \subseteq T \land T \,is \,symmetric \rightarrow S \subseteq T)
Similarly, a relation $ S\subseteq A \times Ais the transitive closure of R if it has the following three properties:
1. $ R \subseteq S
2. S is transitive
3. $ \forall T \subseteq A\times A (R \subseteq T \land T \,is \,transitive \rightarrow S \subseteq T)
4.6.1 Equivalence Relations
Suppose R is a relation on A. Then R is called an equivalence relation on A if it is reflexive, symmetric, and transitive.
4.6.2 Partition
Suppose A is a set and $ \mathcal{F} \subseteq \mathcal{P}(A).
$ \mathcal{F}is pariwise disjoint if $ \forall X \in \mathcal{F} \forall Y \in \mathcal{F}(X \neq Y \rightarrow X \cap Y = \emptyset).
$ \mathcal{F}is called a partition of A if it has the following properties:
1. $ \cup \mathcal{F} = A.
2. $ \mathcal{F}is pairwise disjoint.
3. $ \forall X \in \mathcal{F}(X \neq \emptyset)
4.6.3 Equivalence class
Suppose R is an equivalence relation on a set A, and $ x \in A.
Then the equivalence class of x with respect to R is the set
$ [x]_R = \{ y \in A \mid yRx \} .
The set of all equivalence classes of elements of A is called A modulo R, and is denoted $ A / R.
$ A / R = \{ [x]_R \mid x \in A \} = \{ X \subseteq A \mid \exist x \in A (X = [x]_R) \}
Lemma 4.6.5
Suppose R is an equivalence relation on A. Then:
1. $ \forall x \in A (x \in [x]) .
2. $ \forall x \in A \forall y \in A (y \in [x] \leftrightarrow [y] = [x] )
Theorem 4.6.4
Suppose R is an equivalence relation on a set A. Then $ A / Ris a partition on A.
Theorem 4.6.6
Suppose A is a set and $ \mathcal{F} is a partition of A. Then there is an equivalence relation R on A such that $ A / R = \mathcal{F}
Lemma 4.6.7
Suppose A is a set and $ \mathcal{F}is a partition of A.
Let $ R = \cup_{X \in \mathcal{F}} (X \times X) .
Then R is an equivalence relation on A and is called the equivalence relation determined by $ \mathcal{F}.
5.1.1 Function
Suppose F is a relation from A to B. Then F is called a function from A to B if for every a in A there is exactly one b in B such that (a, b) in F. In other words,
$ \forall a \in A \exists !b \in B ((a, b) \in F)
To indicate F, we write $ F: A \rightarrow B.
5.2.1 One-to-one and Onto
Suppose $ f: A \rightarrow B. We will say that f is one-to-one if
$ \lnot \exist a_1\in A\exist a_2\in A( f(a_1) = f(a_2) \land a_1 \neq a_2)
$ \leftrightarrow \forall a_1\in A \forall a_2\in A (f(a_1) = f(a_2) \rightarrow a_1 = a_2) .
One-to-one functions are called injections.
We say that f is onto if
$ \forall b\in B \exist a\in A(f(a) = b) .
Onto functions are called surjections.
Functions that are both one-to-one and onto are called one-to-one correspondences or bijections.
Theorem 5.3.4 Inverse function
Suppose $ f: A \rightarrow B. The the following statements are equivalent.
1. f is both one-to-one and onto.
2. $ f^{-1}:B \rightarrow A
3. There is a function$ g:A\rightarrow Bsuch that $ g \circ f = i_A \land f \circ g = i_B.
5.4.1 Image
Suppose $ f:A\rightarrow B,$ X \subseteq Aand $ Y \subseteq B.
The image of X under f is the set f(X) defined as followed:
$ f(X) = \{ f(x)\mid x \in X \}
$ = \{ b \in B \mid \exists x \in X (f(x) = b ) \}
The inverse image of Y under f is defined as followed:
$ f^{-1}(Y) = \{ a\in A \mid f(a) \in Y \}.