Exclude operation symbols in signature

671 Views Asked by At

We probably know what a signature is, it contains a set $\sigma_{op}$ (the operation symbols), $\sigma_{rel}$ (the relation symbols) and a function $ar:\sigma_{op}\cup\sigma_{rel}\rightarrow\mathbb N$.

If we exclude some operation symbols we get a structure we call reduction. I have a problem finding all four "reductions" of $(\mathbb N,0,1,+,\times,<)$ which are isomorph to the "reductions" of $(\mathbb Q,0,1,-,+,\times)$.

This is an exercise in my logic book in a chapter where Tarskis definition of truth is discussed, I do not see a relation, may you could help me with that.

1

There are 1 best solutions below

7
On BEST ANSWER

First of all, what you call "reductions" are usually called "reducts".

Now you're looking for four reducts of $(\mathbb{N},0,1,+,\times,<)$ which are isomorphic to reducts of $(\mathbb{Q},0,1,-,+,\times)$. Notice that isomorphism only makes sense for structures in the same signature, so you're going to have to get rid of $<$ and $-$, since these symbols only appear in one of the signatures each.

We're left with the set of symbols $\{0, 1, +, \times\}$. We get one reduct of $(\mathbb{N},0,1,+,\times)$ and $(\mathbb{Q},0,1,+,\times)$ for each subset of this set of symbols. Exactly four of these subsets produce isomorphic structures.

Here's one to get you started: For structures in the empty signature, an isomorphism is just a bijection (there are no operations / relations to respect), so after taking a reduct to the empty signature, any two structures of the same cardinality are isomorphic.

I'm not sure why this is the section on Tarski's definition of truth - I see no connection.