chapter 0 summary

# definitions

A statement in logic or mathematics is an assertion that is either true or false.

Onto
If $f: A\to B$ Then the relation is said to be onto if the entire Range of the function is included by one or more values from the Domain. Meaning $f(A)= B$.

One to One
If $(x_1)\neq(x_2)$ Then $f(x_1)\neq f(x_2)$ as well. The opposite must hold true as well. If $x_1=x_2$ then $f(x_1)=f(x_2)$.

Cartesian Products and Mapping
Given sets $A$ and $B$, we can define a new set $A\times B$, called the Cartesian product of $A$ and $B$, as a set of ordered pairs. That is,

(1)
\begin{align} $A\times B = \lbrace(a,b): a\in A, b\in B\rbrace$ \end{align}

Divides
$a \mid b$$iff$\existsq$:$aq = b$Invertible A map is said to be invertible is it has an inverse. For example, the natural logarithm and the exponential function,$f(x)= \ln x$and$f^{-1}(x) = e^x$, are inverses of each other provided that we are careful about choosing domains. Equivalence Relation An equivalence relation on a set$X$is a a relation$R \subset X \times X$such that: •$(x,x) \in R$for all$x \in X$(Reflexive property) •$(x,y) \in R$implies$(y,x) \in R$(Symmetric property) •$(x,y)$and$(y,z) \in R$implies$(x,z) \in R$(Transitive property) Note: The book usually writes:$x \thicksim y$. Partition A partition$\mathcal{P}$of a set$X$is a collection of nonempty sets$X_1, X_2, \dots$such that$X_i \cap X_j = \emptyset$for$i\neq j$and$\bigcup_k X_k = X$. Let$\thicksim$be an equivalence relation on a set$X$and let$x \in X$. Then$[x] = \{x \in X : y \thicksim x\}$is called the equivalence class of$x$. An equivalence relation gives rise to a partition via equivalence classes. When a partition exists, there is some underlying equivalence relation. See Theorem 0.5. # theorems Standard Set Theory Theorem (Proposition 0.1) Let$A$,$B$and$C$be sets. Then 1.$A \cup A = A$,$A \cap A = A$and$A \setminus A = \emptyset$; 2.$A \cup \emptyset = A$and$A \cap \emptyset = \emptyset$; 3.$A \cup (B \cup C) = (A \cup B) \cup C$and$A \cap (B \cap C) = (A \cap B) \cap C$; 4.$A \cup B = B \cup A$and$A \cap B = B \cap A$; 5.$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$; 6.$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$. De Morgan's Law (Theorem 0.2) Let$A$and$B$be sets. Then 1.$(A \cup B)' = A' \cap B'$; 2.$(A \cap B)' = A' \cup B'$. Mapping Composition Theorem (Theorem 0.3) Let$f:A \rightarrow B, g: B\rightarrow C$, and$h: C \rightarrow D$. Then 1. The composition of mappings is associative; that is,$(h \circ g) \circ f = h \circ (g \circ f)$; 2. If$f$and$g$are both one - to - one, then the mapping$g \circ f$is one - to - one; 3. If$f$and$g$are both onto, then the mapping$g \circ f$is onto; 4. If$f$and$g$are bijective, then so is$g \circ f$. Invertible Mapping Theorem (Theorem 0.4) A mapping is invertible if and only if it is both one-to-one and onto. Equivalence Relation to Partitions Theorem (Theorem 0.5) Given an equivalence relation$\sim$on a set$X$, the equivalence classes of$X$form a partition of$X$. Conversely, if$\mathcal{P}= \{X_i \}$is a partition of a set$X$, then there is an equivalence relation on$X$with equivalence classes$X_i$. Disjoint or Equal Equivalence Classes Corollary (Corollary 0.6) Two equivalence classes of an equivalence relation are either disjoint or equal. # examples & notes Example for Cartesian Products and Mappings If$A = \lbrace x,y\rbrace$,$B= \lbrace1,2\rbrace$, and$C=\emptyset$, then$A\times B(2) \begin{align} \lbrace (x,1), (x,2), (y,1), (y,2)\rbrace \end{align} and (3) \begin{align} A\times C =\emptyset \end{align} GCD The greatest common divisor of integers a and b is a positive integer d such that d is a common divisor of a and b; and if the compliment of d is any other common divisor of a and b, then the compliment of d/d. (d compliment is a divisor of d…) Equivalence Relation Examples (ch.0, #25) 1.x \thicksim y$in$\mathbb{R}$if$x \geq y$fails to be symmetric 2.$m \thicksim n$in$\mathbb{Z}$if$mn>0$fails to be reflexive 3.$x \thicksim y$in$\mathbb{R}$if$\mid x-y \mid \leg 4$fails to be transitive 4.$m \thicksim n$in$\mathbb{Z}$if$m \equiv n (mod 6)$is an equvalence relation 24 B Let$f: X \rightarrow Y$be a map with$A_1, A_2 \subset X$and$B_1, B_2 \subset Y$. Prove$f(A_1 \intersect A_2) \subset f(A_1) \intersect f(A_2)$. Proof: Let$y \in f(A_1 \cap A_2).$Then$\exists x \in (A_1 \cap A_2)$, such that$f(x)=y$which means$x \in A_1$and$x \in A_2$. Since$x \in A_1$and$x \in A_2, y=f(x) \in f(A_1)$and$y=f(x) \in f(A_2)$. Then$y \in f(A_1) \cap f(A_2)$. Formal Definition of Modular Numbers Let$r$and$s \in \mathbb{Z}$and suppose that$n \in \mathbb{N}$. We can say that$r \equiv s$mod$n$if$r-s$is evenly divisible by$n$or$r-s=nk$for some$k \in \mathbb{Z}$. Example of Composition Let$f(x)= x^2$and$g(x)=2x+5. Then (4) \begin{align} (f \circ g)(x)=f(g(x))=(2x+5)^2=4x^2+20x+25 \end{align} and (5) \begin{align} (g\circ f)(x)=g(f(x))=2x^2+5. \end{align} In general(f\circ g) \neq (g\circ f)\$.

page revision: 33, last edited: 09 Mar 2010 12:06