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
    @ 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