Null Quantification Rosen's Discrete Math Textbook Exercise Confusion/Clarification

Question

From Discrete Math Rosen textbook 8th edition Section 1.4 Exercises:

Exercise 48-51 establish rules for null quantification that we can use when a quantified variable does not appear in part of a statement.

Establish these logical equivalences, where x does not occur as a free variable in A. Assume that the domain is nonempty.

Exercise 48:

a) (∀xP(x)) ∨ A ≡ ∀x(P(x) ∨ A)

b) (∃xP(x)) ∨ A ≡ ∃x(P(x) ∨ A)

Exercise 49:

a) (∀xP(x)) ∧ A ≡ ∀x(P(x) ∧ A)

b) (∃xP(x)) ∧ A ≡ ∃x(P(x) ∧ A)

Exercise 50:

a) ∀x(A → P(x)) ≡ A → ∀xP(x)

b) ∃x(A → P(x)) ≡ A → ∃xP(x)

Exercise 51:

a) ∀x(P(x) → A) ≡ ∃xP(x) → A

b) ∃x(P(x) → A) ≡ ∀xP(x)→ A

QUESTION 1: Why do they have to mention that "...where x does not occur as a free variable in A." here? I feel it can be for 2 reasons:

1. So many of the expressions can actually be propositions since if x were a free variable in A, then expressions like (∀xP(x)) ∨ A wouldn't be considered propositions since A's x is not quantified nor assigned a value, the requirements for A to be a proposition and hence make this conjunction a proposition

2. Mainly relating to definition of null quantification, so A is not affected by any quantifier of A, hence we're able to pull it out like this and make logical equivalences.

This will also help clarify another part of the textbook:

Express the statement “If a person is female and is a parent, then this person is someone’s mother” as a logical expression involving predicates, quantifiers with a domain consisting of all people, and logical connectives.

Solution: The statement “If a person is female and is a parent, then this person is someone’s mother” can be expressed as “For every person x, if person x is female and person x is a parent, then there exists a person y such that person x is the mother of person y.” We introduce the propositional functions F(x) to represent “x is female,” P(x) to represent “x is a parent,” and M(x, y) to represent “x is the mother of y.” The original statement can be represented as

∀x((F(x) ∧ P(x)) → ∃yM(x, y)).

Using the null quantification rule in part (b) of Exercise 49 in Section 1.4, we can move ∃y to the left so that it appears just after ∀x, because y does not appear in F(x) ∧ P(x). We obtain the logically equivalent expression

∀x∃y((F(x) ∧ P(x)) → M(x, y)).

Where I guess they meant to say Exercise 50 part b instead, and I guess they just did (using exericse 50b result):

∀x( (F(x) ∧ P(x)) → ∃yM(x, y) )

≡

∀x( ∃y[ (F(x) ∧ P(x)) → M(x, y) ] )

≡

∀x∃y((F(x) ∧ P(x)) → M(x, y))

Where they just focused on the inner statement like I showed here.

QUESTION 2: So this leads me to another question, which is when looking at inner statements, do we assume we're looking at some particular x in the domain, since otherwise,

(F(x) ∧ P(x)) → ∃yM(x, y) wouldn't really be a proposition since the x is quantified nor assigned a value here?

Kindly please let me know if I'm correct and further help clarify my understanding of null quantification.

Answer 1

You have to remember that we want equivalences to not just be between propositions, but between formulas in general that can contain free variables.

For example, take the statement $\forall x (P(x) \lor Q(x))$. Clearly this is equivalent to $\forall x (Q(x) \lor P(x))$. But how do we justifiy that? It is because by Commutation the formula $P(x) \lor Q(x)$ is equivalent to $Q(x) \lor P(x)$. So again, we want equivalences to hold between formulas.

Likewise, consider $\exists x \forall y (P(x) \to R(x,y))$. We want to be able to demonstrate that this is equivalent to $\exists x (P(x) \to \forall y \ R(x,y))$. And we do that by pointing out that $\forall y (P(x) \to R(x,y))$ is equivalent to $P(x) \to \forall y \ R(x,y)$. So again, we need to have equivalences of this type to hold between formulas, not just propositions. And so that's why they need to specuify that the $A$ in all these equivalences do not contain $x$ as a free variable, because that might actually be the case, and if that is the case, the equivalence may no longer hold.

But yes, once we have established those equivalence to hold, then they can be applied to propositions that are only part of 'proper' propositions, just as you show in that example. That is: because $F(x) \land P(x)$ does not contain any free variable $y$, we have that $(F(x) \land P(x)) \to \exists y \ M(x,y)$ is equivalent to $\exists y ((F(x) \land P(x)) \to M(x,y))$, and therefore $\forall x (F(x) \land P(x)) \to \exists y \ M(x,y)$ is equivalent to $\forall x \exists y ((F(x) \land P(x)) \to M(x,y))$