4
$\begingroup$

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!

  • 0
    @Tim: I don't think this is a useful definition. There are uncountably many, say, countable subsets of the natural numbers, most of which cannot be described in any meaningful way.2011-01-12

2 Answers 2

6

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.)

  • 0
    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?2011-01-12
4

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.

  • 0
    @Tim: the thing about describing sets in ZFC is that their elements are also sets, so it is not enough to require that the sets are finite; for any set a, the set {a} is a finite set with a single element, but the set a itself may have infinitely many elements. So any reasonable definition of "finite" should include not only the elements, but the elements of the elements, etc. This leads to the definition of a hereditarily finite set: http://en.wikipedia.org/wiki/Hereditarily_finite_set2011-01-12