6
$\begingroup$

I ask, because I have to come up with a first-order logic sentence that shows that there are exactly N objects in the universe. What I've been able to come up with is:

$$ \forall x \; \exists y_1, y_2, \dots , y_{n-1} \; (x \neq y_1) \land (x \neq y_2) \land \dots \land (x \neq y_{n-1})$$

I'm not sure if this is a valid first-order logic sentence or not.

$\endgroup$
  • $\begingroup$ Your sentence doesn't define the property you want. For any $n$, your sentence is satisfied by the set $\{0,1\}$: for any $x\in\{0,1\}$, set $y_1=\dots=y_{n-1}=1-x$ $\endgroup$ – David Richerby Apr 29 '15 at 8:27
10
$\begingroup$

Strictly speaking, your statement is invalid because $\ldots$ is not part of the syntax of first-order logic. However, your statement is an abbreviation of a statement in first-order logic. For example, when $n = 3$, your statement is an abbreviation of the bona fide statement $$ \forall x, \exists y_1, y_2 (x \neq y_1) \land (x \neq y_2). $$ As long as you understand this difference, you can use the statement. Your statement is stated in the metalanguage, and it corresponds to a bona fide statement of the language.

Here is a similar example. The following defines a number, for every integer $n \geq 1$: $$ \overbrace{11\cdots 1}^{\text{$n$ times}} $$ For example, when $n = 5$, this number is $11111$. While the notation above, which belongs to the metalanguage, is not in itself a valid number, for every specific $n$ it satisfies a valid number. You can think of it as a pattern, a number scheme (in your case, a statement scheme), or a function that takes $n$ and outputs a number (in your case, a statement).

That said, your statement (for every $n > 1$) states that there are at least two different objects in the universe. So while it is a valid statement, it doesn't state what you intended it to.

$\endgroup$
  • $\begingroup$ So, if you can't use ellipses in first-order logic, is it possible to even write that sentence? $\endgroup$ – Colin Apr 29 '15 at 0:20
  • 2
    $\begingroup$ Definitely, for every $n$ you can write the sentence explicitly. For example, when $n = 5$ it is $\forall x, \exists y_1,y_2,y_3,y_4 (x\neq y_1) \land (x\neq y_2) \land (x\neq y_3) \land (x\neq y_4)$. What you wrote is like a function that takes $n$ as input and spits as output the sentence corresponding to your choice of $n$. $\endgroup$ – Yuval Filmus Apr 29 '15 at 0:24
  • $\begingroup$ Your statement says nothing about the uniqueness of $y_1$ and $y_2$. What if $y_1 = y_2$? $\endgroup$ – Francesco Gramano Apr 29 '15 at 0:26
  • 2
    $\begingroup$ Why the downvote? $\endgroup$ – Yuval Filmus Apr 29 '15 at 4:32
  • 3
    $\begingroup$ @J.-E.Pin That would be a poor reason for downvoting, since Yuval's answer already acknowledges that fact. The fact that the formula in the question doesn't actually state what it's supposed to state is a side-issue. The question is about whether it's OK to use "$\dotsc$", not whether the formula in the question actually states what it's supposed to state. $\endgroup$ – David Richerby Apr 29 '15 at 10:11
5
$\begingroup$

Short answer

Yes, you can use ellipses, as long as it is absolutely clear what they mean. In the example in your question, it is absolutely clear what the ellipses mean.

Note. The formula does not, in fact, express the property that the domain has exactly $n$ elements but this is a side-issue: your question was explicitly about the use of ellipses.

Long answer

Question 1. Is $\{1, \dots, 10\}$ a set of natural numbers?

Interpreting the question literally, the answer is no. A set of natural numbers is a set all of whose elements are natural numbers. The elements of this set are one, ten, and dot-dot-dot: only the first two of those are natural numbers.1 But we can all, I think, agree that $\{1, \dots, 10\}$ represents a set of natural numbers: specifically, the set $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$. The ellipsis isn't an element of the set: it's a short-hand we use when writing about sets. Everybody knows that it means "fill in the gap using the obvious pattern" and we've been conditioned to find intervals of the natural numbers obvious.2 Speaking a little more formally, the ellipsis is part of the metalanguage: the language we use to write down, describe and talk about sets.

Question 2. Is $\{1, \dots, n\}$ a set of natural numbers?

Literally, no. Neither dot-dot-dot nor the letter $n$ is a natural number. We've already discussed what the ellipsis is but what is $n$? $n$ is some kind of variable: it stands for something. We'd better restrict it to stand for a natural number because whatever $\{1, \dots, \sqrt{2}\}$ might mean, it certainly isn't a set of natural numbers. However, for every natural number $n$, $\{1, \dots, n\}$ represents a set of natural numbers.

Question 3. Let $\varphi_n\equiv \forall x \exists y_1 \cdots \exists y_{n-1}\,(x\neq y_1)\land \dots \land (x\neq y_{n-1})$. Is $\phi_n$ a formula of first-order logic?

OK, you know the drill by now. Literally no but, for any fixed natural number $n$, $\varphi_n$ is a formula. Now, at this point, I'd like to take issue with either the exercise you were set or your summary of what it says. There is no formula of first-order logic that says "The domain has exactly $n$ elements." Why? Because, as stated, $n$ is a free variable of the formula. It turns out that, even if your domain contains some encoding of the natural numbers, there is no formula you can write of the form $\psi(S,n)$ that is true if, and only if, $|S|=n$.3 What you can do is write a family of sentences $\varphi_1, \varphi_2, \dots$ such that, for each $n$, $\varphi_n$ is true if, and only if, the domain contains exactly $n$ elements.

Here, $n$ is a variable in the metalanguage and you might have noticed a pattern: I'm quibbling with statements in which it's a free variable of the metalanguage and guiding towards statements where it's bound. It doesn't make sense to talk about $\varphi_n$ in isolation, but only in a context where $n$ is defined. You're not really "writing down $\varphi_n$" but, rather, giving a recipe that lets your reader figure out what $\varphi_n$ is once they've decided what $n$ is.

So, to summarize, ellipses (and $n$s and so on) are not literally part of first-order logic. They're tools in the metalanguage that allow you to describe formulas. In the example I gave above, each of $\varphi_1$, $\varphi_2$, $\varphi_{2376}$ etc. is a formula that can, in principal, be written down without ellipses. However, $\varphi_n$ isn't literally a formula: it's sort of a recipe for writing down a formula once you've decided on a value for $n$. It describes a family of formulas with increasing numbers of variables and increasing quantifier depth. As such, it's not going to be possible to write down the "recipe" for such a family without using metalanguage devices such as ellipses.


1 Let's just agree that $1$ is a natural number, rather than being just a representation of some intrinsic concept of "one-ness". Philosophical logic worries about such things; mathematical logic doesn't.

2 Note that this is very much a human construct. There is no unique way of filling in the ellipsis in $\{1, \dots, 10\}$. I might be a jerk who's written that for the set of roots of the polynomial $(x-1)(x-3)(x-7)(x-10)$ but you, and all reasonable readers, assume I'm not a jerk (thanks! I appreciate that) and that I meant $\{i\in\mathbb{N}\mid 1\leq i\leq 10\}$.

3 This can be proven by various means, such as Ehrenfeucht–Fraïssé games or, as I recall, compactness.

$\endgroup$
  • $\begingroup$ "the answer is no" -- I think that falls short. The important thing is that even mathematics can be viewed as syntax and semantics, even though mathematician rarely put it that way (and, in my experience, don't see it that way either). The string $\{1,\dots,n\}$ can be defined to mean the same as $[1..n]$ or $\{ i \mid 1 \leq i \leq n\}$, and I think the common, implicit semantics of mathematics support that. You do need some shorthand if you want express infinite and arbitrarily large things in a finite way. $\endgroup$ – Raphael Apr 29 '15 at 14:34
  • $\begingroup$ To make my point: in order to see if and why such a formula is not FOL for free $n$ (it is for fixed $n$!) one has to dig deeper than ignoring that syntax is just syntax. $\endgroup$ – Raphael Apr 29 '15 at 14:34
4
$\begingroup$

Assuming you work with the usual definition of FOL, no, that iss not a syntactically valid formula. "$\dots$" does not appear in the formal grammar specifying the language.

However, "$\dots$" is commonly and implicitly accepted as a shorthand. As long as it is clear how to fill the gap with finitely many symbols, it is for many purposes¹ fair to save ink and time. This is to say that there is a reasonable extension to the formal language that is FOL and its semantics that would make such formulae valid. For instance, one could say

$\qquad\displaystyle \exists\, y_{[a..b]} : \varphi$

is a FOL formula if $\varphi$ is, and $1 \leq a \leq b$ natural numbers. We can easily define the semantics by noting that

$\qquad \exists\, y_{[a..b]} : \varphi \equiv \begin{cases} \exists\, y_b : \varphi, & a=b;\\ \exists\, y_a : \exists\,y_{[a+1..b]} : \varphi, & a < b. \end{cases}$

Note that we implemented "$\dots$" by recursion, and that the "unfolded" formula for any $a$ and $b$ is a FOL formula by the usual definition.

Keep in mind that this only works for fixed $[a..b]$, or in your case, fixed $N$. If it's not fixed, then you implicitly say

$\qquad\displaystyle \exists\,A \subseteq \mathbb{N} : \exists\,y_A : \varphi$.

Here you quantify over sets, and that is not within the power of FOL.


  1. Not always: if you work with a proof assistant or any other automated system, you probably don't get to do this without rigorously defining all your shorthands.
$\endgroup$
0
$\begingroup$

Your question was: find a first-order logic sentence stating that there are exactly $n$ objects in the universe. The following formula should work: $$ \exists x_1\ ... \exists x_n\ \Bigl(\bigwedge_{1 \leqslant i < j \leqslant n} \neg(x_i = x_j)\Bigr) \wedge \forall x \ \Bigl(\bigvee_{1 \leqslant i \leqslant n} (x = x_i)\Bigr) $$ Intuitively, the first part of the sentence says that there exist at least $n$ distinct elements and the second part says there is no more than $n$ elements.

$\endgroup$
  • $\begingroup$ There's still an ellipsis, and I'm not sure $\bigwedge$ and $\bigvee$ are usually part of FOL syntax. (They are a reasonable extension.) $\endgroup$ – Raphael Apr 29 '15 at 9:38
  • $\begingroup$ @Raphael The ellipsis is unavoidable as long as $n$ is not given explicitely. But if $n$ is given, say $n = 5$, then you can just convert the formula to an explicit one. In other words, the formula I gave is a proof of existence of a sentence for every fixed $n$. I think this is very well accepted in logic. $\endgroup$ – J.-E. Pin Apr 29 '15 at 9:50
  • 1
    $\begingroup$ My point is, the question is all about the ellipsis, less so about how to write that statement as formula. (I agree that using ellipses without fixed $n$ is fair and unavoidable.) $\endgroup$ – Raphael Apr 29 '15 at 14:30

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.