### Problem 1 Let $$F$$ be the set of functions from $$\mathbb{R}$$ to $$\mathbb{R}$$. Let $$R \subseteq F \times F$$ be the relation $$R = \{ (f,g) \mid f,g \in F \land \exists k \in \mathbb{R}(\forall x \in \mathbb{R}(f(x) = g(x) + k))\}$$ Prove that $$R$$ is symmetric. --- #### Scratchwork $$R = \{ (f,g) \mid f,g \in F \land \exists k \in \mathbb{R}(\forall x \in \mathbb{R}(f(x) = g(x) + k))\}$$ Symmetric: $$\forall f,g \in F$$, $$(fRg \rightarrow gRf)$$ Notation: $$fRg$$ means $$(f,g) \in R$$. We assume $$fRg$$, and try to prove that $$gRf$$. $$fRg$$ means there is some real number $$k$$ such that $$f(x) = g(x) + k$$ for all inputs $$x$$. We need to show $$gRf$$, which means there is some real number $$\ell$$ such that $$g(x) = f(x) + \ell$$ for all inputs $$x$$. We can substitute in the assumption $$f(x) = g(x) + k$$ to help us find the $$\ell$$ we're looking for: $$g(x) = (g(x) + k) + \ell$$. Simplifying $$\ell = -k$$. #### Proof Let $$f,g \in F$$ so that $$fRg$$. We aim to show that $$gRf$$. Since $$fRg$$, there exists some real number $$k$$ so that for all $$x \in \mathbb{R}$$, $$f(x) = g(x) + k$$. Then $$g(x) = f(x) + (-k)$$. So in fact, $$gRf$$, as desired. --- --- ### Problem 2 Let $$G$$ be a (directed) graph, and let $$W \subseteq V(G) \times V(G)$$ be the relation $$W = \{ (x,y) \mid x,y \in V(G) \text{ and there is a walk from $x$ to $y$} \}$$ Prove that $$W$$ is transitive. --- #### Scratchwork $$W = \{ (x,y) \mid x,y \in V(G) \text{ and there is a walk from $x$ to $y$} \}$$ Transitive: $$\forall x,y,z \in V(G)$$, $$(xWy \land yWz \rightarrow xWz)$$ We assume $$xWy$$ and $$yWz$$, and try to prove $$xWz$$. $$xWy$$ means there is a walk starting at $$x$$ and ending at $$y$$. $$yWz$$ means there is a walk starting at $$y$$ and ending at $$z$$. We need to show that there is a walk starting at $$x$$ and ending at $$z$$. We can merge the two walks that we can assume exist. #### Proof Let $$x,y,z \in V(G)$$ such that $$xWy$$ and $$yWz$$. We need to show that $$xWz$$. Since $$xWy$$, there exists a walk $$w_1$$ starting at $$x$$ and ending at $$y$$, and since $$yWz$$, there exists a walk $$w_2$$ starting at $$y$$ and ending at $$z$$. The walk $$w_1\hat{y}w_2$$ starts at $$x$$ and ends at $$z$$, so in fact $$xWz$$, as desired. --- --- --- --- --- --- ---