Skip to main content
Commonmark migration
Source Link

Short answer

###Short answer YesYes, 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.

###Long answer

Long answer

###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.

###Long answer

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.

Long answer

Source Link
David Richerby
  • 82.2k
  • 26
  • 144
  • 238

###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.