# Discrete Mathematics - Final

## Domains

Naturals $$\mathbb{N}$$
$$[1,2,3,\ldots,\infty)$$
Integers $$\mathbb{Z}$$
$$(-\infty,\ldots,-2,0,2,\ldots,\infty)$$
Rationals $$\mathbb{Q}$$
Fractions of integers $$\{ \frac{p}{q} \vert p \in Z \land q \in Z \land q \ne 0 \}$$
Reals $$\mathbb{R}$$
All real numbers

#### Proof by Cases

Should be on the exam

This is a proof which can be used a used as a part of another proof when proving implications. If we have an implication where the premise consists of disjunctions, we can apply the following:

\begin{align} (p_1 \lor p_2 \lor \ldots \lor p_n) \to q \\ (p_1 \to q) \land (p_2 \to q) \land \ldots \land (p_n \to q) \end{align}

This proof is very helpful when we want to prove that a condition is satisfiable for a group of elements.

We can also use proof by cases for absolute values. If we have $$|x| = y$$, we can say that $$x = y$$ or $$x = -y$$. This is because $$|x|$$ is the distance from $$x$$ to $$0$$.

• Example

Prove that if $$n$$ is not a multiple of 3, $$2n$$ is not a multiple of 3.

Solution
To define a value as not a multiple of 3, we have two formulas $$n = 3k + 1 \quad n = 3k + 2$$. We can reformulate the proposition by saying $$(n = 3k+1) \lor (n = 3k^\prime) \to \neg (2n = 3k^{\prime\prime})$$. We then have to show that both cases imply the consequence.

#### Equivalence Proof

As previously mentioned $$p \leftrightarrow q = p \equiv q$$, so if we want to prove some equivalence, we can use $$(p \to q) \land (q \to p)$$.

Should be on the exam

We could also prove this by seeing if the two propositions will be false/true for the same values of $$p$$ and $$q$$.

#### Existential Statements Proof

We have two strategies for this.

Constructive Proof
We show an example that verifies a predicate and apply existential generalization to prove the proposition.
Non Constructive Proof
We show that there exists an element which validates the predicate but we dont specify which one. This is most commonly proof by contradiction.

#### Universal Statements Proof

Proving
We show that a predicate holds for an arbitrary value and then apply universal generalization.
Counterexamples
To disprove a universal statement we need to find a counterexample. This action is a process of negation, making the US an ES.

#### Strategy for Proofs

So should you use? It comes down to trial and error, but also practice and intuition.

Trial and error
If direct proof doesnt work, try indirect lol.
Complex propositions
If there are complex propositions in an implication, they quite possibly can be negated, allowing use to use an indirect method.
Using proof by contradiction with conditional statements
We show that $$\neg (p \to q)$$ implies $$\bot$$.

## Proofs Practice Problems

1. Prove that if $$n$$ is an integer, then $$n^2$$ is an integer.

To prove this we need to show that $$p \to q$$ is true. We can assume that $$p$$ is true and then show that $$q$$ is also true. We can do this by applying the laws of inference. We can say that $$n^2 = (n+1)(n-1)$$, which is an integer. This is enough to prove that $$p \to q$$ is true.

2. Prove that if $$n$$ is an integer, then $$n^2$$ is even.

This is not true. It is not necessary for $$n^2$$ to be even. We can show this by taking $$n = 3$$. This would mean that $$n^2 = 9$$ which is odd.

3. Define (using truth tables) the disjunction, conjunction, exclusive or, conditional, and biconditional of the propositions p and q:

Truth Table for Disjunction and Conjunction and Exclusive Or:

\begin{array} \hline p & q & p \lor q & p \land q & p \oplus q \\ \hline T & T & T & T & F \\ T & F & T & F & T \\ F & T & T & F & T \\ F & F & F & F & F \\ \hline \end{array}

Truth Table for Conditional and Biconditional:

\begin{array} \hline p & q & p \to q & p \leftrightarrow q \\ \hline T & T & T & T \\ T & F & F & F \\ F & T & T & F \\ F & F & T & T \\ \hline \end{array}
4. Give a direct proof, a proof by contraposition, and a proof by contradiction of the statement: “If n is even, then n + 4 is even.”
Direct Proof
Let n = an even integer. Then, n = 2k for some integer k. Since n + 4 = 2k + 4, n + 4 is also even. Thus, if n is even, then n + 4 is also even.
Proof by Contraposition
Let n + 4 = an odd integer. Then, n + 4 = 2j + 1 for some integer j. Since n = 2j - 3, n is also odd. Thus, if n + 4 is odd, then n is also odd.
Assume that n is even but n + 4 is odd. Then, n = 2k for some integer k, but n + 4 = 2j + 1 for some integer j. Since 2k = 2j + 1, k = j + 1/2. Since j and k are integers, this is a contradiction. Thus, if n is even, then n + 4 is also even.
1. Explain how a proof by cases can be used to prove a result about absolute values, such as the fact that |xy| = |x||y| for all real numbers x and y

A proof by cases can be used to prove a result about absolute values by breaking the statement into cases and proving each case separately. In the case of |xy| = |x||y|, the statement is broken into two cases: x and y are both positive, and x and y are both negative. For the first case, it can be shown that |xy| = xy, and |x||y| = xy, which proves the statement. For the second case, it can be shown that |xy| = -xy, and |x||y| = -xy, which also proves the statement. Together, these two cases prove that |xy| = |x||y| for all real numbers x and y.

### Problems from the Book

• Show that each of the following conditional statements is a tautology using the fact that a conditional is false exactly when the hypothesis is true and the conclusion is false. (pg 38 Ex140
1. $$(\neg p \land (p \lor q)) \to q$$

Solution: If we use the laws of inference we will get that $$\neg p \land q \to q$$. If we try to make this false, we will should consider the case where the premise is true, for the $$p$$ is false and $$q$$ is true. This will make the conclusion false, which is not possible. Therefore, the statement is a tautology.

2. $$((p\to q) \land (q\to r)) \to (p \to r)$$

Solution: It is pretty easy to see that this is the hypothetical syllogism. We can use the laws of inference to show that $$(p\to q) \land (q\to r)$$ is equal to $$p \to r$$. Now we just need to show that this is a tautology. We can do this by considering the case where the premise is true, and since the premise and conclusion are the same, we can conclude that the statement is a tautology.

3. $$(p \land (p \to q)) \to q$$

Solution: We transform the statement into $$(p \land q) \to q$$. We can see that this is a tautology by considering the case where the premise is true. For the premise to be true, the conclusion also has to be true. This makes the case of the implication being false not possible, which means that the statement is a tautology.

4. $$((p\lor q) \land (p \to r) \land (q \to r)) \to r$$

Solution: By simplifying the premise we get that $$\top \lor r \to r$$.

• Show that each of the following conditional statements is a tautology using the chain of logical identities. (Pg 38 Ex 16)
1. $$(\neg p \land (p \lor q)) \to q$$

Solution:

\begin{align} (\neg p \land (p \lor q)) \to q \\ \neg p \land p \lor \neg p \land q \to q \\ \bot \lor \neg p \land q \to q \\ \neg ( \neg p \land q ) \lor q \\ p \lor \neg q \lor q p \lor \top \\ \top \end{align}
2. $$((p\to q) \land (q\to r)) \to (p \to r)$$

Solution:

\begin{align} ((p\to q) \land (q\to r)) \to (p \to r) \\ (\neg p \lor q \land \neg q \lor r) \to (\neg p \lor r) \\ \neg p \lor \bot \lor r \to \neg p \lor r \\ \neg ( \neg p \lor r ) \lor \neg p \lor r \\ p \lor \neg r \lor \neg p \lor r \\ (p \lor \neg p) \lor (r \lor \neg r) \\ \top \lor \top \\ \top \end{align}
3. $$(p \land (p \to q)) \to q$$

Solution:

\begin{align} (p \land (p \to q)) \to q \\ (p \land (\neg p \lor q)) \to q \\ (p \land \neg p \lor p \land q) \to q \\ (\bot \lor p \land q) \to q \\ \neg (p \land q) \lor q \\ p \lor \neg q \lor q \\ p \lor \top \ \top \end{align}
4. $$((p\lor q) \land (p \to r) \land (q \to r)) \to r$$

Solution:

\begin{align} ((p\lor q) \land (p \to r) \land (q \to r)) \to r \\ \neg((p \lor q) \land (\neg p \lor r) \land (\neg q \lor r)) \lor r \\ \neg p \land \neg q \lor p \land \neg r \lor (q \land \neg r) \lor r \\ (\neg p \land \neg q) \lor (p \land \neg r) \lor (q \lor r) \land (\neg r \lor r) \\ (\neg p \land \neg q) \lor (p \land \neg r) \lor (q \lor r) \land \top \\ q \lor (\neg p \land \neg q) \lor r \lor (p \land \neg r) \\ q \lor \neg p \land q \lor \neg q \lor r \lor p \land r \lor \neg r \\ q \lor \neg p \land \top \lor r \lor p \land \top \\ q \lor \neg p \lor r \lor p \\ q \lor r \lor \top \\ \top \end{align}
• Express the negation of the propositions using quantifiers:
1. $$\forall x(x > 1)$$

Solution: $$\exists x(x \leq 1)$$

2. $$\forall x ((x < -1) \lor (x > 2))$$

Solution: $$\exists x (( x \ge -1) \land (x \le 2))$$

• Determine whether $$\forall x (P(x) \to Q(x))$$ is equivalent to $$\forall x P(x) \to \forall x Q(x)$$. (pg 59 ex 45) Solution:

\begin{align} \forall x (P(x) \to Q(x)) \equiv \forall x P(x) \to \forall x Q(x) \\ \neg \exists x (P(x) \to Q(x)) \lor \exists x P(x) \to \exists x Q(x) \\ \neg \exists x (P(x) \to Q(x)) \lor \neg \exists x P(x) \lor \exists x Q(x) \\ \neg \exists x (P(x) \to Q(x)) \lor \neg \exists x P(x) \lor \neg \exists x Q(x) \end{align}
• Use rules of inference to show that the hypotheses “If it does not rain or if it is not foggy, then the sailing race will be held and the lifesaving demonstration will go on,” “If the sailing race is held, then the trophy will be awarded,” and “The trophy was not awarded” imply the conclusion “It rained.”

First we identify the premises:

• $$p =$$ it rained
• $$q =$$ it was foggy
• $$r =$$ the race was held
• $$s =$$ the lifesaving demonstration went on
• $$t =$$ the trophy was awarded
\begin{align} \neg p \lor \neg q \to r \land s \\ r \to t \\ \neg t \neg r \quad \text{from 2nd and 3rd (modus tollens)} \\ (\neg r \land s) \quad \text{from 1st and 4th} \\ \neg (\neg p \lor \neg q) \\ p \land q \\ p \quad \text{it rained} \end{align}
• Find the argument form for the following argument and determine whether it is valid. Can we conclude that the conclusion is true if the premises are true?
\begin{array}{r} \text{If George does not have eight legs, then he is not a spider.} \\ \text{George is a spider} \\ \hline \text{George has eight legs.} \end{array}

Solution: The form of the argument is Modus Tollens, which is valid.

• What rules of inference are used in this famous argument? “All men are mortal. Socrates is a man. Therefore, Socrates is mortal.”

Solution:

\begin{array}{r} \forall x (M(x) \to Mo(x)) \\ M(S) \\ \hline Mo(S) \end{array}

Here we make us of universal instantiation and them modus ponens.

• Use a direct proof to show that every odd integer is the difference of two squares. Solution:

\begin{align} n = 2k + 1 \\ n = (k+1)^2 - k^2 \\ n = k^2 + 2k + 1 - k^2 \\ n = 2k + 1 \end{align}

## Set Theory

### Sets

A set is a collection of objects. We use the notation $$\{a,b,c\}$$ to denote a set. We can also use the notation $$\{x \in S \mid P(x)\}$$ to denote a set of elements $$x$$ in $$S$$ that satisfy the predicate $$P(x)$$. A set can be empty, which is denoted by $$\emptyset$$.

A more concrete definition of a set using quantifiers is as follows:

$\forall x (( x \in S) \leftrightarrow P(x))$

We also often use interval definitions to define sets. These are defined as follows:

$\{x \in \mathbb{R} \mid a \leq x \leq b\}$

A common way to define a interval is with brackets and parenthesis. For example, $$(a,b)$$ is an open interval, while $$[a,b]$$ is a closed interval.

Two sets are equal if they have the same elements. We denote this as $$A = B$$. A more rigorous definition of this is as follows:

$A = B \equiv \forall x (x \in A \leftrightarrow x \in B)$

The equality of two sets can also be defined using subsets:

$A = B \equiv A \subseteq B \land B \subseteq A$

Should be on the exam

A way to disprove the equality of two sets is by showing that they have at least one element that is not in the other set. This is called a counterexample. It can be represented with an existential quantifier and XOR: $$\exists x (x \in A \oplus x \in B)$$.

Some important elements are the aforementioned empty set $$\emptyset$$ and the universal set $$\mathbb{U}$$. The universal set is the set of all elements in a domain. The empty set is the set that contains no elements. The Domains, mentioned at the beginning are also sets.

### Subsets

A subset is a set that is contained in another set. We denote this as $$A \subseteq B$$. A more rigorous definition of this is as follows:

$A \subseteq B \equiv \forall x (x \in A \to x \in B)$

For all sets, it is true that $$A \subseteq A$$ and $$\emptyset \subseteq A$$. Which means that every set is a subset of itself and the empty set is a subset of every set. We can also say that $$A \subseteq B$$ and $$B \subseteq A$$ implies $$A = B$$. This is called the subset equality.

Should be on the exam

What can be confusing is the proper subset. A proper subset is a subset that is not equal to the set. We denote this as $$A \subset B$$. A more rigorous definition of this is as follows:

$A \subset B \equiv A \subseteq B \land A \neq B$

A quantified version of this is as follows:

$\forall x ((x \in A) \to (x \in B) \land (A \neq B))$

### Set Cardinality

This is not the absolute value of a set. It is the number of elements in a set. We denote this as $$|A|$$. A more rigorous definition of this is as follows:

$\vert A \vert \equiv \# \{x \in A \mid x \in A\}$

### Power Set

The power set is the set of all subsets of a set. We denote this as $$P(A)$$. What is meant by all subsets is that the power set contains the empty set and the universal set aswell as all the subsets of the set. A more rigorous definition of this is as follows:

$P(A) \equiv \{B \mid B \subseteq A\}$

Should be on the exam

The cardinality of a power set is $$2^{|A|}$$.

An example of this is the power set of $$\{1,2,3\}$$ is $$\{\emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\}$$.

What is important to remember is that the power set of a power set is the original set. This is because the power set of a set is the set of all subsets of a set. So the power set of the power set is the set of all subsets of all subsets of a set. This is the original set.

### Cartesian Product

The cartesian product is the set of all ordered pairs of elements from two sets. We denote this as $$A \times B$$. In other words, the cartesian product is the set of all possible combinations of elements from two sets. A more rigorous definition of this is as follows:

$A \times B \equiv \{(a,b) \mid a \in A \land b \in B\}$

Should be on the exam

The cardinality of the cartesian product is $$|A| \times |B|$$.

An example of this is the cartesian product of $$\{1,2\}$$ and $$\{3,4\}$$ is $$\{(1,3), (1,4), (2,3), (2,4)\}$$.

The relation of the Cartesian product to the power set is that the power set of a cartesian product is the cartesian product of the power sets. This is because the power set of a set is the set of all subsets of a set. So the power set of the cartesian product is the set of all subsets of all ordered pairs of elements from two sets. This is the cartesian product of the power sets. A mathematical proof of this is as follows:

$P(A \times B) = \{C \mid C \subseteq A \times B\} = \{C \mid C \subseteq \{(a,b) \mid a \in A \land b \in B\}\} = \{C \mid C \subseteq \{(a,b) \mid a \in P(A) \land b \in P(B)\}\} = P(A) \times P(B)$

Or simply: $$P(A \times B) = P(A) \times P(B)$$.

### Set Operations

Set operations are operations that can be performed on sets. The most common set operations are union, intersection, difference, and complement.

Should be on the exam

It is important to remember that if we have an expression like $$A \subsete A \cup B$$, something that could be tricky is that the order of operations is not the same as in arithmetic. In arithmetic, we would do the multiplication and division first, then addition and subtraction. In set operations, we do the complement first, then the difference, then the intersection, and finally the union. So the expression $$A \subsete A \cup B$$ would be read as $$A \subsete (A \cup B)$$.

Once again, the order of operations for sets is:

1. Complement
2. Difference
3. Intersection
4. Union

### Union

Simply explained, the union of two sets is the set of all elements that are in either set. We denote this as $$A \cup B$$. A more rigorous definition of this is as follows:

$A \cup B \equiv \{x \mid x \in A \lor x \in B\}$

And using quantifiers:

$\forall ((x \in A \cup B) \equiv (x \in A \lor x \in B))$

Should be on the exam

The cardinality of the union is $$|A| + |B| - |A \cap B|$$. The reason why we have to subtract the cardinality of the intersection is because the intersection is counted twice. Once in $$A$$ and once in $$B$$.

An example of this is the union of $$\{1,2\}$$ and $$\{2,3\}$$ is $$\{1,2,3\}$$. The reason why this is the union is because $$1 \in A$$, $$2 \in A$$, $$2 \in B$$, and $$3 \in B$$. So $$1,2,3$$ are all in the union.

### Intersection

The intersection of two sets is the set of all elements that are in both sets. We denote this as $$A \cap B$$. A more rigorous definition of this is as follows:

$A \cap B \equiv \{x \mid x \in A \land x \in B\}$

The cardinality of the intersection is $$|A \cap B|$$. What is important to remember is that the intersection of a set with itself is the set itself. This is because the intersection of a set with itself is the set of all elements that are in the set and the set itself. So the intersection of a set with itself is the set itself.

An example of this is the intersection of $$\{1,2\}$$ and $$\{2,3\}$$ is $$\{2\}$$. The reason why this is the intersection is because $$2 \in A$$ and $$2 \in B$$. So $$2$$ is in the intersection.

### Difference

The difference of two sets is the set of all elements that are in the first set but not the second set. We denote this as $$A \setminus B$$. A more rigorous definition of this is as follows:

$A \setminus B \equiv \{x \mid x \in A \land x \notin B\}$

A visual representation of this is as follows: The cardinality of the difference is $$|A \setminus B|$$ or $$|A| - |A \cap B|$$. The reason why we have to subtract the cardinality of the intersection is because the intersection is counted twice. Once in $$A$$ and once in $$B$$.

An example of this is the difference of $$\{1,2\}$$ and $$\{2,3\}$$ is $$\{1\}$$. The reason why this is the difference is because $$1 \in A$$ and $$1 \notin B$$. So $$1$$ is in the difference.

### Complement

The complement of a set is the set of all elements that are not in the set. We denote this as $$A^c$$. A more rigorous definition of this is as follows:

$A^c \equiv \{x \mid x \notin A\}$

In terms of the universal set, the complement of a set is the set of all elements that are not in the set and are in the universal set. It is denoted as $$A^c = U \setminus A$$. A more rigorous definition of this is as follows:

$A^c \equiv \{x \mid x \in U \land x \notin A\}$

The cardinality of the complement is $$|U| - |A|$$. The reason why we have to subtract the cardinality of the set is because the set is counted twice. Once in $$U$$ and once in $$A$$.

An example of this is the complement of $$\{1,2\}$$ is $$\{3,4\}$$. The reason why this is the complement is because $$3 \in U$$ and $$3 \notin A$$. So $$3$$ is in the complement. This of course depends on the universal set being $$\{1,2,3,4\}$$.

### Logical Operations with Sets

We can relate sets to logical operations. The most common logical operations are conjunction, disjunction, and negation. We can relate these to sets as follows:

\begin{array}{l} A \cup B \sim p \lor q \\ A \cap B \sim p \land q \\ \bar{A} \sim \neg p \end{array}

The reason why we can do this is that the definition of a set, is based on a predicate. So we can relate the set to the predicate and the predicate to the logical operation. For example, the definition of a set is as follows:

$A \equiv \{x \mid x \in A\}$

So we can relate the set to the predicate as follows:

$A \equiv \{x \mid x \in A\} \equiv \{x \mid p(x)\}$

## Functions

A function, is the assignment of a single value $$b\in B$$ to each element $$a$$ in a set $$A$$. We denote this as $$f: A \rightarrow B$$. We can also call a function a mapping, transformation or a black box (in some cases even an oracle). A more rigorous definition of this is as follows:

$f: A \rightarrow B \equiv \{f(a) \mid a \in A\}$

We are mostly interested in what makes a function a function. So we will define what makes a function a function. A function is a function if the following conditions are met:

1. The domain of the function is a set
2. The range of the function is a set
3. The function is one-to-one
4. The function is onto

A mathematical way to express this is as follows:

$\forall a \in A \exists ! b \in B \land f(a) = b$

The reasons why some assignments might not be functions is that not all elements in $$A$$ are assigned to an element in $$B$$. This is called a partial function. Another reason why some assignments might not be functions is that not all elements in $$B$$ are assigned to an element in $$A$$. This is called a surjection. Another reason why some assignments might not be functions is that not all elements in $$A$$ are assigned to a unique element in $$B$$. This is called a bijection.

How can we tell if a function is a function? We can tell if a function is a function by checking if the function is one-to-one and onto. If the function is one-to-one and onto, then the function is a function. If the function is not one-to-one and onto, then the function is not a function.

### Domain, Codomain & Range

If $$f(a) = b$$, then we call $$a$$ the pre-image and $$b$$ the image of $$f$$. We call $$A$$ the domain of $$f$$ and $$B$$ the codomain of $$f$$. We call $$f(A)$$ the range of $$f$$.

The main difference between the codomain and the range is that the codomain is the set of all possible images of $$f$$ and the range is the set of all images of $$f$$.

### One-to-One

A function is one-to-one if each element in the range is assigned to a unique element in the domain. We denote this as $$f: A \rightarrow B$$ is one-to-one. A more rigorous definition of this is as follows:

$f: A \rightarrow B \text{ is one-to-one } \equiv \forall a_1, a_2 \in A \land f(a_1) = f(a_2) \implies a_1 = a_2$

or simply: $$f(a_1) = f(a_2) \implies a_1 = a_2$$.

Should be on the exam

If we want to check if a functions is one-to-one, we have to test if $$f(a_1) = f(a_2) \implies a_1 = a_2$$ for all $$a_1, a_2 \in A$$. If this is true for all $$a_1, a_2 \in A$$, then the function is one-to-one.

### Onto

A function is onto if each element in the codomain is assigned to an element in the domain. We denote this as $$f: A \rightarrow B$$ is onto. This is to say that for each element in the codomain, there is an element in the domain that maps to it. A more rigorous definition of this is as follows:

$f: A \rightarrow B \text{ is onto } \equiv \forall b \in B \exists a \in A \land f(a) = b$

or simply: $$\forall b \in B \exists a \in A \land f(a) = b$$.

Should be on the exam

To see if a function is onto, we have to test if $$\forall b \in B \exists a \in A \land f(a) = b$$. If this is true for all $$b \in B$$, then the function is onto. For example if $$f: \{1,2\} \rightarrow \{1,2,3\}$$, then $$f(1) = 1$$, $$f(2) = 2$$ and $$f(3) = 3$$. So $$f$$ is onto. If $$f: \{1,2\} \rightarrow \{1,2\}$$, then $$f(1) = 1$$, $$f(2) = 2$$ and $$f(3) = 3$$. So $$f$$ is not onto. In this case, the function is not onto because $$3$$ is not assigned to an element in the domain.

### Composite Functions

We can combine functions to create composite functions. We can combine functions by applying one function to the output of another function. We denote this as $$f \circ g$$. We can also call this function composition. A more rigorous definition of this is as follows:

$f \circ g \equiv \{f(g(a)) \mid a \in A\}$

Should be on the exam

If the codomain of $$g$$ is the domain of $$f$$, then we can combine $$g$$ and $$f$$ to create a composite function. We denote this as $$f \circ g: A \rightarrow C$$.

When it comes to functions properties after composition we have the following properties:

1. $$f \circ g$$ is one-to-one if $$f$$ is one-to-one and $$g$$ is one-to-one
2. $$f \circ g$$ is onto if $$f$$ is onto and $$g$$ is onto

If some of the functions are not one-to-one or onto, then the composite function is not one-to-one or onto.

### Inverse Functions

An inverse function is a function that undoes the effects of another function. We denote this as $$f^{-1}$$. The definition is as follows:

$f^{-1} \equiv \{a \mid f(a) = b\}$

Should be on the exam

If $$f$$ is one-to-one and onto, then $$f^{-1}$$ is also one-to-one and onto.

### Partial Functions

A partial function is a function that is not one-to-one or onto. We denote this as $$f: A \rightarrow B$$ is a partial function. Definition:

$f: A \rightarrow B \text{ is a partial function } \equiv \exists a_1, a_2 \in A \land f(a_1) = f(a_2) \land a_1 \neq a_2$

or simply: $$\exists a_1, a_2 \in A \land f(a_1) = f(a_2) \land a_1 \neq a_2$$. If this is true for some $$a_1, a_2 \in A$$, then $$f$$ is a partial function.

### Practice Questions

1. Let $$f: \mathbb{R} \rightarrow \mathbb{R}$$ be defined by $$f(x) = x^2$$. Is $$f$$ one-to-one? Is $$f$$ onto? Is $$f$$ a partial function?
Solution
$$f$$ is one-to-one because $$f(x) = f(y) \implies x = y$$. $$f$$ is not onto because $$f(x) = x^2$$ and $$x^2$$ is not in the domain. $$f$$ is not a partial function because $$f(x) = f(y) \implies x = y$$.
2. Let $$f: \mathbb{R} \rightarrow \mathbb{R}$$ be defined by $$f(x) = x^2$$. Is $$f^{-1}$$ one-to-one? Is $$f^{-1}$$ onto? Is $$f^{-1}$$ a partial function?
Solution
$$f^{-1}$$ is one-to-one because $$f^{-1}(x) = f^{-1}(y) \implies x = y$$. $$f^{-1}$$ is onto because $$f^{-1}(x) = x^2$$ and $$x^2$$ is in the domain. $$f^{-1}$$ is not a partial function because $$f^{-1}(x) = f^{-1}(y) \implies x = y$$.
3. Let $$f: \mathbb{R} \rightarrow \mathbb{R}$$ be defined by $$f(x) = x^2$$. Is $$f \circ f$$ one-to-one? Is $$f \circ f$$ onto? Is $$f \circ f$$ a partial function?
Solution
$$f \circ f$$ is one-to-one because $$f$$ is one-to-one and $$f$$ is one-to-one. $$f \circ f$$ is onto because $$f$$ is onto and $$f$$ is onto. $$f \circ f$$ is not a partial function because $$f \circ f$$ is one-to-one and $$f \circ f$$ is onto.
4. Let $$f: \mathbb{R} \rightarrow \mathbb{R}$$ be defined by $$f(x) = x^2$$. Is $$f \circ f^{-1}$$ one-to-one? Is $$f \circ f^{-1}$$ onto? Is $$f \circ f^{-1}$$ a partial function?
Solution
$$f \circ f^{-1}$$ is one-to-one because $$f$$ is one-to-one and $$f^{-1}$$ is one-to-one. $$f \circ f^{-1}$$ is onto because $$f$$ is onto and $$f^{-1}$$ is onto. $$f \circ f^{-1}$$ is not a partial function because $$f \circ f^{-1}$$ is one-to-one and $$f \circ f^{-1}$$ is onto.

## Sequences

A sequence is a set of elements, which can be continued by using intuition or mathematical patterns. We denote this as $$\{a_n \mid n \in \mathbb{N}\}$$. We will mostly focus on arithmetic sequences and geometric sequences.

### Arithmetic Sequences

An arithmetic sequence is a sequence where the difference between two consecutive terms is constant. We denote this as $$\{a_n \mid n \in \mathbb{N}\}$$ where $$a_n = a_1 + (n-1)d$$ for some $$a_1, d \in \mathbb{R}$$. We can also write this as $$a_n = a_1 + nd$$, where $$n$$ is the nth term of the sequence and $$d$$ is the common difference.

An arithmetic sequence is defined by the following properties:

1. $$a_n = a_1 + (n-1)d$$
2. $$a_n = a_1 + nd$$

This sequence can also be thought of as a linear function. We can write this as $$a_n = f(n)$$ where $$f(n) = a_1 + (n-1)d$$. The main elements of a sequence are the first term and the common difference.

The expansion for the arithmetic sequence is as follows:

\begin{align} a_1 = a_1 + 0d &= a_1 \\ a_2 = a_1 + 1d &= a_1 + d \\ a_3 = a_1 + 2d &= a_1 + 2d \\ a_4 = a_1 + 3d &= a_1 + 3d \\ \vdots &= \vdots \\ a_n = a_1 + (n-1)d &= a_1 + (n-1)d \end{align}

### Geometric Sequences

A geometric sequence is a sequence where the ratio between two consecutive terms is constant. We denote this as $$\{a_n \mid n \in \mathbb{N}\}$$ where $$a_n = a_1 r^{n-1}$$ for some $$a_1, r \in \mathbb{R}$$. We can also write this as $$a_n = a_1 r^n$$, where $$n$$ is the nth term of the sequence and $$r$$ is the common ratio.

An expansion of such as sequence can look something like this:

\begin{align} a_1 &= a_1 \\ a_2 &= a_1 r \\ a_3 &= a_1 r^2 \\ a_4 &= a_1 r^3 \\ \vdots &= \vdots \\ a_n &= a_1 r^{n-1} \end{align}

### Recurrence Relations

A recurrence relation is a sequence that is defined by a formula. We denote this as $$\{a_n \mid n \in \mathbb{N}\}$$ where $$a_n = f(a_{n-1})$$ for some $$f: \mathbb{R} \rightarrow \mathbb{R}$$. It takes the previous term and applies a function to it to get the next term.

We can be told to find the closed formula for a sequence. This is a formula that can be used to find the nth term of a sequence.To do this, we need to use iteration and induction. We can use the following rules to find the closed formula for a sequence:

1. $$a_n = a_1 + (n-1)d$$ where $$a_1, d \in \mathbb{R}$$
2. $$a_n = a_1 r^{n-1}$$ where $$a_1, r \in \mathbb{R}$$
3. $$a_n = f(a_{n-1})$$ where $$f: \mathbb{R} \rightarrow \mathbb{R}$$
4. $$a_n = f(a_{n-1}, a_{n-2})$$ where $$f: \mathbb{R} \times \mathbb{R} \rightarrow \mathbb{R}$$

In short, we need to find the pattern in the sequence and use that to find the closed formula. A closed formula should be defined only in terms of $$n$$.

## Summations

A summation is a way to add up a sequence of numbers. We denote this as $$\sum_{i=1}^n a_i$$. There are many ways to define a summation. To find the sum of a sequence, we can use the following rules:

1. $$\sum_{i=1}^n i = \frac{n(n+1)}{2}$$
2. $$\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}$$
3. $$\sum_{i=1}^n i^3 = \frac{n^2(n+1)^2}{4}$$
4. $$\sum_{i=1}^n C * f(i) = \frac{C}{1-r}$$

If we subtract 1 from the upper bound, we can find the sum of the sequence. For example, $$\sum_{i=1}^n i = \sum_{i=0}^{n-1} i + n = \sum_{i=0}^{n-1} i + \sum_{i=n}^n i = \sum_{i=0}^{n-1} i + n = \frac{n(n-1)}{2} + n = \frac{n(n+1)}{2}$$.

If we have nested summations, we can expand the far-right summation and include it in each iteration of the left summation.

## Divisibility

A number is divisible by another number if the remainder is 0. We denote this as $$a \mid b$$ where $$a$$ is the divisor and $$b$$ is the dividend. We can also write this as $$a = q \cdot d + r$$ where $$r$$ is the remainder and $$q$$ is the quotient. It is important to note that $$r$$ is always less than $$d$$ and always positive.

The elements in the primary equation are as follows:

1. $$a$$ is the dividend
2. $$d$$ is the divisor
3. $$q$$ is the quotient
4. $$r$$ is the remainder

From this equation we gain two new operations, the division operation and the modulus operation. We can use these operations to find the remainder and quotient of a division problem.

Should be on the exam

If we perform division of a negative number, we cannot have a negative remainder. To solve this, we can add the divisor to the dividend until the remainder is positive. This is called the floor division operation. In other words, we want to 'overshoot' with the dividend and then compensate with the remainder.

• Division Function: This function is onto but not one-to-one
• Modulus Function: This function neither one-to-one or onto

### Divisibility Rules

We can use divisibility rules to determine if a number is divisible by another number. The rules are as follows:

1. If $$a$$ divides both $$b$$ and $$c$$, then $$a$$ divides $$b+c$$. Expression: $$a \mid b \land a \mid c \Rightarrow a \mid (b+c)$$
2. If $$a$$ divides $$b$$, then $$a$$ divides any multiple of $$b$$. Expression: $$a \mid b \implies a \mid bm$$ for some $$m \in \mathbb{N}$$
3. If $$a$$ divides $$b$$ and $$b$$ divides $$c$$, then $$a$$ divides $$c$$. Expression: $$a \mid b \land b \mid c \Rightarrow a \mid c$$

## Modular Arithmetic

Modular arithmetic uses the modulus operation to find the remainder of a division problem. We use the notation $$a \equiv b \pmod{m}$$ to denote that $$a$$ is congruent to $$b$$ modulo $$m$$.

Should be on the exam

If we want to identify if two integers are congruent modulo $$m$$, we can test this in the following way:

1. $$a \equiv b \pmod{m} \land b \equiv c \pmod{m} \Rightarrow a \equiv c \pmod{m}$$

In other words, if the remainder of the modulus operation is the same, then the two numbers are congruent modulo $$m$$.

### Rules of Modular Arithmetic

We can use the following rules to perform modular arithmetic:

1. $$a \equiv b \pmod{m} \land c \equiv d \pmod{m} \Rightarrow a+c \equiv b+d \pmod{m}$$
2. $$a \equiv b \pmod{m} \land c \equiv d \pmod{m} \Rightarrow ac \equiv bd \pmod{m}$$
3. $$a \equiv b \pmod{m} \land c \equiv d \pmod{m} \Rightarrow a-c \equiv b-d \pmod{m}$$
4. $$a \equiv b \pmod{m} \land c \equiv d \pmod{m} \Rightarrow a/c \equiv b/d \pmod{m}$$
5. $$a \equiv b \pmod{m} \land c \equiv d \pmod{m} \Rightarrow a^c \equiv b^d \pmod{m}$$
Should be on the exam

The difference between congruency and the modulo operation is that congruency is a relation between two numbers, while the modulo operation is an operation that returns a number. For example, $$a \equiv b \pmod{m}$$ is a relation between $$a$$ and $$b$$, while $$a \pmod{m}$$ is an operation that returns a number.

### Inverse of a Modulo

We can find the inverse of a modulo by using the following equation: $$a \cdot a^{-1} \equiv 1 \pmod{m}$$. In other words, if we multiply the inverse of a modulo by the modulo, we get 1 modulo $$m$$.

To find the inverse of a modulo, we can use the Extended Euclidean Algorithm. This algorithm is as follows:

1. Set $$a = m \cdot q + r$$ where $$q$$ is the quotient and $$r$$ is the remainder
2. Set $$b = a \cdot q + r$$ where $$q$$ is the quotient and $$r$$ is the remainder
3. Repeat step 2 until $$r = 0$$
4. The inverse of $$m$$ modulo $$a$$ is $$q$$ where $$q$$ is the quotient of the last step

For example, if we want to find the inverse of 3 modulo 7, we can use the Extended Euclidean Algorithm as follows:

1. $$7 = 3 \cdot 2 + 1$$
2. $$3 = 1 \cdot 3 + 0$$
3. $$r = 0$$ so we stop
4. The inverse of 3 modulo 7 is 3

### Practice Problems

1. $$2 \equiv 3 \pmod{5}$$

Solution: False, 2 is not congruent to 3 modulo 5

2. $$3 \equiv 4 \pmod{5}$$

Solution: False, 3 is not congruent to 4 modulo 5

3. $$4x \equiv 7 \pmod{5}$$

Solution: This is true when $$x = 0.5$$ because $$4(0.5) \equiv 7 \pmod{5}$$ is true.

4. $$x \equiv 3 \pmod{5} \land x \equiv 4 \pmod{5}$$

Solution: This is not true because $$3 \not\equiv 4 \pmod{5}$$ so $$x \not\equiv 3 \pmod{5} \land x \not\equiv 4 \pmod{5}$$

Practice problems using powers of modular arithmetic:

1. $$2^3 \equiv 8 \pmod{5}$$

Solution: This is true because $$2^3 = 8 \equiv 8 \pmod{5}$$

## Integer Representation

Integers can be represented in many ways. In every day life, we use the base 10 system. This means that we use the digits 0-9 to represent numbers. We can also use the base 2 system. This means that we use the digits 0-1 to represent numbers. We can also use the base 16 system. This means that we use the digits 0-9 and A-F to represent numbers. We can also use the base 26 system. This means that we use the digits A-Z to represent numbers.

If we want to convert the value of base $$b$$ to base $$b'$$, we can use the following formula:

$n = a_k b^k + a_{k-1} b^{k-1} + \cdots + a_1 b + a_0$

The general algorithm for calculating the number representation is as follows:

1. Divide the number by the base
2. Take the remainder and add it to the list of digits
3. Repeat until the number is 0

In mathematics:

\begin{align} n = a_0 + bq_0 \\ n = a_1 + b(a_1 + bq_1) \\ n = a_2 + b(a_1 + b(a_2 + bq_2)) \end{align}

## Binary Representation

Binary representation is the representation of numbers in base 2. We can use the following rules to convert from base 10 to base 2:

1. Divide the number by 2
2. Take the remainder and add it to the list of digits
3. Repeat until the number is 0

To then put together the binary string we take each bit in reverse order and put it together. For example, the binary representation of 13 is 1101.

To make life a bit easier, we can use a table to convert from base 10 to base 2. The table is made up of the powers of 2 and the digits 0-1.

27 26 25 24 23 22 21 20
128 64 32 16 8 4 2 1

Hexadecimal representation is the representation of numbers in base 16. We can use the following rules to convert from base 10 to base 16:

1. Divide the number by 16
2. Take the remainder and add it to the list of digits
3. Repeat until the number is 0

To then put together the hexadecimal string we take each digit in reverse order and put it together. For example, the hexadecimal representation of 15816 is 3DC8. The steps taken to get to this number are as follows:

1. 15816 / 16 = 988 remainder 8
2. 988 / 16 = 61 remainder 12 (12 is C in hexadecimal)
3. 61 / 16 = 3 remainder 13 (13 is represented as D in hexadecimal)
4. 3 / 16 = 0 remainder 3
5. 3DC8

## Prime Numbers

A prime number is a number that is only divisible by 1 and itself. We can use the following rules to determine if a number is prime:

1. If $$n$$ is divisible by $$a$$, then $$n$$ is not prime
2. If $$n$$ is not divisible by $$a$$, then $$n$$ is prime

Any number that is not prime is called a composite number. This relates to the Fundamental Theorem of Arithmetic. This theorem states that every integer greater than 1 can be expressed as a product of prime numbers. This theorem is important because it allows us to factorize numbers.

How to determine if a number is a prime or composite? We can use the following proposition:

$(n \text{ is composite}) \Leftrightarrow \exists a \in \mathbb{N} (( a \mid n) \land (a \neq 1) \land (a \neq n))$

## Algorithms

An algorithm is a collection of instructions that are made to solve a problem. To create any algorithm, we need three basic components:

Sequence
A sequence is a list of instructions that are executed in order
Selection
A selection is a list of instructions that are executed based on a condition
Iteration
An iteration is a list of instructions that are executed multiple times

### Complexity of Algorithms

The complexity of an algorithm is given by the relation between the input size and the number of steps required to solve the problem. We can use the following notations to describe the complexity of an algorithm:

$$O(n)$$
This notation describes the worst case scenario for an algorithm. This means that the algorithm will take at least this amount of time to solve the problem.
$$\Omega(n)$$
This notation describes the best case scenario for an algorithm. This means that the algorithm will take at most this amount of time to solve the problem.
$$\Theta(n)$$
This notation describes the average case scenario for an algorithm. This means that the algorithm will take this amount of time to solve the problem.

We will not need omega and theta notation for the exam, but it is good to know.

### Big O Notation

Big O notation is used to describe the worst case scenario for an algorithm. We can use the following rules to determine the complexity of an algorithm:

The idea of this notation is that we can use it to compare the complexity of different algorithms. For example, if we have two algorithms that solve the same problem, we can use big O notation to determine which algorithm is better. If one algorithm is $$O(n)$$ and the other is $$O(n^2)$$, then the first algorithm is better than the second algorithm.

Algorithm Complexity Example
$$O(1)$$ Constant Finding the first element in a list
$$O(\log n)$$ Logarithmic Binary search
$$O(n)$$ Linear Finding the maximum value in a list
$$O(n \log n)$$ Linearithmic Merge sort
$$O(n^2)$$ Quadratic Bubble sort
$$O(n^3)$$ Cubic Matrix multiplication
$$O(2^n)$$ Exponential Tower of Hanoi
$$O(n!)$$ Factorial Travelling salesman problem

Contrary to intuition, to solve a large problem you should always use the most efficient algorithm, but for a smaller size, higher complexity algorithms are better.

## Greatest Common Divisor

The greatest common divisor of two numbers is the largest number that divides both numbers. We can easily find this if we know the factorizations of each number. Another way to find the greatest common divisor is to use Euclid's algorithm. This algorithm is as follows:

1. Let $$a$$ be the larger number and $$b$$ be the smaller number
2. Divide $$a$$ by $$b$$ and take the remainder
3. If the remainder is 0, then $$b$$ is the greatest common divisor
4. If the remainder is not 0, then set $$a$$ to $$b$$ and $$b$$ to the remainder
5. Repeat until the remainder is 0

An example of this algorithm is as follows:

1. Let $$a = 24$$ and $$b = 16$$
2. $$24 \div 16 = 1$$ remainder $$8$$
3. $$16 \div 8 = 2$$ remainder $$0$$
4. $$b = 8$$ is the greatest common divisor

### Least Common Multiple

The least common multiple of two numbers is the smallest number that is divisible by both numbers. We can easily find this if we know the factorizations of each number. Another way to find the least common multiple is to use the following formula:

$\text{lcm}(a, b) = \frac{a \cdot b}{\text{gcd}(a, b)}$

## Applications of Number Theory

Number theory is used in many different fields. Some of these fields are as follows: cryptography, coding theory, and combinatorics.

### Databases

If we know the number of records in a database and who much space they take up, swell as the starting position, we can use the following formula to determine the position of the nth record:

$\text{position} = \text{starting position} + \text{record size} \cdot (n - 1)$

### Hash Functions

If we want to store some records into a database, we can use a hash function which will map each record to a unique location in the database. This is done by taking the record and applying a hash function to it. The hash function will then return a number which is the location of the record in the database. We might use the $$mod$$ operator to create a hash function.

If each entry has some numerical value we can use $$mod 10$$ to map it to a location in the database. This method is not very practical because we might get some sort of collision. A collision is when two records map to the same location in the database. To avoid collisions we can make use of a secondary hash function.

### Asymmetric Encryption

Asymmetric encryption is a method of encryption that uses two keys. One key is used to encrypt the message and the other key is used to decrypt the message. The two keys are called the public key and the private key. The public key is used to encrypt the message and the private key is used to decrypt the message. The public key is made public and the private key is kept secret.

## Relations

A relation is a set of ordered pairs. It is also a subset of the Cartesian product of the set. We can use the following notation to represent a relation:

$R = \{(x, y) \mid x \in A \land y \in B\}$

The easiest way to represent a relation is to use a table. The table will have the elements of the first set as the rows and the elements of the second set as the columns. If the ordered pair $$(x, y)$$ is in the relation, then we will put a $$1$$ in the cell that corresponds to the row $$x$$ and the column $$y$$. If the ordered pair $$(x, y)$$ is not in the relation, then we will put a $$0$$ in the cell that corresponds to the row $$x$$ and the column $$y$$.

Here is an example of a relation:

$R = \{(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)\}$

We can represent this relation as a table as follows:

\begin{array}{c|ccc} & 1 & 2 & 3 \\ \hline 1 & 0 & 1 & 1 \\ 2 & 1 & 0 & 1 \\ 3 & 1 & 1 & 0 \end{array}

The relationship between functions and relations is that a function is a relation where each ordered pair has a unique first element.

Should be on the exam

To find the cardinality of a relation for a single set, we can use the following formula:

$2^{n^2}$

This is because there are $$2$$ possibilities for each ordered pair. The ordered pair can either be in the relation or it can not be in the relation. If we have $$n$$ elements in the set, then there are $$n^2$$ ordered pairs. Therefore, there are $$2^{n^2}$$ possible relations.

This should also be equivalent to the power set of the Cartesian product of the set.

### Reflexive Relations

A relation is reflexive if it contains the ordered pair $$(x, x)$$ for every element $$x$$ in the set. We can use the following notation to represent a reflexive relation:

$R = \{(x, y) \mid x \in A \land y \in A \land x = y\}$

As a matrix, it would look like this:

\begin{array}{c|ccc} & 1 & 2 & 3 \\ \hline 1 & 1 & 0 & 0 \\ 2 & 0 & 1 & 0 \\ 3 & 0 & 0 & 1 \end{array}

### Symmetric Relations

A relation is symmetric if it contains the ordered pair $$(x, y)$$ for every ordered pair $$(y, x)$$. We can use the following notation to represent a symmetric relation:

$R = \{(x, y) \mid x \in A \land y \in A \land (y, x) \in R\}$

As a matrix, it would look like this (or any other symmetric relation):

\begin{array}{c|ccc} & 1 & 2 & 3 \\ \hline 1 & 0 & 1 & 1 \\ 2 & 1 & 1 & 1 \\ 3 & 1 & 1 & 0 \end{array}

### Antisymmetric Relations

If a relation is antisymmetric, it will it will contain some order pair $$(x,y)$$ but not $$(y,x)$$ for every ordered pair $$(x,y)$$. We can use the following notation to represent an antisymmetric relation:

$R = \{(x, y) \mid x \in A \land y \in A \land (x, y) \in R \land (y, x) \notin R\}$

### Transitive Relations

A relation is transitive if it contains the ordered pair $$(x, z)$$ for every ordered pair $$(x, y)$$ and $$(y, z)$$. We can use the following notation to represent a transitive relation:

$R = \{(x, z) \mid x \in A \land z \in A \land (x, y) \in R \land (y, z) \in R\}$

What its saying is that the relation will be transitive if for every $$n$$ steps, we can get from $$x$$ to $$z$$ in just one step.

### Composite Relations

We can combine two relations to create a composite relation. The composite relation will contain the ordered pair $$(x, z)$$ if the first relation contains the ordered pair $$(x, y)$$ and the second relation contains the ordered pair $$(y, z)$$. We can use the following notation to represent a composite relation:

$R \circ S = \{(x, z) \mid x \in A \land z \in A \land (x, y) \in R \land (y, z) \in S\}$

We can us powers of a binary relation to represent the composite relation. The $n$th power of a binary relation will contain the ordered pair $$(x, z)$$ if the relation contains the ordered pair $$(x, y)$$ and the relation contains the ordered pair $$(y, z)$$ $$n$$ times.

## Directed Graphs

If we want to represent a relation, we can use a directed graph. A directed graph is a graph where the edges have a direction. The edges can be represented by arrows. The arrows will point from the first element of the ordered pair to the second element of the ordered pair. If we have an ordered pair $$(x, y)$$ in the relation, then we will have an arrow from $$x$$ to $$y$$.

An example of a directed graph is the following: ## Grammars

A grammar is a set of rules that can be used to generate strings. The strings that are generated by the grammar are called the language of the grammar. The language of the grammar is the set of all strings that can be generated by the grammar. The language of the grammar is denoted by $$L(G)$$.

Vocabulary
This is a set of symbols which we use to represent the language of the grammar. The vocabulary of the grammar is denoted by $$V$$.
Grammar
This is a set of rules that can be used to generate strings. The grammar is denoted by $$G$$. It is a combination of the vocabulary. By using grammar and vocabulary, we can generate strings which are part of formal language.

An example of a railroad diagram is the following: We write the railroad diagram as follows (not the one above):

<expression> ::= <term> | <term> "+" <expression>
<term>       ::= <factor> | <factor> "*" <term>
<factor>     ::= <constant> | <variable> | "(" <expression> ")"
<variable>   ::= "x" | "y" | "z"
<constant>   ::= <digit> | <digit> <constant>
<digit>      ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"


more coming soon