kenneth h rosen chapter 1 section 1.5 nested quantifiers excercise 1.5 question 48

Question

Show that ∀xP (x) ∨ ∀xQ(x) and ∀x∀y(P (x) ∨ Q(y)),
where all quantifiers have the same nonempty domain,
are logically equivalent. (The new variable y is used to
combine the quantifications correctly.)

Comments

In P(x) , x is free variable. However when we quantify them using any quantifier we can not assign a value to x. Now x refers to domain. So after quantification the variable is dummy its name does not matter whatever the name is it will refer to domain. Therefore it is called a dummy variable.

∀xP (x) ∨ ∀xQ(x) : in any proposition the variable refers to its nearest quantifier. Therefore the X in P(x) and X in Q(x) are different. To avoid confusion we can change any one variable name to another name. You can watch go classes discrete mathematics lecture they are free and this concept taught there very well.

After changing the name : ∀xP (x) ∨ ∀yQ(y). We can take for all Y to the front it is not affecting anything else in the proposition.

To show the same non empty domain. I believe you need to take example.
P(x): Even , Q(y):prime, Domain : N

---

i basically prove using null quantification as you told but i want to prove same by using biconditional stmt as we know that sometimes equivalence sign is same represented by bicondtional

thank you

---

For the same domain, If you want to prove by  ←→

∀xP (x) ∨ ∀xQ(x)  ←→ ∀x∀y(P (x) ∨ Q(y))

You can see LHS and RHS of implication is same in every case.

By conditional is true when both LHS and RHS are same. So It can be used for some Propositional Expression to express equivalence. This thing was explained in first lecture that I mentioned above. It is highly recommendable.