- #1

- 75

- 0

## Main Question or Discussion Point

given a dictionary [tex]\Sigma = \left \{f(),g(),R(,),c_0,c_1,c_2 \right \}[/tex] and a sentence [itex]\phi[/itex] over [itex]\Sigma[/itex], I need to find an algorithm to translate [itex]\phi[/itex] to [itex]\psi[/itex] over [itex]\Sigma'[/itex] where [itex]\Sigma' = \left \{Q(,,,), = \right \}[/itex] (Q is a 4-place relation symbol), so that [itex]\psi[/itex] is valid iff [itex]\phi[/itex] is valid.

I understand that I am supposed to eliminate function symbols using the equality relation in [itex]\Sigma'[/itex], so that [itex] f()[/itex] in [itex]\Sigma[/itex] is translated to a relation symbol [itex]\ F(,) [/itex] , so that [itex]\ F(a,b)[/itex] holds iff [itex]\ f(a)=b [/itex] (and likewise for [itex] g() [/itex]).

the constants can be translated to 1-ary relation symbols.

Therefore, I have an intermediate dictionary

[tex]\Sigma'' = \left \{F(,),G(,),R(,),C_0(),C_1(),C_2(), = \right \}[/tex]

I need to somehow encode the six relation symbols (3 binary and 3 unary) in [itex] Q(,,,) [/itex]. Is there a particular way to do this, is this related to equivalence classes?

thank you.

I understand that I am supposed to eliminate function symbols using the equality relation in [itex]\Sigma'[/itex], so that [itex] f()[/itex] in [itex]\Sigma[/itex] is translated to a relation symbol [itex]\ F(,) [/itex] , so that [itex]\ F(a,b)[/itex] holds iff [itex]\ f(a)=b [/itex] (and likewise for [itex] g() [/itex]).

the constants can be translated to 1-ary relation symbols.

Therefore, I have an intermediate dictionary

[tex]\Sigma'' = \left \{F(,),G(,),R(,),C_0(),C_1(),C_2(), = \right \}[/tex]

I need to somehow encode the six relation symbols (3 binary and 3 unary) in [itex] Q(,,,) [/itex]. Is there a particular way to do this, is this related to equivalence classes?

thank you.