5
$\begingroup$

While I am learning a lot from others here at the Computer Science site, I must admit that I don't get as much out of some questions and answers since I typically don't understand the theorems to the level necessary. I am currently reading How To Prove It - A Structured Approach which is starting to make the theorems easier to read, but still does not get me to the point of being able to understand the theorems to the point that they add great insight to the question or answer.

For this question Is it possible to always construct a hamiltonian path on a tournament graph by sorting?

there is a use of a peroid in the premise.

$\qquad \displaystyle a \leq b \iff (a,b) \in E \lor \left(\exists\, c \in V. a \leq c \land c \leq b\right)$

What does the period mean? I would be expecting either a comma to mean conjuction or or to mean disjunction, but not a period. I don't see how this could be converted to logical statements.

Note: Jukka Suomela has already provided the answer in this CS meta question.

$\endgroup$
7
$\begingroup$

After an $\exists$ the period can be read as "such that". For example, $\exists x\in \mathbb{N}. x>4$ can be read as "there exists a natural $x$ such that $x$ is greater than 4."

After a $\forall$ it can be read as "it is the case that". For example, $\forall x\in\mathbf{N}. x + 1> x$ can be read as "for all natural numbers $x$, it is the case that $x+1$ is greater than $x$.

Generally one can omit "it is the case that" and the sentence still works.

$\endgroup$
  • 2
    $\begingroup$ I would also like to add this: "The symbolism of formal logic is indispensable in the discussion of the logic of mathematics, but used as a means of transmitting ideas from one mortal to another it becomes a cumbersome code." Of course it is good to know how to parse logical formulas, no matter which variant of the syntax people happen to use, but this is not a good example of mathematical writing. If you want to say "there is an $x$ such that...", then say so. :) $\endgroup$ – Jukka Suomela Jul 31 '12 at 14:27
  • $\begingroup$ In other words, the period just serves to separate the name of the variable bound by the quantifier (and its base set), that is $x \in N$, from the applied predicate ($x > 4$). You can use any symbol that is not overloaded. Note how this is similar to $\mid$ in set expressions like $\{x \in N \mid x > 4\}$. $\endgroup$ – Raphael Jul 31 '12 at 16:31
  • 1
    $\begingroup$ @JukkaSuomela: That is, of course, a matter of taste. At least when formulae become more complicated (rule of thumb: both $\forall$ and $\exists$) I dislike verbose constructions of ambiguous natural language immensely; they are hard (sometimes impossible) to parse into rigorous statements. Experts often miss this, because they "know" what is said. Also, it promotes sloppiness and accidents. A good presentation contains both an accessible natural language formulation and a precise formula, imho. $\endgroup$ – Raphael Aug 2 '12 at 7:02
  • $\begingroup$ hmm, long strings of funky symbols are the only path to rigor? I disagree. People can write bad English, but they can also write nonsense formulas. The formula in the question is a prime example of lazy writing. For every jumble of $\forall\exists\ni\forall\exists$, there exists an easier to parse prose paragraph (see what I did there?) $\endgroup$ – Sasho Nikolov Aug 2 '12 at 8:42

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.