Edward A. answered • 05/07/20
High School Math Whiz grown up--I've even tutored my grandchildren
Kaan, I think it isn't that hard.
First, recognize that the x's on the right are different from the x's on the left, so let's change the right hand x's to z's
Second, we don't need to expand the P and Q stuff, because the left hand side is already in prenex form.
So, let's rewrite this as
∃x ∀y M → ∀z R
where M is P(x,y) ↔ Q(y), and R is R(z)
I guess I would start by moving the z quantifier.
∃x ∀y M → ∀z R
∀z (∃x ∀y M → R)
Next we translate the existential quantifier
∀z (∀x (∀y M → R))
and the lowest ∀ ,
∀z (∀x (∃y (M → R)))
and you can remove the parentheses
∀z ∀x ∃y M → R
restore the abbreviations
∀z ∀x ∃y ( (P(x,y) ↔ Q(y)) → R(z) )
If you have any questions, please ask,
Ed
Edward A.
Kaan, now that you ask, I fear that I answered incorrectly. However, abbreviating the M and R is wise. Also, before answering, I want to be sure we understand the implicit parentheses. The original formula is really [1] (∃x (∀y M)) → (∀zR) Now, the Wikipedia article on “prenex normal form” gives the conversion rules. It’s a bit confusing because it shows both the most primitive rules and also the more convenient shortcuts that I used, without distinguishing them. I’ll restate my answer. First, There’s a shortcut rule about removing a quantifier on the right side of implication: ϕ→ (∀x ψ) is equivalent to ∀x(ϕ→ψ) So our formula translates from [1] (∃x (∀y M)) → (∀zR) to [2] ∀z( (∃x (∀y M)) → R) Next, your first question is addressed by the rule in “implication”: (∃xϕ)→ψ Can be interchanged with ∀x(ϕ→ψ), yielding [3] ∀z( ∀x((∀y M ) → R)) Next, we’ll expand the y quantifier: there’s a rule saying (∀y ϕ) → ψ is equivalent to ∃y(ϕ→ψ), so the whole formula is [4] ∀z( ∀x(∃y(M → R))) I made a mistake in saying you could remove all the parentheses. We have to keep the (M → R), so the final statement is [5] ∀z ∀x ∃y (M → R), or, expanding the abbreviations: ∀z ∀x ∃y ( (P(x,y) ↔ Q(y)) → R(z)) Does this help? The key is to be precise about the scope of a quantifier, and to put parentheses where necessary. Please ask more if you need to, Ed05/08/20
Kaan I.
Thank you sir, I have a question: How it is possible to translate existential into this (∃x ∀y M → R) to (∀x (∀y M → R))? And also, How it is possible to translate this (∀y M → R) to ∃y (M → R)?05/07/20