In these notes (page 18, section 1.3.7)

1.3.7 Variables Over One Domain

When all the variables in a formula are understood to take values from the same nonempty set, $D$, it’s conventional to omit mention of $D$. For example, instead of $\forall x \in D \ \exists y \in D.\ Q(x, y)$ (1) we’d write $\forall x \exists y.\ Q(x, y)$ (2). The unnamed nonempty set that $x$ and $y$ range over is called the domain of discourse, or just plain domain, of the formula.

It’s easy to arrange for all the variables to range over one domain. For example, Goldbach’s Conjecture could be expressed with all variables ranging over the domain $\mathbb{N}$ as

$$\forall n.(n \in Evens) \implies (\exists p\ \exists q. p \in Primes \land q \in Primes \land n = p + q).$$

Now I have two questions

  1. It doesn't make sense to me that (2) is the same thing as (1). Omitting the name of the set makes me think that (2) is actually more general, so what are reasons that I shouldn't think that?

  2. Could you please explain the second paragraph in more detail?


We can approach FOL from a "pure" syntactical way, where :

$\exists x \forall y Q(x,y)$

has no "built-in" reference to the domain of the interpretation.

The same formula can be interpreted in different domain, with diofferent "meaning".

Consider for example the binary predicate $\le$ as interpretation for the predicate symbol $Q$.

Now the above formula is :

$\exists x \forall y (x \le y)$.

We can interpret it in the domain $\mathbb N$ of natural numbers, and we have that :

$\mathbb N \vDash \exists x \forall y (x \le y)$

i.e. the formula is satisfied in it, because we have taht the number $0$ is "less-or-equal" than any natural number $n$.

If instead we interpret it in $\mathbb Q$, the same formula is not satisfied any more, i.e. :

$\mathbb Q \nvDash \exists x \forall y (x \le y)$

because there is no rational number which is less-or-equal than any rational number $q$.


Regarding the "formalization" of Goldbach’s Conjecture, we can omit all the reference to domain and subdomains, simply introducing suitable predicates :

$∀n[(Even(n) \land n > 2) \to ∃p ∃q(Prime(p) ∧ Prime(q) ∧ n=p+q)]$.

Now all variables "range over" the same domain; Goldbach’s Conjecture is the assertion that the above formula holds in $\mathbb N$, i.e. that :

$\mathbb N \vDash ∀n[(Even(n) \land n > 2) \to ∃p ∃q(Prime(p) ∧ Prime(q) ∧ n=p+q)]$.

  1. If you're pedantic, you'd say that (2) just doesn't make sense really because from my understanding mathematics is based on a proper treatment of sets and logical quantors. Beginning to omit them for the sake of saving a few symbols isn't worth the confusion you risk by doing so. In that sense (2) is just a notation/convention where you say "if it is clear from the context that we're working on a set $D$, then we might omit it in (1) as well and just write (2)".

  2. The second paragraph basically follows the idea (instead of explaining it in detail I'll make an example to illustrate it): If you have sets $D_1$ and $D_2$ and maybe a statement like $$ \exists x\in D_1 \ \forall y\in D_2: Q(x,y) $$ then you can simply define $D := D_1 \cup D_2$ as the union of these two sets and rewrite the above expression as $$ \exists x \in D: \left( x \in D_1 \wedge \forall y\in D: \left(y\in D_2 \Rightarrow Q(x,y)\right) \right), $$ which by the above notation is the same as $$ \exists x: \left( x \in D_1 \wedge \forall y: \left(y\in D_2 \Rightarrow Q(x,y)\right) \right). $$ And you can do just the same with the Goldbach conjecture. If you do not immediately see why these expressions are the same, it is perfectly okay $-$ it's just unnecessarily complicated to rewrite it this way.


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.