Suppose $A,B$ sets and nonempty $X\subseteq A$. For $f\in B^A$ define $\hat f = f_{|X} \in B^X$. Define a relation $\sim $ on $B^A$ by $f\sim g \iff \hat f = \hat g$. Show that $\sim$ is an equivalence relation. If $A,B$ are finite sets, how many equivalence classes are there? How many elements in each class?
Denote:
- $B^A = \{f \text{ a function}\mid f:A\to B\}$
- $\hat f = f_{|X} \in B^X$ as function $\hat f(x) = f(x), \forall x\in X$.
To show equivalence relation:
- $f\sim f \implies \hat f = \hat f \implies \sim$ is reflexive
- $f\sim g \implies \hat f=\hat g \implies \hat g = \hat f \implies g \sim f \implies \sim$ is symmetric
- $f\sim g \wedge g \sim h \implies \hat f = \hat g \wedge \hat g = \hat h \implies \hat f = \hat g = \hat h \implies f \sim h \implies \sim $ is transitive.
Thus, $\sim$ is an equivalence relation.
If $A,B$ are finite sets, then the number of equivalence classes are defined by the number of functions we have $\hat f : X \to B$? But how does this make sense? Can someone explain?
If this above is the case then we have $|B|^{|X|}$ number of functions $\hat f : X \to B$ and, thus, the number of equivalence classes.
(EDIT) We have $A-X$ elements by which two functions $f,g$ differ. Thus the number of functions $f:A-X \to B$ is $|B|^{|A-X|}$. I am not sure where to proceed from here to characterize the number of elements in each equivalence class.