Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have some problems with the following theorem: Fix an signature $\sigma$ and a set of variables $\mathbb{V}$. We call $t$ and $t_1$ "equivalent", if for every $\sigma$-structure $S$ and every term function $\beta: T \rightarrow \underline{S}$, where $T$ is the set of all $\sigma$-terms and $\underline{S}$ the underlying set of the structure $S$, one has $\beta(t)=\beta(t_1)$. One has then to show, that $t$ is equivalent to $t_1$ iff $t=t_1$.

EDIT: The "counterexample" I previously provided was incorrect, since it wasn't a proper counterexample. (So in terms of what I previously wrote here, the theorem seems to be correct). I still would like to have a full proof for it. The idea for the nontrivial direction ("$\Rightarrow$") is to use the term algebra. My idea was that roughly that I since I know that in a term algebra $\beta(t)=\beta(t_1) \Leftrightarrow t=t_1$ trivially holds, since it is an obvious tautology, I think I should somehow show that every other structure can somehow transformed into a term algebra. Has someone some ideas how to do this ?

share|cite|improve this question
@temo Could you please tell us what textbook you are using. – Bill Dubuque May 29 '11 at 18:12
@temo: I don't understand why you think this is a counterexample to the theorem. Here, you have two different term functions that disagree on any given term. The theorem says that if you have two different terms, then you can find a single term function that takes different values at the two terms. The theorem does not say "a term takes the same value under all term functions." The theorem says "if two terms are different, then you can find a term function that evaluates the two terms to different things." – Arturo Magidin May 29 '11 at 19:04
@ Arturo Magidin: Ah, of course,you're right – temo May 29 '11 at 20:58
@ Bill Dubuque: None - it was just written on the blackboard during a course at the university. Could you maybe recommend me a textbook instead, since I don't know of any, where I potentially could look this type question up ? – temo May 29 '11 at 21:00
@temo: it's not true that "every other structure can be somehow transformed into a term algebra." (Two group words yield the same element in the free group in countably many generators, the equivalent of the term algebra, if and only if they are identical; however, this does not mean that every group can be somehow transformed into a free group. The point is that if it holds always, then it holds in the term algebra, where the conclusion you want follows. – Arturo Magidin May 29 '11 at 21:11
up vote 2 down vote accepted

It should be obvious that if $t=t_1$, then for every $\sigma$-structure $S$ and every term function $\beta\colon T\to\underline{S}$, you have $\beta(t)=\beta(t_1)$; after all, $\beta$ is a function.

What you want to use the term algebra for is the converse: showing that if $t\neq t_1$, then there exists a $\sigma$-structure $S$ and a term function $\beta\colon T\to \underline{S}$ such that $\beta(t)\neq\beta(t_1)$. Take $S$ to be the term algebra, and take $\beta$ to be the canonical map from $T$ to the term algebra.

(Alternatively, if the condition holds, then it holds if $S$ is the term algebra and $\beta$ is the canonical map; in particular, in the term algebra you must have $\beta(t)=\beta(t_1)$, from which you want to conclude that $t=t_1$).

share|cite|improve this answer
as always, a great answer. thanks! – temo May 30 '11 at 5:43

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.