[Solved]: Can I use ellipses in first order logic

Problem Detail: 

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.

Asked By : Colin

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41935

3.2K people like this

 Download Related Notes/Documents