Is there a set for which no defining formula can be found?

93 Views Asked by At

I saw this question, but since (1) it's a little unclear (in fact, it has even been closed as unclear), (2) I'm not familiar enough with the terminology of the answer to judge wheter or not it answers my question and (3) it's old enough for me to assume the commenters won't respond to it, I thought it would be better to ask.

In the book I've been using to study set theory, the author enunciates the Intuitive Principle of Abstraction in the very first chapter:

A formula $P(x)$ defines a set $A$ by the convention that the members of $A$ are exactly those objects $a$ such that $P(a)$ is a true statement.

Thinking a bit more deeply into it, I noticed the author said nothing of the converse. That is, nothing was said if the following statement is true:

For every set $A$ there is a formula $P(x)$ which defines it.

So, here I ask you all: is that statement true? Are there sets for which we can find no formula?

1

There are 1 best solutions below

12
On BEST ANSWER

Fact 1: Since a formula must be of finite length, and our alphabets are finite, the are only countably many formulas.

Fact 2: We usually assume (mostly implicitly) that there are uncountably many sets.

Assuming these two facts, we can conclude that the answer is yes, there must be sets without a defining formula. But we can't describe a single one of them.