# 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,

**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

- $(A \cup B)' = A' \cap B'$;
- $(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$

and

(3)**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)

- $x \thicksim y$ in $\mathbb{R}$ if $x \geq y$ fails to be symmetric
- $m \thicksim n$ in $\mathbb{Z}$ if $mn>0$ fails to be reflexive
- $x \thicksim y$ in $\mathbb{R}$ if $\mid x-y \mid \leg 4$ fails to be transitive
- $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

and

(5)In general $(f\circ g) \neq (g\circ f)$.