2

are these translations equivalent?

(∀x)(Ax ⇒ (∀y)(By ⇒ Cxy))

(∀x)(Bx ⇒ (∀y)(Ay ⇒ Cyx))

1

1 Answer 1

1

Yes. We can use the following basic equivalence principles:

Prenex Laws: P ⇒ (∀y)(Qy) = (∀y)(P ⇒ Qy) (assuming P does not contain any y's as a free variable)

Swapping Quantifiers of Same Type: (∀x)(∀y)F = (∀y)(∀x)F (works for any formula F)

Replacing Variables: (∀x)F(x) = (∀y)F(y)

Exportation: P ⇒ (Q ⇒ R) = (P∧Q)⇒R

So:

(∀x)(Ax⇒(∀y)(By⇒Cxy))= (Prenex)

(∀x)(∀y)(Ax⇒(By⇒Cxy))= (Exportation)

(∀x)(∀y)((Ax∧By)⇒Cxy)= (Commutation)

(∀x)(∀y)((By∧Ax)⇒Cxy)= (Exportation)

(∀x)(∀y)(By⇒(Ax⇒Cxy))= (Swapping Quantifiers of Same Type)

(∀y)(∀x)(By⇒(Ax⇒Cxy))= (Replacing variables)

(∀z)(∀x)(Bz⇒(Ax⇒Cxz))= (Replacing variables)

(∀z)(∀y)(Bz⇒(Ay⇒Cyz))= (Replacing variables)

(∀x)(∀y)(Bx⇒(Ay⇒Cyx))= (Prenex)

(∀x)(Bx⇒(∀y)(Ay⇒Cyx))

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .