Definition df-bj-nnf 37463

Description: Definition of the nonfreeness quantifier. The formula Ⅎ'𝑥𝜑 has the intended meaning that the variable 𝑥 is semantically nonfree in the formula 𝜑. The motivation for this quantifier is to have a condition expressible in the logic which is as close as possible to the non-occurrence condition DV (𝑥, 𝜑) (in Metamath files, "$d x ph $."), which belongs to the metalogic.

The standard syntactic nonfreeness condition, also expressed in the metalogic, is intermediate between these two notions: semantic nonfreeness implies syntactic nonfreeness, which implies non-occurrence. Both implications are strict; for the first, note that ⊢ Ⅎ'𝑥𝑥 = 𝑥, that is, 𝑥 is semantically (but not syntactically) nonfree in the formula 𝑥 = 𝑥; for the second, note that 𝑥 is syntactically nonfree in the formula ∀𝑥𝑥 = 𝑥 although it occurs in it.

We now prove two metatheorems which make precise the above fact that, as far as proving power is concerned, the nonfreeness condition Ⅎ'𝑥𝜑 is very close to the non-occurrence condition DV (𝑥, 𝜑).

Let S be a Metamath system with the FOL-syntax of (i)set.mm, containing intuitionistic positive propositional calculus and ax-5 1943 and ax5e 1945.

Theorem 1. If the scheme

(Ⅎ'𝑥𝜑 & PHI₁ & ... & PHI_n ⇒ PHI₀, DV)

is provable in S, then so is the scheme

(PHI₁ & ... & PHI_n ⇒ PHI₀, DV ∪ {{𝑥, 𝜑}}).

Proof: By bj-nnfv 37504, we can prove (Ⅎ'𝑥𝜑, {{𝑥, 𝜑}}), from which the theorem follows. QED

Theorem 2. Suppose that S also contains (the FOL version of) modal logic KB and commutation of quantifiers alcom 2196 and excom 2199 (possibly weakened by a DV condition on the quantifying variables), and that S can be axiomatized such that the only axioms with a DV condition involving a formula variable are among ax-5 1943, ax5e 1945, ax5ea 1946. If the scheme

(PHI₁ & ... & PHI_n ⇒ PHI₀, DV)

is provable in S, then so is the scheme

(Ⅎ'𝑥𝜑 & PHI₁ & ... & PHI_n ⇒ PHI₀, DV ∖ {{𝑥, 𝜑}}).

More precisely, if S contains modal 45 and if the variables quantified over in PHI₀, ..., PHI_n are among 𝑥₁, ..., 𝑥_m, then the scheme

(PHI₁ & ... & PHI_n ⇒ (antecedent → PHI₀), DV ∖ {{𝑥, 𝜑}})

is provable in S, where the antecedent is a finite conjunction of formulas of the form ∀𝑥_i1 ...∀𝑥_ip Ⅎ'𝑥𝜑 where the 𝑥_ij's are among the 𝑥_i's.

Lemma: If 𝑥 ∉ OC(PHI), then S proves the scheme

(Ⅎ'𝑥𝜑 ⇒ Ⅎ'𝑥 PHI, {{𝑥, 𝑎} ∣ 𝑎 ∈ OC(PHI) ∖ {𝜑}}).

More precisely, if the variables quantified over in PHI are among 𝑥₁, ..., 𝑥_m, then

((antecedent → Ⅎ'𝑥 PHI), {{𝑥, 𝑎} ∣ 𝑎 ∈ OC(PHI) ∖ {𝜑}})

is provable in S, with the same form of antecedent as above.

Proof: By induction on the height of PHI. We first note that by bj-nnfbi 37483 we can assume that PHI contains only primitive (as opposed to defined) symbols. For the base case, atomic formulas are either 𝜑, in which case the scheme to prove is an instance of id 23, or have variables all in OC(PHI) ∖ {𝜑}, so (Ⅎ'𝑥 PHI, {{𝑥, 𝑎} ∣ 𝑎 ∈ OC(PHI) ∖ {𝜑}}) by bj-nnfv 37504, hence ((Ⅎ'𝑥𝜑 → Ⅎ'𝑥 PHI), {{𝑥, 𝑎} ∣ 𝑎 ∈ OC(PHI) ∖ {𝜑}}) by a1i 11. For the induction step, PHI is either an implication, a negation, a conjunction, a disjunction, a biconditional, a universal or an existential quantification of formulas where 𝑥 does not occur. We use respectively bj-nnfim 37488, bj-nnfnt 37486, bj-nnfan 37490, bj-nnfor 37492, bj-nnfbit 37494, bj-nnfalt 37526, bj-nnfext 37527. For instance, in the implication case, if we have by induction hypothesis

((∀𝑥₁ ...∀𝑥_m Ⅎ'𝑥𝜑 → Ⅎ'𝑥 PHI), {{𝑥, 𝑎} ∣ 𝑎 ∈ OC(PHI) ∖ {𝜑}}) and ((∀𝑦₁ ...∀𝑦_n Ⅎ'𝑥𝜑 → Ⅎ'𝑥 PSI), {{𝑥, 𝑎} ∣ 𝑎 ∈ OC(PSI) ∖ {𝜑}}),

then bj-nnfim 37488 yields

(((∀𝑥₁ ...∀𝑥_m Ⅎ'𝑥𝜑 ∧ ∀𝑦₁ ...∀𝑦_n Ⅎ'𝑥𝜑) → Ⅎ'𝑥 (PHI → PSI)), {{𝑥, 𝑎} ∣ 𝑎 ∈ OC(PHI → PSI) ∖ {𝜑}})

and similarly for antecedents which are conjunctions as in the statement of the lemma.

In the universal quantification case, say quantification over 𝑦, if we have by induction hypothesis

((∀𝑥₁ ...∀𝑥_m Ⅎ'𝑥𝜑 → Ⅎ'𝑥 PHI), {{𝑥, 𝑎} ∣ 𝑎 ∈ OC(PHI) ∖ {𝜑}}),

then bj-nnfalt 37526 yields

((∀𝑦∀𝑥₁ ...∀𝑥_m Ⅎ'𝑥𝜑 → Ⅎ'𝑥∀𝑦 PHI), {{𝑥, 𝑎} ∣ 𝑎 ∈ OC(∀𝑦 PHI) ∖ {𝜑}})

and similarly for antecedents which are conjunctions as in the statement of the lemma.

Note bj-nnfalt 37526 and bj-nnfext 37527 are proved from positive propositional calculus with alcom 2196 and excom 2199 (possibly weakened by a DV condition on the quantifying variables), and modalB (via bj-19.12 37459). QED

Proof of the theorem: Consider a proof of that scheme directly from the axioms. Consider a step where a DV condition involving 𝜑 is used. By hypothesis, that step is an instance of ax-5 1943 or ax5e 1945 or ax5ea 1946. It has the form (PSI → ∀𝑥 PSI) where PSI has the form of the lemma and the DV conditions of the proof contain {{𝑥, 𝑎} ∣ 𝑎 ∈ OC(PSI) }. Therefore, one has

((∀𝑥₁ ...∀𝑥_m Ⅎ'𝑥𝜑 → Ⅎ'𝑥 PSI), {{𝑥, 𝑎} ∣ 𝑎 ∈ OC(PSI) ∖ {𝜑}})

for appropriate 𝑥_i's, and by bj-nnfa 37464 we obtain

((∀𝑥₁ ...∀𝑥_m Ⅎ'𝑥𝜑 → (PSI → ∀𝑥 PSI)), {{𝑥, 𝑎} ∣ 𝑎 ∈ OC(PSI) ∖ {𝜑}})

and similarly for antecedents which are conjunctions as in the statement of the theorem. Similarly if the step is using ax5e 1945 or ax5ea 1946, we would use bj-nnfe 37467 or bj-nnfea 37470 respectively.

Therefore, taking as antecedent of the theorem to prove the conjunction of all the antecedents at each of these steps, we obtain a proof by "carrying the context over", which is possible, as in the deduction theorem when the step uses ax-mp 5, and when the step uses ax-gen 1828, by bj-nnf-alrim 37481 and bj-nnfa1 37520 (which requires modal 45). The condition DV (𝑥, 𝜑) is not required by the resulting proof.

Finally, there may be in the global antecedent thus constructed some dummy variables, which can be removed by spvw 2014. QED

Compared with df-nf 1817, the present definition is stricter on positive propositional calculus (bj-nnfnfTEMP 37476) and equivalent on core FOL plus sp 2219 (bj-nfnnfTEMP 37518). While being stricter, it still holds for non-occurring variables (bj-nnfv 37504), which is the basic requirement for this quantifier. In particular, it translates more closely the associated variable disjointness condition. Since the nonfreeness quantifier is a means to translate a variable disjointness condition from the metalogic to the logic, it seems preferable. Also, since nonfreeness is mainly used as a hypothesis, this definition would allow more theorems, notably the 19.xx theorems, to be proved from the core axioms, without needing a 19.xxv variant.

One can devise infinitely many definitions increasingly close to the non-occurring condition, like ((∃𝑥𝜑 → 𝜑) ∧ (𝜑 → ∀𝑥𝜑)) ∧ ∀𝑥((∃𝑥𝜑 → 𝜑) ∧ (𝜑 → ∀𝑥𝜑)) ∧ ∀𝑥∀𝑥... and each stronger definition would permit more theorems to be proved from the core axioms. A reasonable rule seems to be to stop before nested quantifiers appear (since they typically require ax-10 2178 to work with), and also not to have redundant conjuncts when full metacomplete FOL= is developed.

(Contributed by BJ, 28-Jul-2023.)

Assertion

Ref	Expression
df-bj-nnf	⊢ (Ⅎ'𝑥𝜑 ↔ ((∃𝑥𝜑 → 𝜑) ∧ (𝜑 → ∀𝑥𝜑)))

Detailed syntax breakdown of Definition df-bj-nnf

Step	Hyp	Ref	Expression
1		wph	. . 3 wff 𝜑
2		vx	. . 3 setvar 𝑥
3	1, 2	wnnf 37462	. 2 wff Ⅎ'𝑥𝜑
4	1, 2	wex 1812	. . . 4 wff ∃𝑥𝜑
5	4, 1	wi 4	. . 3 wff (∃𝑥𝜑 → 𝜑)
6	1, 2	wal 1568	. . . 4 wff ∀𝑥𝜑
7	1, 6	wi 4	. . 3 wff (𝜑 → ∀𝑥𝜑)
8	5, 7	wa 401	. 2 wff ((∃𝑥𝜑 → 𝜑) ∧ (𝜑 → ∀𝑥𝜑))
9	3, 8	wb 209	1 wff (Ⅎ'𝑥𝜑 ↔ ((∃𝑥𝜑 → 𝜑) ∧ (𝜑 → ∀𝑥𝜑)))

This definition is used by:  bj-nnfa  37464  bj-nnfe  37467  bj-alnnf  37473  bj-dfnnf2  37475  bj-nnfbi  37483  bj-nnfnt  37486  bj-nnfim  37488  bj-nnfan  37490  bj-nnfand  37491  bj-nnfor  37492  bj-nnford  37493  bj-nnfv  37504  bj-dfnnf3  37517  bj-wnfnf  37519  bj-nnfa1  37520  bj-nnfe1  37521  bj-nnfalt  37526  bj-nnfext  37527