4
$\begingroup$

Normally on dba stackexchange, I am looking for assistance in transforming these statements into English.

Negating Quantified Predicates

Not all $x$ in $P(x)$ in Universe (is true if) $x$ exists in Universe for which not $P(x)$

I attempted to resolve the first one using Math Symbols but this surely isn't the best way to learn.

So my first question is a request for help translating the above. Second question is also a request for any "useful" advice on understanding how to transform these statements into English.

The image comes from Itzik Ben Gan's book on TSQL.

Thank you in advance.

Update 28/08/2013

I am adding this image as another attempt at translating the first statement. Perhaps this will help to identify what I'm trying to accomplish.

enter image description here

$\endgroup$
2
  • $\begingroup$ What level of English are you after? The first can be written 'not all possible x satisfy P, iff at least one possible x does not satisfy P', with iff meaning 'if and only if'. $\endgroup$ – android.weasel Aug 28 '13 at 12:40
  • $\begingroup$ @android.weasel Just "English" enough to be able to continue reading Itzik's booK. Every attempt I've made to write out these statements has failed using my current wikipedia method. $\endgroup$ – Craig Efrein Aug 28 '13 at 12:43
3
$\begingroup$

The way those sentences are translated into English depends on the exact meaning of $\Leftrightarrow$: either it's the object-language material implication ($\equiv$ or $\leftrightarrow$) or the meta-theoretic "if...then." I've given translations for each interpretation. I think you're asking about the second, but just to be safe.

$\lnot (\forall x \in U(P(x)) \Leftrightarrow \exists x \in U (\lnot P(x))$

  • (in the object-language): It's not the case that for all x in U, P holds of x: if and only if for some x in U, P doesn't hold of x.

  • (in the meta-language): "It's not the case that for all x in U, P holds of x" is true if and only if "for some x in U, P doesn't hold of x" is true.

$\forall x \in U (P(x)) \Leftrightarrow \lnot(\exists x \in U(\lnot P(x))$

  • (in the object-language): For all x in U, P holds of x: if and only if it's not the case that for some x in U, P doesn't hold of x.

  • (in the meta-language): "For all x in U, P holds of x" is true if and only if "it's not the case that for some x in U, P doesn't hold of x" is true.

$\lnot(\exists x \in U (P(x)) \Leftrightarrow \forall x \in U (\lnot P(x))$

  • (in the object-language): It's not the case that for some x in U, P holds of x: if and only if for all x in U, P doesn't hold of x.

  • (in the meta-language): "It's not the case that for some x in U, P holds of x" is true if and only if "for all x in U, P doesn't hold of x" is true.

$\exists x \in U (P(x) \Leftrightarrow \lnot(\forall x \in U (\lnot P(x)))$

  • (in the object-language): For some x in U, P holds of x: if and only if it's not the case that for all x in U, P doesn't hold of x.

  • (in the meta-language): "For some x in U, P holds of x" is true if and only if "it's not the case that for all x in U, P doesn't hold of x" is true.

Generally, first-order formulas are pretty straightforward to translate. Use "it's not the case that" for complex negated sentences, "in" for the membership relation, "holds of" for function or predicate application, and some type of consistent notation for avoiding ambiguities (I like to use colons, but semicolons might also be acceptable).

$\endgroup$
2
  • $\begingroup$ thank you for your answer, I will get back to you shortly. $\endgroup$ – Craig Efrein Aug 29 '13 at 7:01
  • $\begingroup$ oh, no problem :) Good luck with SQL. $\endgroup$ – Hunan Rostomyan Aug 29 '13 at 9:14

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.