0
$\begingroup$

Basically, in predicate logic, do we read from the inside outwards? In the example question, would 1a) be read as "For all values of y, there exists a value of x which divides y"? I've been told different things from different lecturers and online, I'm not quite sure what to do.

For example, would 1c) be "For some values of y, every value of x divides into it" (and hence is false)

Any help is appreciated! Thanks

example question

$\endgroup$
  • $\begingroup$ "There is an $y$ such that, for every $x$, ($x$ divides $y$)". In other words : is it true that there is a number (call it $y$) that is divided by every number ? $\endgroup$ – Mauro ALLEGRANZA Mar 31 at 8:31
0
$\begingroup$

Formulas in propositional and predicate logic are defined recursively. You can decompose them into terms and logical connectives by writing them as a Beth tree.

To answer your question, we read from left to right, but due to the recursive definition things can get a bit messy when conjunctions/disjunctions are involved (which is not the case in your examples). In your case 1c, we start from the left, so there is some $y$ (we fix this in the back of our mind). Now we are given any $x$ (this is the $\forall x$ part). In particular, $y + 1$ could be chosen for $x$. But it's clear that $P(y+1,y)$ is false for all positive integers. Hence the sentence is false.

For example, would 1c) be "For some values of y, every value of x divides into it" (and hence is false)

Yes. As an aid, think of $\exists$ as "I pick a specific number" and $\forall$ as "You give me any number you like". Then $\exists y \forall x P(x,y)$ turns into "I pick some $x$, you give me any $y$ you like, and $x$ divides $y$".

$\endgroup$
0
$\begingroup$

You read neither from inside to outside or vice versa. Rather, you have to understand how to parse the syntax first. "$∀x ( P(x) )$" means "for every $x$ it is true that $P(x)$", where $P(x)$ can be any sentence about $x$, which may include its own quantifiers. The outer brackets are there to show you what the quantifier "$∀x$" governs. If you're just starting out, you should always write the brackets. For example, think carefully what "$∀x ( ∀y ( x=y ∨ ¬∃z( x=z ∧ y=z ) ) )$" means, based on what I said about the brackets.

It is necessary for you to first understand what the quantifier syntax I described above means, before you move on to other syntax like the one in your question. The reason is that the underlying structure is the same; you must be able to identify exactly what each quantifier governs. Consider why we can omit some brackets in the above example. "$x=z ∧ y=z$" actually means "$(x=z) ∧ (y=z)$", but why? It's because we stipulate some precedence rules, namely that we 'evaluate' operations with higher precedence first before those with lower precedence. Conventionally, the precedence rules for boolean operations and equality is:

(highest to lowest) $=,¬,∧,∨,⇒$.

Similarly we could include precedence rules for quantifiers, but I personally don't recommend dropping any brackets except for "$∀x ∃y ( P(x,y) )$" meaning "$∀x ( ∃y( P(x,y) ) )$". But for the sake of reading what others write, the precedence rule typically is that each quantifier governs the shortest possible part following it, so the last example becomes just "$∀x ∃y P(x,y)$".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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