2
$\begingroup$

I read it as "Everyone is either a student or has read every book". But what's the use of the existential y outside the bracket?

R(x, y): “x has read y.” S(x): “x is a student.” Domain for x: all people Domain for y: all books ∀x∃y(S(x) ⋁ ∀yR(x, y)) 

2 Answers 2

5

Indeed, your intuition is correct about the extra existential quantifier. We have, per your post:

$R(x, y)$: “x has read y.”

$S(x)$": “x is a student.”

Domain for $x$: all people. $\quad$Domain for $y$: all books $\forall x \exists y(S(x) \lor \forall y(R(x,y)))\tag{1}$

Was this exactly how you encountered the problem? If so, are you trying to translate? Or are you trying to express a statement?

Assuming that you encountered this, as is, your translation would be correct if there were no $\exists y$ outside the parentheses. However, it may also serve as an example of how the closest quantifier to the quantified variable "overrides" any earlier quantification, in which case you are correct in your translation (with $\forall y$ over-riding $\exists y$ since it is closest to the quantified variable y), so $(1)$ can be expressed by:

$\forall x (S(x) \lor \forall y(R(x,y))) \equiv \forall x \forall y(S(x) \lor R(x,y))\tag{2}$

So I'd agree that, as is, the statement reads: "Everyone is either a student or has read every book."


Note: If the intent is to say (the highly unlikely) "Every student has read every book", we would write:

$\forall x(S(x) \implies \forall y(R(x,y))) \equiv \forall x \forall y(S(x) \implies R(x,y))\tag{3}$

If the intent is to express (the most likely case) "Every student has read some book", we would write:

$\forall x(S(x) \implies \exists y(R(x,y))\ \equiv \forall x \exists y(S(x) \implies R(x,y))\tag{4}$

Finally, we can express the unlikely case: (5)"There is a student who has read every book" or the trivial case (6)"There is a student who has read some book", we could write, respectively $\exists x(S(x) \land \forall y(R(x,y))) \equiv \exists x \forall y(S(x) \land R(x,y))\tag{5}$ $\exists x (S(x) \land \exists y(R(x,y)))\equiv \exists x\exists y(S(x) \land R(x,y)))\tag{6}$

If nothing else, the above demonstrates how the order and placement(scope) of quantifiers and the quantified variables is crucial, as is the choice of quantifier used.

  • 1
    @gallais Yup...I just didn't want to confuse the OP... :-)2012-11-05
0

(i) Where did the stray existential quantifier come from?

Putting things into Loglish -- that useful logic/English mix we use informally in the logic classroom -- for "Everyone is either a student or has read every book" we have

For any person $p$(either $p$ is a student or, for any book $b$, $p$ has read $b$).

If you are allowed sorted variables, so $p$ is runs over people and $b$ runs over books, then you could indeed write

$\forall p((Sp \lor \forall b(Rpb)))$

But don't use $x$ and $y$ for differently sorted variables!

(ii) Note though that , in standard first order logic (as taught to beginners) variables are not sorted: all your quantifiers in a particular sentence or argument must run over the same domain, and you need to explicitly restrictive clauses in order to render sorted quantifications. So we have to further unpack the Loglish like this to get a single domain:

Everything x is such that (if x is a person, then either x is a student or everything $y$ is such that (if $y$ is a book, $x$ has read y)).

So now you just need to use the official logical notation for that!

$\forall x(Px \to (Sx \lor \forall y(By \to Rxy)))$

  • 0
    "loglish" - I like that! :)2012-11-04