1
$\begingroup$

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 ?

  • 0
    @temo Could you please tell us what textbook you are using.2011-05-29
  • 0
    @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."2011-05-29
  • 0
    @ Arturo Magidin: Ah, of course,you're right2011-05-29
  • 0
    @ 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 ?2011-05-29
  • 0
    @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.2011-05-29
  • 0
    @temo There are a few different ways to present this material, and the answer may depend on such. What is your definition of the term algebra, and what results do you know about it? Did your course say anything about its universal properties?2011-05-29
  • 0
    @ Bill Dubuque The term algebra was introduced in the following way: "For each $\sigma$-signature there exists an unique $\sigma$-structure $S$ such that for all term functions $\beta$ and all $\sigma$-terms $t,t_1$ we have $\beta(t)=\beta(t_1) \Leftrightarrow t=t_1$. This structure is then called $\mathit{term} \ \mathit{algebra}$". There weren't any other results/theorems etc. proved about it. This definition is all I got.2011-05-30

1 Answers 1

2

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$).

  • 0
    as always, a great answer. thanks!2011-05-30