### 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.

---
---
---
---
---
---
---