Why is "there no way in pure logic to write a single statement expressing that there are an infinite number of objects with a certain property"?

Question

In his A Mathematical Tour Through Logic, Wolf states in Section 1.3, Quantifiers, that

… there is no way in pure logic to write a single statement expressing that there are an infinite number of objects with certain property.

Now consider the statement “there are countably infinite even natural numbers.”($\Bbb{N}$ includes $0$ and can be constructed from $\emptyset$.)
Can’t we restate it in formal symbolic language as $\forall n\in \Bbb{N}\,\exists\, 2n$?

Also, what does he mean by pure logic? (He is yet to formalise first-order logic.)

Answer 1

You cannot prove the existence of the set of natural numbers, defined as a smallest set containing $0=\varnothing$ and closed under the operation $S(a)=a \cup \{a\}$ using just pure logic. You need to assume the axiom of infinity from Zermelo-Fraenkel set theory, that is, you need to assume that there exist at least one infnite set. That axiom does not belong to "pure logic".

Answer 2

I haven't read that text, but presumably by "pure logic", Wolf means something like "in first-order logic with no particular non-logical axioms assumed". That would mean you can't assume that you have numbers or sets.

What Wolf means (though it's a bit poorly worded, at least given just that extract) is say that we have some predicate symbol $P$ so that $P(t)$ means $P$ holds of the term $t$. This predicate symbol corresponds to some arbitrary, unknown "property". There is no single formula in (classical) first-order logic (with equality) that states that $P$ holds for some unknown infinite collection of objects.

To be clear, it's quite easy to make theories that imply that there must be an infinite number of objects, and you can even ensure a predicate holds of infinitely many of them. To use your example, we can add part of Peano Arithmetic to our theory and then add axioms which state that $P(0)$ holds and $P(s(s(n))$ holds whenever $P(n)$ holds, i.e. we'd add the axioms $P(0)$ and $\forall n.P(n)\to P(s(s(n)))$. This would ensure that $P$ holds for, at least, all even numbers. Rather than asserting this, we could "ask" this with the formula $P(0)\land(\forall n.P(n)\to P(s(s(n))))$ which is true if $P$ holds for all even numbers. The problem is what if $P$ holds for all odd numbers? That formula becomes false but $P$ still holds for an infinite number of objects. In other words, I can describe with formulas some infinite classes of objects, but checking that formula only checks that $P$ does or does not hold on those classes of objects, not on any infinite class of objects.

It's easier (for me) to consider what the negation of such a formula would state which is that there's a formula involving $P$ that states that $P$ holds only for an unknown, finite collection of objects. We can't do this either. We can write something like $$\exists x,y.\forall z.P(z)\leftrightarrow (z=x\lor z=y)$$ which would mean $P$ holds for at most $2$ values. We can do this for any given number of objects, but we'd need an infinite number of them to cover every possibility. To stick them all together with disjunctions would produce an infinitely long formula which isn't allowed by definition.

The typical proof I've seen of the above facts uses a property of first-order logic called compactness. It states that given any collection of axioms, possibly infinite, it has a model if and only if each finite subset of the collection of axioms has a model. Now say $\varphi$ is the formula that states that $P$ holds for finitely many objects. Write $\psi_n$ for the formula that states that $P$ holds for at least $n$ values. The negation of the earlier formula would be $\psi_3$. Consider the theory consisting of $\varphi$ and $\psi_n$ for all natural numbers $n$. This has no model since a set that has greater than $n$ elements for any natural number $n$ is infinite and thus $\varphi$ wouldn't hold. However, for any finite subset of axioms, there is a largest $n$ such that $\psi_n$ is in that subset (unless it's just $\{\varphi\}$ in which case take $n=0$), and this subset of axioms has a model whenever $P$ is interpreted as a subset of the domain with at least $n$ elements. This means the existence of the formula $\varphi$ contradicts compactness.

Answer 3

Partial answer. Don't know about countably infinite.

… there is no way in pure logic to write a single statement expressing that there are an infinite number of objects with certain property.

Suppose we have a unary predicate $P$ and binary predicate $F$ such that:

$\forall a:[P(a)\implies \exists b: [P(b) \land [ F(a,b) \land\forall c:[P(c) \implies [F(a,c) => c=b]]]]]$

$\land \forall a,b,c:[P(a)\land P(b)\land P(c) \implies [F(a,b) \land F(c,b) \implies a=c]]$

$\land \exists a:[P(a) \land \forall b:[P(b) \implies \neg F(b,a)]]$

Then there must exist infinitely many $x$ such that $P(x)$.

The above is based on a definition equivalent to that of Dedekind's definition of an infinite set. $F$ is a function on the domain $P$ (line 1), a function that is injective (line 2), but not surjective (line 3).

For countably infinite you probably will need either infinitely many axioms (an axiom schema) or set theory for the required Principle of Mathematical Induction.

Answer 4

Whatever Thor means by pure logic, I am confident that it would rule out being able to use quantifiers that explicitly refer to the natural numbers. Thus, your

$\forall n\in \Bbb{N}\,\exists\, 2n$

by which I assume you meant:

$\forall n\in \Bbb{N}\,\exists m \in \Bbb{N}: m= 2n$

will not be allowed.

Moreover, if instead you use:

$\forall n\,\exists m : m= 2n$

then this does not at all force any model to be of infinite size: You could have a universe with one object, denoted by $2$, and for which it holds that $2 \cdot 2 = 2$

Now, it is in fact quite easy to force any model to be infinite. Take the first two Peano Axioms, for example:

$\forall x : x \not = 0$

$\forall x \ \forall y : (s(x) = s(y) \to x = y)$

These can only be satisfied by an infinite sized domain .. and by adding $\forall x : P(x)$, any model would thus need to have infintily many objects with property $P$.

Hmmm, but that would seem that Thor was not correct? Well, at this point, go read Derek Elkins' excellent answer to understand what exactly Thor meant.