I'd like to prove, following Terence Tao's Analysis I book, that the relation $R$ in the class of functions from $X$ to $Y$ given by $$f\mathrel{R}g \iff \textrm{ for every } x\in X, f(x)=g(x)$$ satisfies what Tao calls the "Axiom of Substitution", that is, if $f,g:X\to Y$ are functions and $f\mathrel{R} g$, then $h(f)=h(g)$, for every admissible function $h$.

I don't know, however, how to proceed, so I was wondering if someone could help me prove that. How does one prove that $h(f)=h(g)$ just knowing that $f(x)=g(x)$, for all $x\in X$?

enter image description here

  • $\begingroup$ Well, you know that $=$ satisfies the axiom of substitution by definition. $\endgroup$ Aug 6 at 23:59
  • $\begingroup$ @TianVlašić You are referring to the equality symbol between $f(x)$ and $g(x)$? $\endgroup$ Aug 7 at 0:05
  • 2
    $\begingroup$ What is an "admissible function"? $\endgroup$ Aug 7 at 0:45
  • $\begingroup$ @GleisonStanlley Yes $\endgroup$ Aug 7 at 1:07
  • $\begingroup$ @TrevorGunn Any function where talking about what we want to talk about makes sense. In this case, any function $h$ that have $f$ and $g$ in its domain. $\endgroup$ Aug 7 at 1:08

1 Answer 1


I suppose you are trying to solve exercise 3.3.1 in Tao's book. The exercise requires to prove that composition of functions obeys the axiom of substitution; i.e., that if $f,\tilde{f}: X \to Y$ and $g,\tilde{g}: Y \to Z$ are functions such that $f = \tilde{f}$ and $g = \tilde{g}$, then $g \circ f = \tilde{g} \circ \tilde {f}$.

This could be proven as follows:

Let $x \in X$. Then, by reflexivity of equality $x = x$. By the axiom of substitution of equality $f(x) = f(x)$. Since $f = \tilde{f} \iff \forall x(f(x) = \tilde{f}(x))$ we can write $f(x) = \tilde{f}(x)$. By the axiom of substitution of equality $g(f(x)) = g(\tilde{f}(x))$. Since $g = g'$ we have $g(f(x)) = \tilde{g}(\tilde{f}(x))$.

  • $\begingroup$ Not really. What I want to prove is what I wrote in the text: if $f,g:X\to Y$ are functions and $f \mathrel{R} g$, then $h(f)=h(g)$, for every admissible function $h$. $\endgroup$ Aug 7 at 1:05
  • 1
    $\begingroup$ @GleisonStanlley Ok, why do you think that the same reasoning does not apply to the exact proposition you are trying to prove? If $f R g$; i.e., $(\forall x \in X)(f(x) = g(x))$ and $h$ is admissible; i.e., $h: Y \to Z$, then $h(f(x)) = h(g(x))$ by the axiom of substitution again. $\endgroup$ Aug 7 at 10:29
  • $\begingroup$ But we want to prove that $h(f)=h(g)$, not that $h(f(x))=h(g(x))$ (which may not make sense if $f(x)$ and $g(x)$ aren't in $h$ domains). $\endgroup$ Aug 7 at 13:54
  • $\begingroup$ @GleisonStanlley I'm not sure I understand what you are trying to prove then. Usually Tao proves reflexivity, symmetry and transitivity in general and then he proves substitution once he has defined some operation on the objects under interest. In this case the relation under interest is equality between functions. Thus, functions of such an equality is simply the composition of functions. He also explicitly states to prove this both in the text and in the exercises. What does $h(f)$ as opposed to $h(f(x))$ mean in your opinion? $\endgroup$ Aug 7 at 17:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .