Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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))
share|improve this question
add comment

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
    
yeah, thats how it was in the PDF i downloaded. thanks man! –  Bulbo Nov 3 '12 at 15:12
    
« So I'd agree that, as is, the statement reads: "Everyone is either a student or has read every book and the set of books is non-empty." » FTFY –  gallais Nov 5 '12 at 17:18
1  
@gallais Yup...I just didn't want to confuse the OP... :-) –  amWhy Nov 5 '12 at 17:57
add comment

(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)))$

share|improve this answer
    
"loglish" - I like that! :) –  amWhy Nov 4 '12 at 15:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.