Clearly and unambiguously communicate computational ideas using appropriate formalism. Translate across levels of abstraction.
Defining important sets of numbers, e.g. set of integers, set of rational numbers
Classifying sets into: finite sets, countably infinite sets, uncountable sets
Defining functions, predicates, and binary relations using multiple representations
Determining whether a given binary relation is symmetric, antisymmetric, reflexive, and/or transitive
Determining whether a given binary relation is an equivalence relation and/or a partial order
Know, select and apply appropriate computing knowledge and problem-solving techniques. Reason about computation and systems. Use mathematical techniques to solve problems. Determine appropriate conceptual tools to apply to new situations. Know when tools do not apply and try different approaches. Critically analyze and evaluate candidate solutions.
Using the definitions of the div and mod operators on integers
Using divisibility and primality predicates
Applying the definition of congruence modulo n and modular arithmetic
Apply proof strategies, including direct proofs and proofs by contradiction, and determine whether a proposed argument is valid or not.
Using proofs as knowledge discovery tools to decide whether a statement is true or false
Review quiz based on Week 8 class material (due Monday)
Test 2 in the CBTF at your scheduled time! You will be required to show a physical photo identification in order to test. Electronic IDs and photos of IDs are not accepted. Additionally, you will only be allowed to bring your ID and a writing utensil into the testing room. You will have to store away all of your other belongings before entering the room. Please see the Triton Testing Center’s website for more details.
No class Friday of Week 9 in observance of UCSD holiday.
A relation \(R\) on a set \(A\) is called reflexive means \((a, a) \in R\) for every element \(a \in A\).
Informally, every element is related to itself.
Graphically, there are self-loops (edge from a node back to itself) at every node.
A relation \(R\) on a set \(A\) is called symmetric means \((b, a) \in R\) whenever \((a, b) \in R\), for all \(a, b \in A\).
Informally, order doesn’t matter for this relation.
Graphically, every edge has a paired “backwards” edge so we might as well drop the arrows and think of edges as undirected.
A relation \(R\) on a set \(A\) is called transitive means whenever \((a, b) \in R\) and \((b, c) \in R\), then \((a, c) \in R\), for all \(a, b, c \in A\).
Informally, chains of relations collapse.
Graphically, there’s a shortcut between any endpoints of a chain of edges.
A relation \(R\) on a set \(A\) is called antisymmetric means \(\forall a \in A ~\forall b \in A~\left(~\left( ~(a,b) \in R \land (b,a) \in R ~\right) \to a=b~\right)\)
Informally, the relation has directionality.
Graphically, can organize the nodes of the graph so that all non-self loop edges go up.
When the domain is \(\{ a,b,c,d,e,f,g,h\}\) define a relation that is not reflexive and is not symmetric and is not transitive.
When the domain is \(\{ a,b,c,d,e,f,g,h\}\) define a relation that is not reflexive but is symmetric and is transitive.
When the domain is \(\{ a,b,c,d,e,f,g,h\}\) define a relation that is symmetric and is antisymmetric.
Is the relation \(EQ_{\mathbb{R}}\) reflexive? symmetric? transitive? antisymmetric?
Is the relation \(R_{(\textbf{mod } 4)}\) reflexive? symmetric? transitive? antisymmetric?
A relation is an equivalence relation means it is reflexive, symmetric, and transitive.
Example: For \(A = \mathcal{P}(\mathbb{R})\), the relation \(EQ_{\mathbb{R}}\) defined on \(A\) as \[\{ (X_1, X_2 ) \in\mathcal{P}(\mathbb{R}) \times \mathcal{P}(\mathbb{R}) ~|~ |X_1| = |X_2| \}\] is an equivalence relation.
Example: For \(A = \mathbb{Z}\), for each positive integer \(n\), the relation \(R_{(\textbf{mod } n)}\) defined as the set of ordered pairs \((a, b)\) such that \((a \textbf{ mod } n = b \textbf{ mod } n)\) is an equivalence relation.
A relation is a partial ordering (or partial order) means it is reflexive, antisymmetric, and transitive. Summary: binary relations can be useful for organizing elements in a domain. Some binary relations have special properties that make them act like some familiar relations. Equivalence relations (reflexive, symmetric, transitive binary relations) “act like” equals. Partial orders (reflexive, antisymmetric, transitive binary relations) “act like” less than or equals to.
For a partial ordering, its Hasse diagram is a graph representing the relationship between elements in the ordering. The nodes (vertices) of the graph are the elements of the domain of the binary relation. The edges do not have arrow heads. The directionality of the partial order is indicated by the arrangements of the nodes. The nodes are arranged so that nodes connected to nodes above them by edges indicate that the relation holds between the lower node and the higher node. Moreover, the diagram omits self-loops and omits edges that are guaranteed by transitivity.
Draw the Hasse diagram of the partial order on the set \(\{a,b,c,d,e,f,g\}\) defined as \[\begin{align*} \{ &(a,a), (b,b), (c,c), (d,d), (e,e), (f,f), (g,g), \\ &(a,c), (a,d), (d,g), (a,g), (b,f), (b,e), (e,g), (b,g) \} \end{align*}\]
A partition of a set \(A\) is a set of non-empty, disjoint subsets \(A_1, A_2, \cdots, A_n\) such that \[A = \bigcup_{i=1}^{n} A_i = \{ x \mid \exists i (x \in A_i) \}\]
An equivalence class of an element \(a \in A\) with respect to an equivalence relation \(R\) on the set \(A\) is the set \[\{s \in A \mid (a, s) \in R \}\] We write \([a]_R\) for this set, which is the equivalence class of \(a\) with respect to \(R\).
Recall: We say \(a\) is congruent to \(b\) mod \(n\) means \((a, b) \in R_{(\textbf{mod } n)}\). A common notation is to write this as \(a \equiv b (\textbf{mod } n)\).
We can partition the set of integers using equivalence classes of \(R_{(\textbf{mod } 4)}\)
\[\begin{align*} [0]_{R_{(\textbf{mod } 4)}} &= \phantom{ \{ x \in \mathbb{Z} \mid x \equiv 0 ((\textbf{mod } 4)) \} = \{ x \in \mathbb{Z} \mid x \textbf{ mod } 4 = 0 \textbf{ mod } 4 = 0 \} = \{ 4c \mid c \in \mathbb{Z}\} }\\ [1]_{R_{(\textbf{mod } 4)}} &= \phantom{ \{ x \in \mathbb{Z} \mid x \equiv 1 ((\textbf{mod } 4)) \} = \{ x \in \mathbb{Z} \mid x \textbf{ mod } 4 = 1 \textbf{ mod } 4 = 1 \} = \{ 4c+1 \mid c \in \mathbb{Z}\} }\\ [2]_{R_{(\textbf{mod } 4)}} &= \phantom{ \{ x \in \mathbb{Z} \mid x \equiv 2 ((\textbf{mod } 4)) \} = \{ x \in \mathbb{Z} \mid x \textbf{ mod } 4 = 2 \textbf{ mod } 4 = 0 \} = \{ 4c+2 \mid c \in \mathbb{Z}\} }\\ [3]_{R_{(\textbf{mod } 4)}} &= \phantom{ \{ x \in \mathbb{Z} \mid x \equiv 3 ((\textbf{mod } 4)) \} = \{ x \in \mathbb{Z} \mid x \textbf{ mod } 4 = 3 \textbf{ mod } 4 = 3 \} = \{ 4c+3 \mid c \in \mathbb{Z}\} }\\ [4]_{R_{(\textbf{mod } 4)}} &= \phantom{ \{ x \in \mathbb{Z} \mid x \equiv 4 ((\textbf{mod } 4)) \} = \{ x \in \mathbb{Z} \mid x \textbf{ mod } 4 = 4 \textbf{ mod } 4 = 0 \} = \{ 4c \mid c \in \mathbb{Z}\} }\\ [5]_{R_{(\textbf{mod } 4)}} &= \phantom{ \{ x \in \mathbb{Z} \mid x \equiv 5 ((\textbf{mod } 4)) \} = \{ x \in \mathbb{Z} \mid x \textbf{ mod } 4 = 5 \textbf{ mod } 4 = 1 \} = \{ 4c+1 \mid c \in \mathbb{Z}\} }\\ [-1]_{R_{(\textbf{mod } 4)}} &= \phantom{ \{ x \in \mathbb{Z} \mid x \equiv -1 ((\textbf{mod } 4)) \} = \{ x \in \mathbb{Z} \mid x \textbf{ mod } 4 = -1 \textbf{ mod } 4 = 3 \} = \{ 4c+3 \mid c \in \mathbb{Z}\} } \end{align*}\] \[\mathbb{Z} = [0]_{R_{(\textbf{mod } 4)}}~ \cup ~[1]_{R_{(\textbf{mod } 4)}} ~\cup~[2]_{R_{(\textbf{mod } 4)}}~\cup~ [3]_{R_{(\textbf{mod } 4)}}\]
Integers are useful because they can be used to encode other objects and have multiple representations. However, infinite sets are sometimes expensive to work with computationally. Reducing our attention to a partition of the integers based on congrunce mod \(n\), where each part is represented by a (not too large) integer gives a useful compromise where many algebraic properties of the integers are preserved, and we also get the benefits of a finite domain. Moreover, modular arithmetic is well-suited to model any cyclic behavior. Fact: When \(R\) is an equivalence relation on a nonempty set \(A\), the collection of equivalence classes of \(R\) is a partition of \(A\).
Also, given a partition \(P\) of \(A\), the relation \(R_P\) on \(A\) given by \[R_P = \{ (x,y) \in A \times A ~|~ \text{$x$ and $y$ are in the same part of the partition $P$}\}\] is an equivalence relation on \(A\).
Claim: For each \(a \in U\), \([a]_{E} \neq \emptyset\).
Proof: Towards a \(\underline{\phantom{\hspace{1.3in}}}\)
consider an arbitrary element \(a\) in
\(U\). We will work to show that \([a]_E \neq \emptyset\), namely that \(\exists x \in [a]_E\). By definition of
equivalence classes, we can rewrite this goal as \[\exists x \in U ~( ~(a,x) \in E~)\]
Towards a \(\underline{\phantom{\hspace{1.3in}}}\),
consider \(x = a\), an element of \(U\) by definition. By \(\underline{\phantom{\hspace{1.3in}}}\) of
\(E\), we know that \((a,a) \in E\) and thus the existential
quantification has been proved.
Claim: For each \(a \in U\), there is some \(b \in U\) such that \(a \in [b]_{E}\).
Towards a \(\underline{\phantom{\hspace{1.3in}}}\)
consider an arbitrary element \(a\) in
\(U\). By definition of equivalence
classes, we can rewrite the goal as \[\exists
b \in U ~( ~(b,a) \in E~)\] Towards a \(\underline{\phantom{\hspace{1.3in}}}\),
consider \(b = a\), an element of \(U\) by definition. By \(\underline{\phantom{\hspace{1.3in}}}\) of
\(E\), we know that \((a,a) \in E\) and thus the existential
quantification has been proved.
Claim: For each \(a,b \in U\) , \((~(a,b) \in E ~\to ~ [a]_{E} =
[b]_{E}~)\) and \((~(a,b) \notin E
~\to ~ [a]_{E} \cap[b]_{E} = \emptyset~)\)
Corollary: Given an equivalence relation \(E\) on set \(U\), \(\{ [x]_{E} \mid x \in U \}\) is a partition of \(U\).
Modular arithmetic:
Informally: can bring mod “inside" and do it first, for addition and for multiplication.
Claim: For \(a, b, c, d \in \mathbb{Z}\) and positive integer \(n\), if \(a \equiv b ~(\textbf{ mod } n)\) and \(c \equiv d ~(\textbf{ mod } n)\) then \(a+c \equiv b+d ~(\textbf{ mod } n)\) and \(ac \equiv bd ~(\textbf{ mod } n)\).
\(123456 \times 789012 \textbf{ mod } 1000 =\)
Smaller examples work too:
\((102 + 48) \textbf{ mod } 10 =\)
\((7 \cdot 10) \textbf{ mod } 5 =\)
Let’s consider exponentiation:
\((2^5) \textbf{ mod } 3 =\)
To prove the claim: the following lemma is useful.
Lemma: For \(a, b \in \mathbb{Z}\) and positive integer \(n\), \((a,b) \in R_{(\textbf{mod } n)}\) if and only if \(n | a-b\).
Proof:
Compute the last digit of \[(42)^{2026}\]
Extra Describe the pattern that helps you perform this computation and prove it using mathematical induction and/or modular arithmetic.