# Describability of a set

As Wikipedia says, there are two ways to describe a particular set: intensional definition and extensional definition.

1. For a set able to be described by extensional definition, is it necessary and sufficient to say the set has to be countable? Do there exist sets that are not describable by extensional definition?
2. For a set able to be described by intensional definition, is this equivalent to existence of a predicate to specify the membership of the set?

As "there are only countably many predicates you can actually write down (or even possible at all with a countable alphabet)" (from a comment after this reply, courtesy of Arturo Magidin), are there only countable number of sets that can be described by intensional definition? Do there exist sets that are not describable by intensional definition?

3. Are there other ways for describing a set other than intensional definition and extensional definition?

4. Do there exist sets that are not describable ?

Thanks and regards!

-
It's not clear to me that either of these terms have well-defined or unique meanings in set theory. – Qiaochu Yuan Jan 11 '11 at 23:26
@Tim: Wouldn't the set of all bachelors be a set describable by extensional definition? You just list all the people that are bachelors. – PEV Jan 11 '11 at 23:32
@Qiaochu: Assuming you are talking about intensional definition and extensional definition. AFAIK, intensional definition and extensional definition are just ways of giving definitions. Here they are used to describe set but not define set. – Tim Jan 11 '11 at 23:33
@Trevor: in set theory, the set of all bachelors is not a set. For example, in ZFC the only elements of sets are other sets. Like I said, I am not sure that "intensional" and "extensional" are well-defined notions in set theory. In particular, it is far from clear to me what it means to give an extensional definition of an infinite set. – Qiaochu Yuan Jan 11 '11 at 23:33
@Trevor: extensional definition of a set is to list all elements of the set. – Tim Jan 11 '11 at 23:34

The thing is, in common practice within set theory, we use parameters in our descriptions, so actually any set can be given intentionally, though not necessarily in an interesting way: $a=\{x\mid x\in a\}$. This is not so useless as it first appears. For example, every set in Goedel's constructible universe $L$ is definable using as parameters "simpler" sets, and this is an important feature of $L$ that allows us to analyze it in detail, being ultimately responsible for the fact that $L$ satisfies the axiom of choice.

As already pointed out, if we only use parameter-free formulas, then we can only describe intentionally countably many sets.

As for extensional descriptions, by the most strict of interpretations, only countable sets can be described this way and, really, we need some explicit way of mentioning their elements. Of course, in practice, we usually write things like $A=\{a_0,a_1,\dots\}$ and I would say this is as extensional as it gets, though of course it is an intentional definition $A=\{a_i\mid i\in{\mathbb N}\}$ in disguise, and even this only makes sense if we have a function $i\mapsto a_i$ to begin with.

Of course, we usually write sets by listing them as $A$ above, even if the sets are not countable, by considering well-orderings, i.e., we write their elements as a long sequence (indexed by some not necessarily countable ordinal). Under choice, any set can be listed that way.

I think this idea of "extensional" and "intentional" (or "by comprehension") definitions of sets is a bit of an unintended consequence of the "new math" idea of teaching set theory in schools. So, rather than talking about the axiom of extensionality, that sets are completely determined by their elements, somehow we ended up writing sets by their extensions (i.e., by listing their elements), and rather than talking about the axiom scheme of comprehension, we ended up writing sets by comprehension. Very strange. (I (still) remember being 9 or so and my teacher asking me to write the empty set intentionally. I don't remember my teacher ever explaining how to do this. That was very confusing to me. I guess at that age, writing $\phi$ was akin to saying that $\phi$ had to hold, so the idea of writing a property $\phi(x)$ that fails for all $x$ was completely foreign.)

-
Thanks! (1) When defining a set by "a={x∣x∈a}", isn't that already a kind of definition fallacy "circular definition"? i.e. define "a" using "a" before it is defined. So people still define a specific set this way? (2) "As for extensional descriptions, by the most strict of interpretations, only countable sets can be described this way" " if we have a function i↦ai to begin with", I think a set being countable means there exists an injective function from N to the set and how to construct the function is a different issue? – Tim Jan 12 '11 at 1:00
Hi Tim. I am not sure what you mean by a fallacy here. The equality $a=\{x\mid x\in a\}$ is certainly true. As I said, it is kind of useless, in that it gives you no information about $a$, but it is not incorrect. It is not an equation with unique solution $a$, though. And there is a slight technical point here. In ZFC we define classes intentionally but allow parameters in the descriptions. The fact that any set can be written in this silly way shows that any set is a class. A proper class is a class that is not a set' for example $V$, the class of all sets (by Russell's paradox). – Andrés E. Caicedo Jan 12 '11 at 1:06
I think your definition of countable reversed an arrow somewhere: $A$ is countable iff there is an injection from $A$ into ${\mathbb N}$. If $A$ is countable, and infinite, then there is also an injection from ${\mathbb N}$ into $A$, and in fact a bijection, but this is a theorem, not a definition. Sets $A$ for which there is an injection from ${\mathbb N}$ into $A$ are called Dedekind infinite and, under the axiom of choice, this is the same as infinite. Countable, on the other hand, is more restrictive. It says that in a sense the set is small (even if it happens to be infinite). – Andrés E. Caicedo Jan 12 '11 at 1:09
Thanks! For definition fallacy, I mean en.wikipedia.org/wiki/Fallacies_of_definition , and it is logical fallacy. For circular definition, I mean en.wikipedia.org/wiki/Circular_definition . I agree with you a={x∣x∈a} is a true equality, because every set satisfies it. But I cannot imagine if it is used to define a (therefore unique) set, because that would be circular definition, a fallacy it is. Or am I wrong? Do people really use it to define a set (either a specific set or a general set)? – Tim Jan 12 '11 at 1:24
Thanks! You are right about "countable", except that AFAIK the existence of an injection from A into N is the definition of A being countable, as cardinality of a set is defined in terms of such injective function. Am I wrong? – Tim Jan 12 '11 at 1:29

For any reasonable definition of "describable," the answer to #4 has to be "yes." In fact, for any reasonable definition of "describable," it should be true that almost all sets (in an appropriate sense) are not describable.

Let's take our sets to be sets in ZFC, and let's say that a set in ZFC is describable if its elements are precisely the sets $x$ satisfying a predicate $p(x)$. The correspondence between describable sets and predicates is not perfect because some (possibly most) predicates describe classes, not sets, but in any case there are at most as many describable sets as predicates in ZFC. But there are only countably many such predicates, and the class of sets is so large that it is not a set (that is, it does not have a well-defined cardinality in ZFC). So the vast majority of sets are not describable by such a predicate.

-
In fact, the situation is worse than this: the vast majority of subsets of the natural numbers are not describable. More or less equivalently, the vast majority of real numbers are not describable. Maybe the clearest illustration of this basic principle in set theory itself is that at most countably many ordinals are describable. Try to describe the ordinals, in order; it is very, very hard. – Qiaochu Yuan Jan 11 '11 at 23:46
Can I say by "describable", you mean only "intensional definition" (or equivalently "description by predicate"?) not "extensional definition"? Are only countable sets describable ty extensional definition, and can there be countably many countable sets? – Tim Jan 11 '11 at 23:49
@Tim: Note that a set is describable if its elements (which are sets) $x$ satisfy $p(x)$. There seems to be no formalization of "intensional" or "extensional." – PEV Jan 11 '11 at 23:53
Edited: by "Are only countable sets describable ty extensional definition, and can there be countably many countable sets?", I wanted to say "assume only countable sets describable ty extensional definition, and can there be UNcountably many countable sets? " – Tim Jan 11 '11 at 23:57
@Tim: like I said, you still have not provided a definition of extensional definition. The one I'm thinking of has the property that every set definable by an extensional definition can also be defined by an intensional definition. Does yours? – Qiaochu Yuan Jan 12 '11 at 0:01