Intereting Posts

vanishing ideal of product of two affine varieties
Integral domain without unity has prime characteristic?
Basis for rank $n$ ring containing $1$.
What is degree of freedom in statistics?
Using the Residue theorem or Fourier transform to solve this integral
Proof that a Combination is an integer
Enough Dedekind cuts to define all irrationals?
Why does $x= \frac{1}{2}(z+\bar{z}) = \frac{1}{2}(z+\frac{r^{2}}{z})$ on the circle?
Probability of a random $n \times n$ matrix over $\mathbb F_2$ being nonsingular
partition a number N into K tuples
An interesting series
MVT for integrals: strict inequality not needed before applying IVT?
Does $a!b!$ always divide $(a+b)!$
Difference between $\sum$ and $\int$
Lambert W function with rational polynomial

In Stephen Cole Kleene, *Mathematical Logic* (1967 – Dover reprint : 2002) there is a counterexample to the rule : $”A(x)\vdash\forall xA(x)”$.

The counterexample is (pag.110):

we are not justified in saying $”R \rightarrow P(y) \vdash R \rightarrow \forall x P(x)”$. In fact, this is not true, since [by soundness, is not the case that] $”R \rightarrow P(y) \vDash R \rightarrow \forall x P(x)”$ were true.

- Illustrative examples of a phenomenon in the logic of mathematical induction
- What's the difference between material implication and logical implication?
- Should this “definition” of set equality be an axiom?
- Gödel, Escher, Bach: $ b $ is a power of $ 10 $.
- In classical logic, why is $(p\Rightarrow q)$ True if $p$ is False and $q$ is True?
- Truth Tables for Digital Circuits

Elliott Mendelson, *Introduction to Mathematical Logic* (4th ed – 1997) uses the *generalization rule*; trying the same example in Mendelson’s system, we have :

1) $R \rightarrow P(y)$ — assumption

2) $R$ — assumption

3) $P(y)$ — 1,2 MP

4) $\forall yP(y)$ — 3,Gen

5) $R \rightarrow \forall yP(y)$ — 2,4 by Deduction Th ($y$ not free in $R$)

Is it correct ? Of course, I cannot have : $\vdash (R \rightarrow P(y)) \rightarrow (R \rightarrow \forall yP(y))$ because now $y$ is free in $R \rightarrow P(y)$ and so DT does not apply.

May I say that this is acceptable in Mendelson’s system because in it the deducibility relation ( $\vdash$) tracks *validity* and not *logical consequence* (according to Mendelson definition) ?

- Avoiding circular logic using L'Hospital's rule
- Logical Form - Union of a Set containing the Power Set with Predicate/Propositional Function
- Meaning of symbols $\vdash$ and $ \models$
- Who invented $\vee$ and $\wedge$, $\forall$ and $\exists$?
- First Order Language for vector spaces over fields
- Some questions about Gödel's theorems of completeness and incompleteness
- Existence of elementary substructures of a uncountable structure over a countable language
- Logic, set theory, independence proofs, etc
- Problem on ultrafilters
- expressability of finite and infinite ramsey theorems in Peano arithmetic

I think that the correct answer needs a careful comparison of Kleene’s system [*Mathematical Logic*, 1967] and Mendelson’s one [*Introduction to Mathematical Logic*, fourth ed, 1997], regarding the relation, in the respective systems, between the two notion of consequence : the syntactical one ($\vdash$) and the semantical one ($\vDash$).

First of all, both authors define in the same way “validity” and “logical consequence”.

In Kleene’s system the “basic” quantifier rule is the $\forall$-rule [see Th.16, pag.96] :

if $\vdash C \rightarrow A(x)$ then $\vdash C \rightarrow \forall xA(x)$ , (x not free in $C$).

According to Kleene’s remark [pag.110],

we are not justified in saying $”R \rightarrow P(y) \vdash R \rightarrow \forall x P(x)”$. In fact, this is not true, since [is not the case that] $”R \rightarrow P(y) \vDash R \rightarrow \forall x P(x)”$ were true.

This counterexample shows that we are not licensed to read the $\forall$-rule as :

$C\rightarrow A(x) \vdash C \rightarrow \forall xA(x)$.

Accordingly, Kleene’s system derives the (weak) Gen-rule : “if $\vdash A(x)$ then $\vdash \forall xA(x)$”, where the strong one : “$A(x) \vdash \forall xA(x)$” is not allowed (because unsound).

In Mendelson’s system, instead, Gen-rule is the strong one : “$A(x) \vdash \forall xA(x)$”, so that the above derivation is correct; in Mendelson’s system we have that :

$R \rightarrow P(y) \vdash R \rightarrow \forall x P(x)$

(but, of course, not $\vdash (R \rightarrow P(y)) \rightarrow (R \rightarrow \forall x P(x))$, due to the restrictions of the Deduction Theorem).

The main difference between the two systems is that in Kleene’s book we have that :

$A \vdash B$ iff $A ⊨ B$.

This is not true , in general, for Mendelson’s system; in it we have (for example) :

$P(x) \vdash \forall xP(x)$ , by Gen,

but not : $P(x) \vDash \forall xP(x)$ ,

by the “usual” counterexample [the domain of the interpretation is the set of natural numbers, the interpretation of $P$ is the property “is even” and take as assignement to the free variable $x$ the number $2$].

See also George Tourlakis, *Lectures in Logic and Set Theory, Volume 1 : Mathematical Logic* [2003], pag.50 (footnote) :

In Mendelson (1987) $\vDash$ is defined inconsistently with $\vdash$.

- Old AMM problem
- How to prove $1$,$\sqrt{2},\sqrt{3}$ and $\sqrt{6}$ are linearly independent over $\mathbb{Q}$?
- Why complete measure spaces?
- Proving that a definition of e is unique
- When a 0-1-matrix with exactly two 1’s on each column and on each row is non-degenerated?
- Prove that $x^2 = – 1$ has no solution in $\mathbb{Z}$
- If $\mu$ is a probability measure on $\mathbb R$, is $t\mapsto\mu\{t\}$ differentiable almost everywhere?
- About the limit of the coefficient ratio for a power series over complex numbers
- The only finite group which can act freely on even dimensional spheres is $C_2$.
- Noetherian ring whose ideals have arbitrarily large number of generators
- Prove an interpolation inequality
- Interchanging pointwise limit and derivative of a sequence of C1 functions
- Polynomial passing through two points with specific tangents
- Decomposing a discrete signal into a sum of rectangle functions
- system of equations