0

In Example 9 of section 17 of 'First Order Mathematical Logic' by Angelo Margaris, it is stated that:

In this example from number theory, we show what can happen if the restriction on gen ($v$ is not free in $\Delta$) is violated.

  1. $x < 2$ (as)
  2. $\forall x(x < 2)$ (gen)

... The error occurs at step 2. Since $x$ is free in the assumption $x < 2$, gen cannot be applied with $x$ until this assumption is discharged...

What does $x < 2$ mean as an assumption if it does not mean that for every $x$ in the domain of discourse $x < 2$ is true?

user695931
  • 517

2 Answers2

1

Comment : in the calculus, on open formula is not "implicitly" universally quantified.

Consider :

1) $x=2$ (as)

2) $∀x(x=2)$ (gen) --- wrong !

3) $x=2 \to ∀x(x=2)$ --- from 1) and 2) by $\to$-intro (or Deduction Th, or Conditional Proof)

4) $∀x (x=2 \to ∀x(x=2))$ (gen) --- correct

5) $2=2 \to ∀x(x=2)$ --- from 4) instantiating the quantified variable $x$.

Mauro ALLEGRANZA
  • 94,169
  • This is a good example. I think I also worked it out in my comments on coffeemath's answer. The assumption $x = 2$ or $x < 2$ is just restricting the values that $x$ can take, in the same manner that an assumption like $P \to Q$ in propositional logic restricts the truth values that $P$ and $Q$ can take? – user695931 Feb 21 '17 at 07:21
  • @user695931 - More or less... The issue is that the assumption $x<2$ put a constraint on the variable $x$: it must be "read" as a temporary name for the number $2$. This is why it is wrong to generalize it: if we use it (in the context of the proof) to "name" $2$, we are not licensed to assert of $x$ "facts" that do not hold for the number $2$. – Mauro ALLEGRANZA Feb 21 '17 at 07:40
  • 1
    Do you mean the assumption $x = 2$? – user695931 Feb 21 '17 at 07:58
  • So in general we should read an assumption $P(x)$ as restricting the objects from the domain of discourse that the variable $x$ can take in the deduction to those that make $P(x)$ hold true? This is clearly different than saying that all objects from the domain of discourse will make $P(x)$ hold true. – user695931 Feb 23 '17 at 07:22
  • @user695931 - Correct. Consider different math "equations": if we have the identity $(x^2-1)=(x-1)(x+1)$, it holds for every $x$. But if we have $x^2-1=0$ we are not asserting that it holds for every $x$... what we say when we write it on the blackboard is that it holds for some $x$. – Mauro ALLEGRANZA Feb 23 '17 at 07:28
0

In "gen" one can go from $\Delta$ to $\forall v \Delta,$ provided $v$ is not free in $\Delta,$ the latter meaning that $\Delta$ cannot contain $v$ as a free variable.

Ex: OK to say given $ \exists a (a>2)$ that it follows $\forall x \exists a (a>2).$ In this case the $x$ is not free in the $\exists a (a>2).$

The problem that can arise is when the variable generalized over is "free" in the statement over which generalization is to be done, since before the generalization the statement is only about one specific case, while after generalization it would be saying true for all cases of the generalizing variable.

You might want to look up the topic of "free and bound variables" which is a subtopic of quantifier theory.

coffeemath
  • 29,884
  • 2
  • 31
  • 52
  • How would you interpret the statement $x < 2$ by itself? – user695931 Feb 21 '17 at 04:33
  • Should $x < 2$ be read as 'We can choose an $x$ such that $x < 2$.'? If so, how is that different than $\exists x (x < 2)$? – user695931 Feb 21 '17 at 05:17
  • That is, why not write it in the proof as $\exists x (x < 2)$. – user695931 Feb 21 '17 at 05:24
  • Does it just mean that we are restricting the variable $x$ in the proof to values less than $2$? – user695931 Feb 21 '17 at 05:49
  • Sorry, I guess I am rambling here. I think my last comment makes the most sense. It would be in line with interpreting an assumption in propositional calculus like $P \to Q$ as a restriction on the combination of truth values that $P$ and $Q$ can take. – user695931 Feb 21 '17 at 06:03
  • This would imply that we can not get $\exists x (x < 2)$ from the assumption $x < 2$. Correct? – user695931 Feb 21 '17 at 06:05
  • In fact we can not get either $\exists x(x < 2)$ or $\forall x(x < 2)$ from the assumption $x < 2$. – user695931 Feb 21 '17 at 06:10
  • No, I guess we can get $\exists x(x < 2)$? – user695931 Feb 21 '17 at 06:32
  • But then in this interpretation of $x < 2$ as an assumption, what would $P \land \lnot P$ mean as an assumption? That $P$ can not take on either truth value? – user695931 Feb 21 '17 at 06:47
  • @user695931 - Correct : if we have the assumption $∃x(x<2)$, we can assume for $∃$-elim : $(x<2)$, but we cannot generalize it (again due to the fact that $x$ is free in the assumtpion $(x<2)$) because otherwise, as you correctly say, we can derive the invalid $∃(x<2) \to ∀x(x<2)$. – Mauro ALLEGRANZA Feb 21 '17 at 07:43