Equivalence Relations from $\mathbb Z \to\mathbb Z$

Question

The question is, "Which of these relations on the set of all functions from $\mathbb Z$ to $\mathbb Z$ are equivalence relations."

The first relation to consider is $\{(f,g)|f(1)=g(1)\}$,it seems easy ,but I don't know how to handle

The second relation to consider is, $\{(f,g)|f(0)=g(0)∨f(1)=g(1)\}$ For this one, I am not very certain where to begin.

The third one, $\{(f,g)|f(x)−g(x)=1,\forall x∈\mathbb Z\}$ I can see how this isn't reflexive, because f(x)−f(x)=0 is always true for any function. I can also see how it isn't symmetric, because although $f(x)−g(x)=1$ could be true, it's counter-part, $g(x)−f(x)=−1$, won't be true. Despite me being able to see those facts, I can not see how it isn't transitive. How would I show that?

The fourth one, $\{(f,g)|$for some $C ∈\mathbb Z,\forall x∈\mathbb Z,f(x)−g(x)=C\}$ I had the idea that it wasn't an equivalence relation based on the fact that if we let $f(x)=x$, and $g(x)=x−1$, and say x=1, then $f(1)−g(1)=C\implies C=1$, but $g(1)−f(1)=C\implies C=−1$. The C values aren't the same, implying the relation wouldn't be symmetric, right? Also, I am not sure how to prove or disprove that the relation is transitive.

The last one is similar to the first one: $\{(f,g)|f(0)=g(1)∧f(1)=g(0)\}$; and like the first one, I am not sure where to begin.

Sorry that this post is rather long. But thank you for reading! and I hope that you can help me.

Answer 1

Keep in mind that the equivalence property is actually $3$ different properties.

Definition 1: Let $R$ be a relation on a set $A$. We say that $R$ is Reflexive iff $\forall x\in A$, $$xRx$$

Definition 2: Let $R$ be a relation on a set $A$. We say that $R$ is Symmetric iff $\forall x\in A, \forall y\in A$, $$xRy \Rightarrow yRx$$

Definition 3: Let $R$ be a relation on a set $A$. We say that $R$ is Transitive iff $\forall x\in A, \forall y\in A, \forall z\in A$, $$xRy \text{ and }yRz\Rightarrow xRz$$

So to prove a relation is an equivalence relation, you need to prove all three properties. Let us denote $\mathcal{C}$ to be the set of all auto functions on $Z$

Let us start with the first relation on $\mathbb{Z}$ we say that $$fRg\Leftrightarrow f(1)=g(1)$$

Reflexive: $\forall f\in \mathcal{C}$, $$f(1)=f(1)$$ $$\Rightarrow fRf$$ $$\Rightarrow R \text{ is reflexive }$$

Symmetric: $\forall f\in\mathcal{C},\forall g\in \mathcal{C}$, $$fRg$$ $$\Rightarrow f(1)=g(1)$$ $$\Rightarrow g(1)=f(1)$$ $$\Rightarrow gRf$$ $$\Rightarrow R \text{ is symmetric}$$

Transitive: $\forall f\in\mathcal{C},\forall g\in \mathcal{C}, \forall h\in \mathcal{C}$, $$fRg\;\wedge \; gRh$$ $$\Rightarrow f(1)=g(1)\; \wedge \; g(1)=h91)$$ $$\Rightarrow f(1)=h(1)$$ $$\Rightarrow fRh$$ $$\Rightarrow R \text{ is Transitive}$$

hence why we concude that $R$ is an equivalence relation.

As for the second relation $$fTg\Leftrightarrow f(0)=g(0)\;\vee\; f(1)=g(1)$$ this relation is not transitive. Let $f(x)=x, g(x)=2x, \text{ and } h(x)=x+1$ $$f(0)=g(0)=0, g(1)=h(1)=2, f(1)=1, \text{ and }h(0)=1$$ $$\Rightarrow f(0)\ne h(0)\text{ and }f(1)\ne h(1)$$ $$\Rightarrow fTg\;\wedge \; gTh \text{ but } f\not T h$$ which means that $T$ is not transitive and, hence not an equivalence relation.

As for the third and forth relation, these will only be true if $C=0$ which means they are the same function. For $C\ne 0$ $$fKg\Leftrightarrow \forall x\in \mathbb{Z}, f(x)-g(x)=C$$ This relation is not reflexive ( nor transitive but reflexive is easier to disprove) Let $f(x)=x$, $\forall x\in \mathbb{Z}$ $$f(x)-f(x)=0\ne C$$ $$\Rightarrow f\not K f$$ which means that $K$ is not reflexive and, hence not an equivalence relation.

As for the last relation $$fPg\Leftrightarrow f(0)=g(1)\;\wedge\; f(1)=g(0)$$ Again this one is not reflexive. Let $f(x)=x$ then $$f(0)=0\;\wedge\; f(1)=1$$ $$\Rightarrow f(0)\ne f(1)$$ $$\Rightarrow f\not P f$$ which means that $P$ is not reflexive and, hence not an equivalence relation.

Hope this helped.

Answer 2

1. For the first one, $(f,f)$ always belongs to the relation because $f(1)=f(1)$. Hence it is reflexive.
   It is symmetric too, as $f(1)=g(1)\implies g(1)=f(1)$. And of course, it is transitive, as $$f(1)=g(1)\land g(1)=h(1)\implies f(1)=h(1),$$ thus causing $(f,h)$ to belong to the relation whenever $(f,g)$ and $(g,h)$ both do. This has to do directly with Equality being an equivalence relation.
2. This is almost identical to the first one.

3,4. You might get some clarity by observing that the fourth one is a direct generalisation of the third one, with a parameter C replacing the constant $1$. For transitivity, if $(f,g)$ and $(g,h)$ belong to the set, then $f(x)-g(x)=g(x)-h(x)=1$ and adding them gives $f(x)-h(x)=2$, which means $(f,h)$ definitely cannot belong to the relation. Thus, non-transitive.

5. This one is not reflexive, as all ordered pairs $(f,f)$, where $f:\mathbb Z\to \mathbb Z$ is any function, do not belong to the relation set. It is symmetric though, which should be easy to see. For transitivity, if $(f,g)$ and $(g,h)$ belong to the set, then we have $$f(0)=g(1), g(0)=f(1)$$$$g(0)=h(1), h(0)=g(1).$$ which means that $$f(0)=h(0), f(1)=h(1)$$ which means that $(f,h)$ needn’t necessarily be in the set. Thus non-transitive.