Talk:Original proof of Gödel's completeness theorem

This page might be made clearer if the same fonts were used in the text as in the expressions. (I mean, use the LaTeX version of the symbol in the text)... I tried doing this in this comment but found that Wikipedia automatically converts "< math > \ phi < / math >" into $\phi$. Is it possible to get the symbol in $\neg \phi$ without the $\neg$?

Shouldn't this be in WikiBooks? --Rory ☺ 17:31, Jun 13, 2004 (UTC)

Shouldn't this be called Godels INcompleteness theorem, for which there is already an article and proof here?

No. In addition to his incompleteness theorem, Goedel also proved a completeness theorem, in which he proved that any logically sound statement can be proven in 1st order logic.

Why is there since 13 January 2006 the incompleteness theorem at the page of the completeness theorem? Thank you for removing this again. Why is the core part of the proof missing, is anybody able to complete it?

December 2021

New discussion:

I intend to add the following to 2.5 of "Original proof of Gödel's completeness theorem" just after "In this particular case,... (x,y|x',y').":

(Φ, Φ', and Ψ are known to be of degree k only under the assumption that Q is of degree 0. The preceding step makes Q to be of degree k, violating this assumption for k ≥ 1, thus invalidating the induction step from degree k to degree k+1.)

Is this correct logically, is it formatted properly, and is it otherwise proper to add to the Wikipedia article?

Added 2021-12-31, 17:53 (UTC): I have decided to, instead of using the above parenthetical note, put a Comment near the end of 2.5 which will include the note but also a section giving more detail than the note. That section is shown below.

An important part of the proof is the induction on the degree of the arbitrary sentential (meaningful) formula φ, showing that for every integer k ≥ 0, if the theorem holds for a formula of degree k, then it holds for one of degree k+1, i.e., if every valid sentential formula of degree k is provable (which is equivalent to every sentential formula of degree k being either refutable or satisfiable), then every such formula of degree k+1 is provable (iff the equivalent for sentential formulas of degree k+1). To do this the proof constructs formulas Φ ≡ Φ' ≡ Ψ, each containing the relation Q and implying an arbitrary φ of degree k+1, each of which three is of degree k if and only if Q is of degree 0, which the proof assumes, so that by the induction hypothesis that the theorem holds for every sentential formula of degree k, the three formulas are either each refutable or each satisfiable. Then if any one of the three is satisfiable, φ is also satisfiable (by the detailed structure of the formulas). If any one is refutable, then ¬Φ is provable. However, the proof then replaces Q in ¬Φ with a formula of degree k, thus violating the induction assumption that Q is of degree 0, but the proof nevertheless concludes that, because of the induction hypothesis, if Φ is not satisfiable, then it is refutable, so ¬Φ is provable, so (because of the detailed structure of Φ) ¬φ is provable, so φ is refutable, so if the theorem is true for all sentential formulas of degree k, it is true for all of degree k+1, so it is true for all k if it can be shown to be true for k = 1, which is supposedly done in the proof's next section. The proof's violation of the essential assumption that Q is of degree 0 invalidates the induction, so invalidates the proof. I have no idea how to correct the proof to make it valid. References: Aristotle for basic logic, Mathematical Logic by Joseph Shoenfield for proof theory, Set Theory by Thomas Jech for model theory. Dirsaka (talk) 07:35, 2 January 2022 (UTC)

Welcome here! As I have noted on Wikipedia_talk:WikiProject_Mathematics#Help_needed, I am not entirely sure we should have this as a separate page in the first place.

If we do, then any discussion of the proof beyond recounting Gödel's original papers should be covered by secondary sources about the proof. I only know of the discussion in Avigad's essay (https://www.andrew.cmu.edu/user/avigad/Papers/goedel.pdf), so in case there is consensus to keep this as a separate article, we should compare with such published sources. Felix QW (talk) 13:24, 4 January 2022 (UTC)

Dear Dirsaka, I am not sure when I will get round to it, but I really think we should check what established authors have to say.

There is the following body of work which I am aware of:

Avigad's essay (https://www.andrew.cmu.edu/user/avigad/Papers/goedel.pdf)

The chapter by van Attan and Kennedy in The History of Logic (https://doi.org/10.1016/S1874-5857(09)70014-7)

The introduction to the collected works edition of Gödel's thesis

The explanatory power of a new proof: Henkin’s completeness proof (http://homepages.math.uic.edu/~jbaldwin/pub/chietihenkfeb20.pdf) by John Baldwin Felix QW (talk) 18:58, 21 January 2022 (UTC)

For what it's worth, I am not sure about your argument myself. The nifty idea in the proof of the Lemma is precisely to apply the induction statement with an uninterpreted symbol Q so that the degree is preserved, and then to substitute in the longer expression. After that, the inductive hypothesis is no longer invoked. Felix QW (talk) 19:17, 21 January 2022 (UTC)

There are two issues here, @Dirsaka::

The first is that Gödel's proof has been covered by different experts (see above), whose accounts of the proof differ somewhat from what we have on this page. None of them think there is a mistake in the proof, and they have given it quite detailed analysis. So if you think there is a problem, you should read what they have written and rewrite (the unclear parts of) the proof along their lines. If you can't do that yourself, then put a note on the talk page (as you have done) and wait until there is someone with enough time and expertise that can do it.

The second is that I don't actually believe that there is a mistake in the proof as written. The proof of the lemma applies the induction hypothesis to a formula which includes Q as a relation symbol and undisputably has degree not exceeding k. Then, after a division by cases, an argument via 'functional substitution' (see the paranthetical note in the proof) is used to conclude something about a formula which does not necessarily have degree not exceeding k. Since the induction hypothesis is no longer used after this point, though, it does not matter that it is no longer applicable. That is the point of introducing Q and appealing to functional substitution in the first place. Felix QW (talk) 11:28, 22 January 2022 (UTC)

The Wikipedia article's supposed proof fairly accurately follows, up to where my Comment was, Gödel's 1930 lecture on his completeness theorem, without any unclarity, just incorrectness, which is what my Comment was commenting on. There are several different supposed proofs of the incompleteness theorem, such as in Avigad's essay. I am a semi-expert on the subject of mathematical logic, having studied it and passed a university Ph.D. qualifying exam on that subject, and I don't think the version of the "proof" given in the W. article can be saved without a major revision of its induction argument, which I have no idea how to do, even if such a rescue revision is possible. There may be other claimed proofs of the completeness theorem which are correct.

¬Φ is the formula which contains Q and is known to be provable only because it is assumed from the induction hypothesis to have degree k and, in the case under consideration, to be provable. It is then necessary to show, from this hypothesis, that every formula of degree k+1 is either refutable or satisfiable. It certainly isn't true that, for each Q dependent on the same variables, including, as the "proof" essentially uses, Qs with additional quantifiers, substituting this Q inside ¬Φ will result in a formula which is known to be provable, since Qs with additional quantifiers would make ¬Φ to be of degree > k, and the induction hypothesis, which we are not through with yet, since we haven't yet proved the theorem for formulas of degree k+1, and which is the only reason we know ¬Φ to be provable, covers only those formulas of degree = k. The Wikipedia article, with its "functional substitution" paragraph, is confused on this point.

I'll wait for a while to see whether some other expert comes along with an argument convincing me that my Comment is incorrect. If this doesn't happen fairly soon, I'll reinsert my Comment into the article. If the Comment is again deleted, I'll probably just allow Wikipedia to continue having this article with an incorrect proof and without a correcting comment. BTW, the completeness theorem, whether correct or incorrect, is a very important theorem, or non-theorem, in mathematical logic. Shouldn't the article be given an importance rating of Top, if it is going to be kept in Wikipedia? @Felix QW: Dirsaka (talk) 20:05, 22 January 2022 (UTC)

Don't worry about the completeness theorem; Gödel's original proof is now mainly of historical value, since it has been superseded by the well-known proof by Henkin that one can find in all the main logic/model theory texts. This is also why the priority of this article is "Low", since we have a separate article on the Completeness theorem itself. Felix QW (talk) 22:26, 22 January 2022 (UTC)

The discussions by Avigad etc. that I linked above are all modern reformulations of Gödel's very proof, not new proofs of the same result. Felix QW (talk) 22:27, 22 January 2022 (UTC)

The completeness theorem is important enough and improbable enough that I think there is a need for an understandable detailed proof outline of it in Wikipedia. The W. Completeness theorem article's proof depends on Henkin's model completeness theorem, and the only W. article for that I found presents only a very bare-bones outline of Henkin's proof. The Gödel original proof article gives a much more detailed proof outline of Gödel's supposed proof of his form of the theorem, which, however, may not be valid. You argued for its correctness in your 11:28 comment. Did my 20:05 reply convince you that there is a problem? I will study the Henkin proof, but the Gödel claimed proof needs consideration too. Eagleash, whom I mistakenly bothered about the original proof article edit, on his User Talk page called the insertion of my Comment into the article "Disruptive" and requested that I not reinstate my edit at the article as this would probably be seen as disruptive and could even lead to the loss of editing privileges. (Is it reasonable to consider this as a threat?) Presumably he did this because he considers the edit likely to be incorrect, even though he admits that he probably has less than little knowledge of the article's subject. Do you also consider the edit disruptive? @Felix QW: Dirsaka (talk) 20:02, 25 January 2022 (UTC)

I think the logic may be clearer if you explicitly consider the fact that there are two different formulas before and after the substitution: Let me call them $\Phi _{Q}$ and $\Phi _{P}$.

• The reason we know $\neg \Phi _{Q}$ is provable is the induction hypothesis.
• The reason we know $\neg \Phi _{P}$ is provable is that, we can "translate" a proof for $\neg \Phi _{Q}$ to a proof for $\neg \Phi _{P}$, without ever needing to "unpack" the expression $(\forall u)(\exists v)(P)\psi (x,y|x',y')$.

Bbbbbbbbba (talk) 18:14, 6 April 2023 (UTC)

I will post the proof in a more rigorous and precise way, so that you can understand better why these objections are not valid.

Proof

Let k≥1.

Inductive hypothesis: Every formula in R of degree k is either refutable or satisfiable.

Let $\phi$ be a formula of degree k+1; then we can write it as

$\phi =(\forall x)(\exists y)(\forall u)(\exists v)(P)\psi$

where (P) is the remainder of the prefix of $\phi$ (it is thus of degree k-1) and $\psi$ is the quantifier-free matrix of $\phi$. x, y, u and v denote here tuples of variables rather than single variables.

Let now x' and y' be tuples of previously unused variables of the same length as x and y respectively, and let Q be a previously unused relation symbol that takes as many arguments as the sum of lengths of x and y; we consider the formula

$\Phi =(\forall x')(\exists y')Q(x',y')\wedge (\forall x)(\forall y)(Q(x,y)\rightarrow (\forall u)(\exists v)(P)\psi )$

The deduction chain can be written as follows:

1. $\Phi \implies \phi$, clearly.

2. $(Q(x,y)\rightarrow (\forall u)(\exists v)(P)\psi )\equiv (\forall u)(\exists v)(P)(Q(x,y)\rightarrow \psi )$, since the string of quantifiers $(\forall u)(\exists v)(P)$ does not contain variables from x or y.

3. Since these two formulas are equivalent, if we replace the first with the second inside Φ, we obtain the formula Φ' such that Φ≡Φ':

$\Phi '=(\forall x')(\exists y')Q(x',y')\wedge (\forall x)(\forall y)(\forall u)(\exists v)(P)(Q(x,y)\rightarrow \psi )$

4. We form Ψ as follows:

$\Psi =(\forall x')(\forall x)(\forall y)(\forall u)(\exists y')(\exists v)(P)Q(x',y')\wedge (Q(x,y)\rightarrow \psi )$

5. We have $\Phi '\equiv \Psi$, since Φ' has the form $(S)\rho \wedge (S')\rho '$, where (S) and (S') are some quantifier strings, ρ and ρ' are quantifier-free, and, furthermore, no variable of (S) occurs in ρ' and no variable of (S') occurs in ρ.

6. If $\Psi$ is satisfiable, then, considering $\Psi \equiv \Phi '\equiv \Phi$ and $\Phi \implies \phi$, we see that $\phi$ is satisfiable as well.

7. Now, assume that $\Psi$ is refutable. Then so is $\Phi$, which is equivalent to it; thus $\neg \Phi$ is provable.

8. By "functional substitution" rule of inference (for example), if we replace all occurences of Q(x',y') in $\neg \Phi$ with the formula $(\forall u)(\exists v)(P)\psi (x,y|x',y')$, we obtain another provable formula. So, $\neg \Phi$ becomes

$\neg ((\forall x')(\exists y')(\forall u)(\exists v)(P)\psi (x,y|x',y')\wedge (\forall x)(\forall y)((\forall u)(\exists v)(P)\psi \rightarrow (\forall u)(\exists v)(P)\psi ))$

and this formula is provable. Since the part of the formula after the $\land$ is provable, it trivially follows that $\neg \phi$ is provable, and $\phi$ is refutable.

9. Summarizing, we proved these two implications:

• $\Psi$ is satisfiable $\implies$ $\phi$ is satisfiable (by point 6);
• $\Psi$ is refutable $\implies$ $\phi$ is refutable (by points 7, 8).

10. The implications at point 9 entail the following:

$\Psi$ is satisfiable or refutable $\implies$ $\phi$ is satisfiable or refutable.

But the antecedent of this last implication is true by inductive hypothesis, since $\Psi$ has degree k. This implies that $\phi$ is satisfiable or refutable, and the lemma is proved.

Comment: Observing the point 7, it's evident that "$\neg \Phi$ is provable" follows if $\Psi$ is refutable, so there's no deduction error at all.

Furthermore, the substitution doesn't take place after the theorem has been shown to be true for formulas of degree k+1: at point 7, we assumed that $\Psi$ is refutable and accordingly proved that $\neg \Phi$ is provable. And then, at point 8, the substitution takes place. Finally, at point 10, we used the inductive hypothesis to prove that $\Psi$ is either refutable or satisfiable.

From this, it's clear that the substitution does not invalidate the induction argument, since the inductive hypothesis is never used in the formula obtained by the substitution. The inductive hypothesis is used only at point 10 on $\Psi$, and it is legit. Germanomosconi1 (talk) 16:04, 25 July 2023 (UTC)

Several problems in this article

I was trying to translate the article into Italian, but I've encountered several problems.

First of all, the "Proving the theorem for formulas of degree 1" paragrah is not so clear, especially the last part is very obsure.

In particular, it's not clear how a propositional truth assignment can assign values to formulas with free variables, since free variables have not an interpretation... so it's not clear the meaning of the phrase: "Each i-ary predicate $\Psi$ should be true of the naturals $(u_{1}...u_{i})$ precisely when the proposition $\Psi (z_{u_{1}}...z_{u_{i}})$ is either true in the general assignment", because how the general assignment can assign truth values to formulas like $\Psi (z_{u_{1}}...z_{u_{i}})$, since it contains free variables? Moreover, $\Psi$ is a predicate symbol, but it also represent a formula... how a predicate symbol can represent a formula?

Then, what $(\exists y_{1}...y_{m})\phi (a_{1}^{n}...a_{k}^{n},y_{1}...y_{m})$ means? Why are indices of variables $a_{1}^{n}...a_{k}^{n}$ used as terms in a formula?

It seems that whoever wrote this section doesn't know what he was writing...

Finally, the section "Extension to arbitrary sets of formulas" doesn't seem to make sense: since the formulas are finite strings of symbols, the set of all formulas is countable, so it seems there is no way to have uncountable sets of formulas, unless we allow formulas of infinite length... Germanomosconi1 (talk) 11:39, 22 July 2023 (UTC)

Just regarding the "extension to arbitrary sets of formulas" for now, the signature can be uncountable in general, so that there can indeed by uncountably many formulas of finite length. Felix QW (talk) 07:34, 23 July 2023 (UTC)

But this seems to be impossible by Cantor's theorem... How we can have an uncountable signature, if we can only use a finite number of symbols to represent formulas? And even if we accept to have an infinite countable number of symbols (indexed by naturals), we can also use a finite number of symbols to represent them (digits 0 and 1, for example). But, for example, we can't use the real numbers as symbols, since by Cantor's diagonal argument reals are not indexable by natural numbers, and we should use infinite strings to represent them, so how we can concretely have an uncountable signature? Germanomosconi1 (talk) 09:14, 23 July 2023 (UTC)

I think the issue is that there is nothing in the definition of a signature that requires it to be actually representable in any concrete way. For any set, I can simply define that set to be, say, the set of constants. This is very useful, say, in model theory, where we might want to have a constant for every real or complex number. Felix QW (talk) 10:57, 23 July 2023 (UTC)

But again, this is actually impossible, since we can't have a constant for every real number, unless, again, we allow to consider infinite strings of digits to index the real numbers... Germanomosconi1 (talk) 11:51, 23 July 2023 (UTC)

Then, what $(\exists y_{1}...y_{m})\phi (a_{1}^{n}...a_{k}^{n},y_{1}...y_{m})$ means? Why are indices of variables $a_{1}^{n}...a_{k}^{n}$ used as terms in a formula?

$a_{1}^{n}...a_{k}^{n}$ are not merely indices, they are natural numbers. The notation is commonly used in model theory and signifies that we interpret the variables in the indexed tuple by the elements $a_{1}^{n}...a_{k}^{n}$ of the underlying domain. Felix QW (talk) 07:45, 23 July 2023 (UTC)

I had already understood this, but in this context it seems to be senseless, if you don't solve first the problem that it's not specified how the general assignment give truth values to formulas with free variables... Germanomosconi1 (talk) 09:22, 23 July 2023 (UTC)

An assignment in propositional logic is merely a function mapping propositions into the set {true, false}. Once we define our proposition symbols, we can define an assignment. Of course, propositional logic does not "know" about the intended meaning of the variable symbols. In my opinion, the tricky bit is linking the propositional logic with the first-order proof calculus. The step from refuting an existential formula ($D_{n}$) in the first-order calculus to the existence of a satisfying propositional assignment is terribly vague, but these seems to be a consequence of never actually specifying the first-order calculus for which we claim the statement in the first place. Felix QW (talk) 11:03, 23 July 2023 (UTC)

I think the very issue is the step when we assign a truth value to the subformulas of $D_{n}$: since there are quantified subformulas, this violates the truth-functional evaluation of propositional logic, because obviously the propositional logic does not define a way to assign values to subformulas if there is a quantifier surrounding them... Germanomosconi1 (talk) 12:00, 23 July 2023 (UTC)

The solution to this issue I used in my italian translation is first to assign truth only to closed subformulas, then take every closed subformula surrounded with a quantifier, and assign a truth value to the subformula once removed the quantifier, but substituting the free variable obtained by removing the quantifier with the natural representing the index of the variable, in this way:

Given a formula in the assignment of the form $X=\exists z_{u}F$:

• if $X$ is true, then the formula $F[z_{u}/u]$ will be true;
• if $X$ is false, then the formulas $F[z_{u}/l]$ will be false, for every integer $l\geq 1$.

The assignment must then also be extended to the subformulas using the rules of propositional logic, and using the rule just described in the case of formulas that begin with an existential quantifier. Germanomosconi1 (talk) 12:07, 23 July 2023 (UTC)

The above solution didn't convince me, so the final solution I adopted for italian version is as follows:

If $D_{n}$ is refutable for some n, it follows that φ is refutable. On the other hand, suppose that $D_{n}$ is not refutable for any n. Then for each n, the formula $D'_{n}:=B_{1}\land \dots \land B_{n}$ is not refutable. This property must be a direct consequence of the rules of deduction, otherwise the system could not guarantee its completeness.

Then for each n, there is some way of assigning truth values to the distinct subformulas $E_{h}$ (ordered by their first appearance in $D'_{n}$; "distinct" here means either distinct predicates, or distinct bound variables) in $B_{k}$, such that $D'_{n}$ will be true when each proposition is evaluated in this fashion. This follows from the completeness of the underlying propositional logic.

We will now show that there is such an assignment of truth values to $E_{h}$, so that all $D'_{n}$ will be true: The $E_{h}$ appear in the same order in every $D'_{n}$; we will inductively define a general assignment to them by a sort of "majority vote": Since there are infinitely many assignments (one for each $D'_{n}$) affecting $E_{1}$, either infinitely many make $E_{1}$ true, or infinitely many make it false and only finitely many make it true. In the former case, we choose $E_{1}$ to be true in general; in the latter we take it to be false in general. Then from the infinitely many n for which $E_{1}$ through $E_{h-1}$ are assigned the same truth value as in the general assignment, we pick a general assignment to $E_{h}$ in the same fashion.

This general assignment must lead to every one of the $B_{k}$ and $D'_{k}$ being true, since if one of the $B_{k}$ were false under the general assignment, $D'_{n}$ would also be false for every n > k. But this contradicts the fact that for the finite collection of general $E_{h}$ assignments appearing in $D'_{k}$, there are infinitely many n where the assignment making $D'_{n}$ true matches the general assignment.

From this general assignment, which makes all of the $D'_{k}$ true, we construct an interpretation of the language's predicates that makes φ true. The universe of the model will be the natural numbers. Each i-ary predicate $\Psi$ should be true of the naturals $(u_{1}...u_{i})$ precisely when the atomic proposition $\Psi (z_{u_{1}}...z_{u_{i}})$ is either true in the general assignment, or not assigned by it (because it never appears in any of the $D'_{k}$).

In this model, each of the formulas $(\exists y_{1}...y_{m})\phi (a_{1}^{n}...a_{k}^{n},y_{1}...y_{m})$ is true by construction. But this implies that φ itself is true in the model, since the $a^{n}$ range over all possible k-tuples of natural numbers. So φ is satisfiable, and we are done. Germanomosconi1 (talk) 01:19, 24 July 2023 (UTC)

I think the above solution is clear and rigorous enough for the purposes of this article. Germanomosconi1 (talk) 16:34, 24 July 2023 (UTC)

Secondary sourcing

Given the confusion about the proof as presented here, I would just like to point out again that there are in fact several good expositions of the proof in secondary sources:

1. Avigad's essay, which is apparently a slightly updated transcription of a lecture presented to the Association for Symbolic Logic in May, 2006.
2. The chapter by van Attan and Kennedy in The History of Logic
3. The introduction to the collected works edition of Gödel's thesis (https://antilogicalism.com/wp-content/uploads/2021/12/Godel-1.pdf, p. 50 onwards)
4. The explanatory power of a new proof: Henkin’s completeness proof by John Baldwin (publisher version: https://link.springer.com/chapter/10.1007/978-3-319-93342-9_9 )

The general sourcing rules on Wikipedia mandate that we should follow the secondary sources in our interpretation and exposition of the proof, so the fact that the page currently does not even mention any source beyond Gödel's original works is a problem. Felix QW (talk) 08:53, 3 August 2023 (UTC)

I hope I have finally resolved the dispute with Dirsaka on my talk page. Germanomosconi1 (talk) 11:03, 3 August 2023 (UTC)

Dirsaka's objection to proof of reduction to formulas of degree 1

Since I could not resolve the dispute with @Dirsaka on my talk page, I repost here the objection argument, and also I explain why it's incorrect, at least for me. I do this because I'm sure that anyone else who knows formal logic will agree with me.

In the proof linked here, it's used the "functional substitution" rule of inference to get a provable formula from the formula

$\neg \Phi =\neg [(\forall x')(\exists y')Q(x',y')\wedge (\forall x)(\forall y)(Q(x,y)\rightarrow (\forall u)(\exists v)(P)\psi )]$

The rule is set out in Principles of Mathematical Logic, ch. III, par. 5 by David Hilbert (1950), exactly as follows:

"Under certain circumstances, a predicate variable with $n$ argument places may be replaced by a formula which contains at least $n$ free individual variables. Let $F$ be the $n$-adic predicate variable, and ${\mathfrak {A}}$ the formula in which $F$ is to be replaced. From among the individual variables occurring in the formula which is to replace $F$, we select any $n$ whatsoever ordered in any arbitrary way, say, $x_{1},x_{2},\dots ,x_{n}$. The formula which is to be substituted will accordingly be designated by ${\mathfrak {B}}(x_{1},x_{2},\dots ,x_{n})$. The substitution is now permissible only if the remaining free individual variables which may still occur in ${\mathfrak {B}}(x_{1},x_{2},\dots ,x_{n})$ do not occur in the formula ${\mathfrak {A}}$ as bound variables, and if, further, there is no occurrence of $F$ in ${\mathfrak {A}}$ such that a variable occupying an argument place in $F$ occurs as a bound variable in ${\mathfrak {B}}(x_{1},x_{2},\dots ,x_{n})$, provided always that the result of the substitution is a formula. The substitution is accomplished as follows: Considering any specific occurrence of the predicate variable $F$ in ${\mathfrak {A}}$, we find the argument places of $F$ occupied by certain individual variables, which we designate, for the moment, by ${\mathfrak {a}}_{1},{\mathfrak {a}}_{2},\dots ,{\mathfrak {a}}_{n}$. These need not all be different. We now replace $F({\mathfrak {a}}_{1},{\mathfrak {a}}_{2},\dots ,{\mathfrak {a}}_{n})$, at this occurrence of $F$, by ${\mathfrak {B}}({\mathfrak {a}}_{1},{\mathfrak {a}}_{2},\dots ,{\mathfrak {a}}_{n})$, i.e. by the formula obtained from ${\mathfrak {B}}(x_{1},x_{2},\dots ,x_{n})$ when the variables $x_{1},x_{2},\dots ,x_{n}$ are replaced, wherever they occur, by ${\mathfrak {a}}_{1},{\mathfrak {a}}_{2},\dots ,{\mathfrak {a}}_{n}$ respectively. The corresponding substitution is to be made at every occurrence of $F$."

In our case, we have ${\mathfrak {A}}:=\neg \Phi$, $F:=Q$, and ${\mathfrak {B}}(x,y):=(\forall u)(\exists v)(P)\psi$, where $x$ and $y$ are tuples of variables, which have been selected.

Now, @Dirsaka is sure that, in this case, the substitution is not permissible, because, as he says: "there are remaining free individual variables which still occur in ${\mathfrak {B}}(x,y):=(\forall u)(\exists v)(P)\psi$ and also they occur in the formula ${\mathfrak {A}}$ as bound variables". But this is clearly a misinterpretation of the rule, since it's clear that by "remaining free individual variables which may still occur in ${\mathfrak {B}}(x_{1},x_{2},\dots ,x_{n})$" the author intended not the all free variables, but instead the unselected free variables; otherwise, why Hilbert (or the translator) would use the word "remaining"? There would be no need, he could only say "free variables occurring in the formula". Furthermore, why the author wrote "which may still occur"? If he meant the all free variables, it's obvious that they still occur! So, it's clear that, at least in my opinion, the objection raised is completely meaningless. @Felix QW @Bbbbbbbbba Germanomosconi1 (talk) 22:37, 3 August 2023 (UTC)

Reply to Germanomosconi1

I put a reply to Germanomosconi1 on the bottom of his Talk page, dated 19:32, 3 August 2023 (https://en.wikipedia.org/wiki/User_talk:Germanomosconi1), the first paragraph of which is a deductively valid argument whose premises are both clearly true and which, I think, Germanomosconi1 would agree are true, and whose conclusion is that the substitution is not now permissible (with "permissible" having the meaning it has in the rule, the Hilbert functional substitution rule). The premises of that argument don't include any unlikely-to-be-true claims about the word choice of Hilbert or the translator, in particular about "remaining free variables" in the Hilbert substitution rule. This phrase clearly means those variables (in 𝔅) which are still free, i.e., are unbound (by the quantifiers in 𝔅). Dirsaka (talk) 18:40, 6 August 2023 (UTC) Dirsaka (talk) 10:20, 8 August 2023 (UTC) Dirsaka (talk) 22:32, 24 August 2023 (UTC)

No, I do not agree with the premises of your argument. I could also prove to you that my interpretation is the correct interpretation with an argument of model theory, but I won't do it, since anyone that knows enough of formal logic (not you, clearly) can see for himself that it is correct. Germanomosconi1 (talk) 15:30, 8 August 2023 (UTC)

Anyway, the proof sketch is as follows.

Consider the formula ${\mathfrak {B}}(x_{1},\dots ,x_{n})$, where $x_{1},\dots ,x_{n}$ are any $n$ variables, ordered in any arbitrary way, selected from among the free individual variables occurring in the formula ${\mathfrak {B}}(x_{1},\dots ,x_{n})$.

Fix any structure $M=\langle U,I\rangle$ and any assignment $\eta \colon vars\to U$ for the individual variables of the language.

For any tuple $(e_{1},\dots ,e_{n})\in U^{n}$, we redefine $\eta$ for the variables $x_{1},\dots ,x_{n}$ as the following assignment:

$\eta [x_{1},\dots ,x_{n}/e_{1},\dots ,e_{n}](v):={\begin{cases}e_{i},&{\text{ if }}v=x_{i}{\text{ for some }}i\in \{1,\dots ,n\}\\\eta (v),&{\text{ otherwise}}\end{cases}}$

Now, we can define an $n$-ary relation $R_{M,\eta }\subseteq U^{n}$ as follows:

$R_{M,\eta }:=\{(e_{1},\dots ,e_{n})\in U^{n}\mid M,\eta [x_{1},\dots ,x_{n}/e_{1},\dots ,e_{n}]\models {\mathfrak {B}}(x_{1},\dots ,x_{n})\}$

Clearly, this relation is well defined, since the structure $M$ is fixed, and also the intepretation of the unselected free variables is fixed by the assignment $\eta$.

Now, take a valid formula ${\mathfrak {A}}$, containing occurrences of an $n$-ary predicate variable $F$.

Since ${\mathfrak {A}}$ is valid, then any arbitrary structure and any arbitrary assignment satisfies ${\mathfrak {A}}$. Since we can choose any structure we want, this means that we can also interpret the symbol $F$ with whatever $n$-ary relation we want, since there are no restriction in the structure $M=\langle U,I\rangle$ and in the assignment $\eta$ that we choose. But this entails that we can interpret $F$ as $R_{M,\eta }$, i.e. we can take $I(F):=R_{M,\eta }$ (clearly, the symbol $F$ cannot occur in the formula ${\mathfrak {B}}(x_{1},\dots ,x_{n})$, otherwise $I(F)$ may be ill-defined due to self-reference, although this is not a real problem for the substitution: since the validity of a formula doesn't depend by the names of its distinct predicates, we can rename $F$ in ${\mathfrak {A}}$ with another symbol not yet appeared).

This implies that, provided that no unselected free variables of ${\mathfrak {B}}(x_{1},\dots ,x_{n})$ are bound in ${\mathfrak {A}}$ (and the others provisos of the rule), if we replace the symbol $F$ with the formula ${\mathfrak {B}}(x_{1},\dots ,x_{n})$ as described in Hilbert's rule, we obtain another valid formula, since replacing $F$ with ${\mathfrak {B}}(x_{1},\dots ,x_{n})$ is equivalent to forcing to interpret $F$ as the relation $R_{M,\eta }$, by its own definition. This is relatively easy to show by structural induction on formulas.

The unselected free variables must not be bound in ${\mathfrak {A}}$ because, otherwise, their interpretation is no longer fixed by the assignment $\eta$, but it is varied by quantifiers, and so it is no longer correct to interpret ${\mathfrak {B}}(x_{1},\dots ,x_{n})$ as $R_{M,\eta }$.

As you can see, there's no need for the variables $x_{1},\dots ,x_{n}$ to be not bound in ${\mathfrak {A}}$, also because they can be renamed in ${\mathfrak {B}}(x_{1},\dots ,x_{n})$ with other distinct variables $y_{1},\dots ,y_{n}$ which don't even appear in ${\mathfrak {A}}$ and in ${\mathfrak {B}}(x_{1},\dots ,x_{n})$, and using ${\mathfrak {B}}(y_{1},\dots ,y_{n})$ in the substitution instead of ${\mathfrak {B}}(x_{1},\dots ,x_{n})$ you get EXACTLY THE SAME resulting formula, but obviously $y_{1},\dots ,y_{n}$ are not bound in ${\mathfrak {A}}$. Germanomosconi1 (talk) 16:57, 8 August 2023 (UTC)

So, in the light of the last paragraph of my previous answer, I would say that we can definitively close the question on the applicability of the rule. Germanomosconi1 (talk) 13:10, 9 August 2023 (UTC)