Skip to content

Infinite Sets…I see it, and now, I believe it.

November 16, 2012

Symbols of infinity from Wikipaedia

I have been exploring the idea that infinite sets might not exist. This is suggested by Prof. N. Wildberger found in his youtube sermons here. It is interesting that the preaching ties the existence of an infinite set to our ability to write it down. Is this some kind of extreme construtivist teaching or something?

Indeed Georg Cantor must have been considered a heretic when he preached on the idea of infinite sets in the late 19th century. Today, for sure it is part of math’s orthodox doctrine.
It so happened that I am studying model theory too and as I reflected on this, I asked myself what model theory might say about this issue.

Getting out my copy of D. Marker’s Model Theory: An Introduction I accidentally  stumbled on his Example 1.2.1 (Infinite Sets) and it goes like this…

Consider the language \mathcal{L}={0}, that means no functions, relations nor constants. Consider now the theory of  \mathcal{L} where we have, for each n, the sentence \phi_n=\exists x_1 \exists x_2 \exists x_3...\exists x_n \bigwedge\limits_{i \leq j < n}x_i \neq x_j.  This says that there are at least n distinct elements. Then a structure \mathcal{M} is a model for this theory iff the carrier set/universe of \mathcal{M}, called M is infinite.

This is not obvious and the example showed no proof. However, I will try to show why M must be infinite.

Proof:

(\Rightarrow)

We only prove in this direction. For a contradiction, assume there is a model \mathcal{M} \models T=\{ \phi_n\mid n \in \mathbb{N} \} but M is finite.

M being finite implies it is of finite cardinality k, i.e., |M| = k. We know that

\forall k \in \mathbb{N} , there \exists q \in \mathbb{N} such that q > k. For example, q = k + 1 . I think this step is often called “without loss to generality”;-)

Then we can always set n = q. Consider now the definition of satisfiability,  \mathcal{M} a model of T. By definition of satisfaction this implies \exists a_1, \exists a_2, \exists a_3,...\exists a_q . \mathcal{M} \models\bigwedge\limits_{i \leq j < k + 1}a_i \neq a_j. This says that \exists a_q,  which  says there is an a_{k+1}th element in M. This is a contradiction, for we said that the number of elements of M is k. This implies that \phi_n can not be satisfied by the structure \mathcal{M}, thus it is not a model, a contradiction.

\therefore \; M must be infinite.

The proof for (\Leftarrow) follows a similar line.

Q.E.D.

About these ads
No comments yet

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: