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 $\exists$ $q$ : $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)$.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License