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 for Test 2. The test is in class on Friday May 31, 2024.
Homework assignment 6 (due Thursday June 6, 2024).
The set of positive integers \(\mathbb{Z}^{+}\) is countably infinite.
The set of integers \(\mathbb{Z}\) is countably infinite and is a proper superset of \(\mathbb{Z}^{+}\). In fact, the set difference \[\mathbb{Z} \setminus \mathbb{Z}^{+} = \{ x \in \mathbb{Z} \mid x \notin \mathbb{Z}^+\} = \{ x \in \mathbb{Z} \mid x \leq 0 \}\] is countably infinite.
The set of rationals \(\mathbb{Q} = \left\{ \frac{p}{q} \mid p \in \mathbb{Z} \text{ and } q \in \mathbb{Z} \text{ and } q \neq 0 \right\}\) is countably infinite.
The set of real numbers \(\mathbb{R}\) is uncountable. In fact, the closed interval \(\{x \in \mathbb{R} ~|~ 0 \leq x \leq 1\}\), any other nonempty closed interval of real numbers whose endpoints are unequal, as well as the related intervals that exclude one or both of the endpoints are each uncountable. The set of irrational numbers \(\overline{\mathbb{Q}} = \mathbb{R} - \mathbb{Q} = \{ x \in \mathbb{R} \mid x \notin \mathbb{Q} \}\) is uncountable.
We can classify any set as
Finite size. Fact: For each positive number \(n\), for any sets \(X\) and \(Y\) each size \(n\), there is a bijection between \(X\) and \(Y\).
Countably Infinite. Fact: for any countably infinite sets \(X\) and \(Y\), there is a bijection between \(X\) and \(Y\).
Uncountable. Examples: \(\mathcal{P}(\mathbb{N})\), the power set of any infinite set, the set of real numbers, any nonempty interval of real numbers. Fact: there are (many) examples of uncountable sets that do not have a bijection between them.
Definition: When \(A\) and \(B\) are sets, we say any subset of \(A \times B\) is a binary relation. A relation \(R\) can also be represented as
A function \(f_{TF} : A \times B \to \{T, F\}\) where, for \(a \in A\) and \(b \in B\), \(f_{TF}(~(a,b)~) = \begin{cases} T \qquad&\text{when } (a,b) \in R \\ F \qquad&\text{when } (a,b) \notin R \end{cases}\)
A function \(f_{\mathcal{P}} : A \to \mathcal{P}(B)\) where, for \(a \in A\), \(f_{\mathcal{P}}( a ) = \{ b \in B ~|~ (a,b) \in R \}\)
When \(A\) is a set, we say any subset of \(A \times A\) is a (binary) relation on \(A\).
For relation \(R\) on a set \(A\), we can represent this relation as a graph: a collection of nodes (vertices) and edges (arrows). The nodes of the graph are the elements of \(A\) and there is an edge from \(a\) to \(b\) exactly when \((a,b) \in R\).
Example: For \(A = \mathcal{P}(\mathbb{R})\), we can define the relation \(EQ_{\mathbb{R}}\) on \(A\) as \[\{ (X_1, X_2 ) \in\mathcal{P}(\mathbb{R}) \times \mathcal{P}(\mathbb{R}) ~|~ |X_1| = |X_2| \}\]
Example: Let \(R_{(\textbf{mod } n)}\) be the set of all pairs of integers \((a, b)\) such that \((a \textbf{ mod } n = b \textbf{ mod } n)\). Then \(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)\).
\(R_{(\textbf{mod } n)}\) is a relation on the set \(\underline{\phantom{\mathbb{Z}}\hspace{20em}}\)
Some example elements of \(R_{(\textbf{mod } 4)}\) are:
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?
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.