Hello so I'm trying to make an exercise, but it makes no sense to me it goes as follows.
$Fun(X,Y)$ is the set of all functions $f:X\rightarrow Y$. We define a relation $R$ on $Fun(X,Y)$ by saying that $(f,g)\in R$ if and only if $$\{x \in X \mid f(x) \neq g(x)\}$$ is a finite set.
Prove that R is an equivalence relation?
But isn't that R is not an equivalence relation?
- Because for example if I would prove that this function is reflexive I would have to say that $f(x) \neq f(x)$.
- Hower I can say it is symmetric because if $f(x) \neq g(x)$ then surely $g(x) \neq f(x)$.
- And at last it is not transitive because if $f(x) \neq g(x)$ and $g(x) \neq h(x)$ then $f(x) \neq h(x) $ is not implied.
Is my thoughtprocess wrong or is it just the exercise? If you can help me please share your wisdom
Thanks in advance
Your problem is that you’re not actually using the definition of $R$. For each ordered pair $\langle f,g\rangle$ of functions from $X$ to $Y$ you have to look at
$$\{x\in X:f(x)\ne g(x)\}\,,$$
the set of points in $X$ at which $f$ and $g$ disagree. For instance, if $X=Y=\Bbb N$, $f(n)=n$ for all $n\in\Bbb N$, and $g(n)=\max\{3,n\}$ for all $n\in\Bbb N$, then $f(n)=g(n)$ for all $n\ge 3$, but $f(0)=0\ne 3=g(0)$, $f(1)=1\ne 3=g(1)$, and $f(2)=2\ne 3=g(2)$:
$$\{n\in\Bbb N:f(n)\ne g(n)\}=\{0,1,2\},,$$
because $f$ and $g$ differ at the points $0,1$, and $2$ and at no others. And this set is finite, so $\langle f,g\rangle\in R$.
Change the definition of $g$ by setting $g(n)=\min\{3,n\}$ for each $n\in\Bbb N$, and you’d find that $f(n)=g(n)=n$ for $n\in\{0,1,2,3\}$, but $f(n)=n\ne 3=g(n)$ for $n>3$. Now
$$\{n\in\Bbb N:f(n)\ne g(n)\}=\{n\in\Bbb N:n\ge 4\}$$
is an infinite set, so $\langle f,g\rangle\notin R$.
It’s inconvenient to have to keep writing $\{x\in X:f(x)\ne g(x)\}$, so for $\langle f,g\rangle\in\operatorname{Fun}(X,Y)$ let
$$D(f,g)=\{x\in X:f(x)\ne g(x)\}\,;$$
this abbreviation will save a good bit of writing and reduce the visual clutter. By definition, then, $\langle f,g\rangle\in R$ if and only if $D(f,g)$ is finite.
Reflexivity should now be clear: for any $f:X\to Y$, $f(x)=f(x)$ for every $x\in X$, so $D(f,f)=\varnothing$. $\varnothing$ is finite, so $\langle f,f\rangle\in R$, and $R$ is reflexive.
Symmetry is also easy. For any $f,g:X\to Y$, $D(f,g)=D(g,f)$. If $\langle f,g\rangle\in R$, then $D(f,g)$ is finite, so $D(g,f)=D(f,g)$ is finite, and therefore $\langle g,f\rangle\in R$.
It does take a little more work to prove that $R$ is transitive. Suppose that $\langle f,g\rangle,\langle g,h\rangle\in R$, so that $D(f,g)$ and $D(g,h)$ are finite subsets of $X$; we’d like to prove that $D(f,h)$ is also finite. This would certainly be true if we could show that $D(f,h)\subseteq D(f,g)\cup D(g,h)$, since the union of two finite sets is finite.
Suppose that $x\in X\setminus\big(D(f,g)\cup D(g,h)\big)$. Then $f(x)=g(x)$ (since $x\notin D(f,g)$), and $g(x)=h(x)$ (since $x\notin D(g,h)$), so $f(x)=h(x)$, and therefore $x\notin D(f,h)$, i.e., $x\in X\setminus D(f,h)$. In other words, we’ve shown that
$$X\setminus\big(D(f,g)\cup D(g,h)\big)\subseteq X\setminus D(f,h)$$
and hence that
$$D(f,h)\subseteq D(f,g)\cup D(g,h)\,,$$
as desired.