2

On https://de.wikipedia.org/wiki/Pr%C3%A4nexform a set of slides (lecture material in German) is cited. On slide 6 the following tautology is written:

$(\exists x B \rightarrow A) \leftrightarrow \forall x (B \rightarrow A) \quad x \notin \mathrm{Free}(A) $

I have difficulties to understand the meaning of this.

Currently I read

  • $\exists x B \rightarrow A$: There is at least one $x$ such that $B \rightarrow A$.
  • $\forall x (B \rightarrow A)$: The implication $B \rightarrow A$ holds for all $x$.

In my understanding the second assertion is much more general. Couldnt it be the case that there is only one $x$ (say $x=0$) such that B implies A?

Example: B: "$y$ is a polynomial of degree $x$", A: "$y$ is a constant number".

Where is my fallacy?

cknoll
  • 437
  • 2
    Probably the placement of parentheses is important. The first formula thus should be $(\exists x:B)\implies A$. – Berci Oct 01 '21 at 09:59
  • What berci said. An example of the first expression would be "if one of my hands is holding an umbrella, then it is raining". – DanielV Oct 01 '21 at 09:59
  • 2
    ∃xB→A does not read "There is at least one x such that B→A", it reads "If there is at least one x such that B, then A". Your sentence corresponds to ∃x(B→A) instead. Since x is not free in A then A does not depend on x. So if some x makes B imply A then B must imply it regardless of what x is. – Conifold Oct 01 '21 at 10:22
  • I always thought that the precedence/scope rules of $\forall$ and $\exists$ are vague, in particular with implication and equivalence. Probably best to use parentheses and not assume that the writer and the reader agree about the rules! – Jukka Kohonen Oct 01 '21 at 10:53
  • $∀x(B→A)$: "Couldnt it be the case that there is only one x (say x=0) such that B implies A?" We have to read correctly the formula; following your example we have (say) $B(0)$ True and $B(0) \to A$ also True that means that $A$ is True also. Now, to say that $B(1) \to A$ is False means that $B(1)$ is True and $A$ is False, contradicting the previous fact ($A$ does not have $x$ free) . Conclusion; the only case for $\forall x (Bx \to A)$ being False is when $A$ is False and $Bx$ True for some object, in which case also $\exists x Bx \to A$ is. – Mauro ALLEGRANZA Oct 01 '21 at 12:17

1 Answers1

1

Example: B: "y is a polynomial of degree x", A: "y is a constant number".

Let's stipulate that the degree of a polynomial is a natural number.

Then $(\exists x.Bx) \to A$ becomes:

$$(B(0) \lor B(1) \lor B(2) \dots) \to A$$

Which by definition of B is $\text{true} \to A$, which is just $A$.

Also, $\forall x . (Bx \to A)$ becomes

$$(B(0) \to A) \land (B(1) \to A) \land (B(2) \to A) \dots$$

which becomes

$$\underbrace{(\text{true} \to A)}_\text{One of these} \land \underbrace{(\text{false} \to A) \land (\text{false} \to A) \dots}_{\infty \text{ of these}}$$

Which again simplifies to just $A$.

DanielV
  • 23,556
  • I guess it boils down to $(\exists x B \rightarrow A)$ is the same as $(\exists x. Bx) \rightarrow A$ or shorter $(\exists x. B) \rightarrow A$? This obviously depends on operator precedence which I seemingly not respected sufficiently ... – cknoll Oct 01 '21 at 10:31
  • 1
    @cknoll - obviously $(∃xB→A)$ is the same as $(∃xBx)→A$ and not $∃x(B→A)$ – Mauro ALLEGRANZA Oct 01 '21 at 12:44
  • @cknoll I am not aware of any standardization. Sometimes, in math, you gotta ask yourself "what makes more sense" and just go with that. – DanielV Oct 01 '21 at 13:03