We can use congruence mod k to create a new "modular" number system. To keep this simple, we'll use a fixed base k=7.
\([n]_k\) is the set of all numbers congruent to n mod k, called a "congruence class". We'll drop the k subscript since we're just using k=7.
Examples:
[2] = {2, 9, -5, 16, -12, ...}
[4] = {4, 11, -3, 18, -10, ...}
[9] = {2, 9, -5, 16, -12, ...}
[2] = [9] = [-12]
Any element of a congruence class can be chosen as a "representative" to name the class. Analogy: "Brandon's house" and "Marcus's house" might be two names for the same house, if both Brandon and Marcus live there.
Each congruence class will be a single modular numer in our new number system. Our number system (called \(\mathbb{Z}_7\)) contains seven numbers
\(\mathbb{Z}_7 = \{[0],[1],[2],[3],[4],[5],[6]\}\)
When doing extended computation, people often drop the square brackets. We'll keep them for now as a reminder that these aren't normal integers.
To add or multiply modular numbers, you add or multiply the numbers inside the square brackets.
$[4] + [5] = [9]$
$[4] \times [3] = [12]$
\([6]^2 = [36]\)
It's usually convenient to normalize modular numbers to use small representatives:
$[4] + [5] = [9] = [2]$
$[4] \times [3] = [12] = [5]$
\([6]^2 = [36] = [1]\)
A useful way to think about modular numbers is that they wrap around like hours on a clock or (if you've seen them) unsigned integers in C/C++.
Normalizing to use small representatives lets us easily do complex computations like
$([4] \times [3])^2 = [12]^2 = [5]^2 = [25] = [4]$
$[3]^5 = [3]^{3+2} = [3]^3 \times [3]^2 = [27] \times [9] = [-1] \times [2] = [-2] = [5]$
Corner cases with set operations:
You can think of the empty set as like $\{\}$ but it's not written that way in math.
A set is a real layer of structure, like a box. So the two sets below are different. The first one is a box containing another box which contains two numbers.
When is the empty set a member of another set? Answer: only when it's explicitly in there.
Is the empty set a subset of $\{3, 4, 5\} $?
Definition: $A$ is a subset of $B$ if every element of $A$ is also an element of $B$.
Using this definition, \(\emptyset \subseteq \{3,4,5\}\) if and only if
For every \(x\), if \(x\in \emptyset\), then \(x \in \{3,4,5\}\)
The hypothesis \(x \in \emptyset\) is never true. So the if/then statement is true because of the strange truth table for if/then. So
Notice the difference in symbols: \(\subseteq\) is subset inclusion, \(\in\) is membership.
\(A = \{(x,y) \in \mathbb{R}^2 \ \mid \ x = y^2\}\)
The separator (| or :) divides this into two parts.
So A contains pairs of real numbers, but only ones whose second coordinate is the square of the first coordinate.
Another way to define the same set:
\(A = \{(x,y) \ \mid \ x \in \mathbb{R}, y \in \mathbb{R}, \text{ and } x = y^2\}\)
Problem:
$A = \{ (a, 5-(a-3)^2) \ \mid\ a \in \mathbb{R},\ 1 \leq a \leq 5\}$
$ B = \{ (x,y) \ \mid\ x,y \in \mathbb{R}, \ x \geq 0, \ y \geq 0\}$
Prove that $A \subseteq B$.
Proof:
Let $m$ be an arbitrary element of $A$.
By the definition of set $A$, we know that $m = (p, 5-(p-3)^2)$ where $1 \leq p \leq 5$ and $p$ is a real number. Let's call the second coordinate $q$. Then $q = 5-(p-3)^2)$ and $q$ is obviously also a real number.
To show $m$ is also an element of $B$, we need to show $p \geq 0$ and $5-(p-3)^2 \geq 0$.
Since $p \geq 1$, we already know $p \geq 0$.
Then, since $1 \leq p \leq 5$, subtracting $3$ from all sides of the inequality, $-2 \leq p-3 \leq 2$.
Since $|p-3| \leq 2$, we know $(p-3)^2 \leq 4$. Then $5-(p-3)^2 \geq 1 \geq 0$. So $q = 5-(p-3)^2 \geq 0$.
Since $p \geq 0$ and $q\geq 0$, $m = (p,q)$ is an element of $B$.
Since we have proven that any arbitrary element of $A$ is also an element of $B$, we have shown that $A \subseteq B$.
Prove the following claim using proof by contrapositive.
For any sets $A$ and $B$, if $(A-B) \cup (B-A) = A \cup B$, then $A \cap B = \emptyset$.
Hint: try drawing a Venn diagram to help understand why the claim is true.
Proof
To prove the claim, we will prove the contrapositive. That is, we'll prove thatFor any sets $A$ and $B$, if $A \cap B \neq \emptyset$, then $(A-B)\cup(B-A) \neq A \cup B$.Let $A$ and $B$ be sets and suppose that $A \cap B \neq \emptyset$
Since $A \cap B$ isn't empty, we can pick an arbitrary element $x$ in $A \cap B$.
Since $x \in A \cap B$, $x \in A$ and $x \in B$. And, also, $x \in A \cup B$.
Now let's look at the two set differences mentioned in the claim. Since $x\in B$, $x \notin (A-B)$ by the definition of set difference. Similarly, since $x \in A$, $x \notin (B-A)$.
Since $x \notin (A-B)$ and $x \notin (B-A)$, $x \notin (A-B)\cup(B-A)$.
We know that $x \in A \cup B$ but we also know that $x \notin (A-B)\cup(B-A)$. So those two sets cannot be equal. That is, $(A-B) \cup (B-A) \neq A \cup B$, which is what we needed to prove.
Consider the following sets.
$A = \{ (a,b) \in \mathbb{Z}^2 \mid b \geq a \}$
$B = \{ (x,y) \in \mathbb{Z}^2 \mid x \not = 0 \ \textrm{and} \ y = x^{x^2-x} \}$
What is the relationship between $A$ and $B$? Are they equal? Is one a subset of the other?
$A$ cannot be a subset of $B$. A contains some pairs that can't possibly be in $B$. For example, $(1,3)$ is in $A$. But it can't be in $B$ since 1 raised to any power is 1.
It seems likely that $B$ is a subset of $A$, since that exponentiation sure looks like it will produce a bigger number, at least if $x$ is positive.
Hypothesis: $B$ is a proper subset of $A$, i.e. $B \subseteq A$ and $B \neq A$.
Let $(x,y)$ be an element of $B$. Then $x,y \in \mathbb{Z}$, $x \not = 0$, and $y=x^{x^2-x}$.
There are three cases:
Case 1: $x=1$: Then $x^2 -x = 0$. So $y=x^{x^2-x} = x^0 = 1$, which is greater than or equal to $x$.
Case 2: $x > 1$: Since x is an integer this is equivalent to $x \geq 2$. Then $x^2 - x = x(x-1) \ge 2\cdot 1 = 2$. So $y=x^{x^2-x} \ge x^2$. And $x^2 > x$ because $x$ is a positive integer. So $y \ge x$.
Case 3: $x < 0$: Consider the exponent $x^2-x = x(x-1)$. Since $x$ is an integer, $x(x-1)$ must be an even integer. Anything raised to an even power is non-negative. So $y=x^{x^2-x}$ is non-negative and therefore greater than $x$ (which is negative).
In all three cases, $y \ge x$. So $(x,y) \in A$.