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
    It's not clear to me that either of these terms have well-defined or unique meanings in set theory.2011-01-11
  • 0
    @Tim: Wouldn't the set of all bachelors be a set describable by extensional definition? You just list all the people that are bachelors.2011-01-11
  • 0
    @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.2011-01-11
  • 0
    @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.2011-01-11
  • 0
    @Trevor: extensional definition of a set is to list all elements of the set.2011-01-11
  • 0
    @Tim: yes, that's the problem (to me). What does it mean to list the elements of an infinite set?2011-01-11
  • 0
    @Qiaochu: So couldn't we take each "set" to be a bachelor?2011-01-11
  • 0
    @Qiaochu: I guess the extensional definition makes sense only for countably infinite sets. So you have to find a bijective function between the set $S$ and $\mathbb{N}$.2011-01-11
  • 0
    @Qiaochu: I guess list by enumeration? "An extensional definition, also called a denotative definition, of a concept or term specifies its extension. It is a list naming every object that is a member of a specific set." http://en.wikipedia.org/wiki/Definition#Intension_and_extension2011-01-11
  • 0
    @Trevor: I'm not sure what this means. @Tim: that's not an answer to my question. The Wikipedia article is talking about what seems to me to be primarily a philosophical notion, whereas you seem to be interested in a set-theoretic notion, and it's not clear to me that such a notion exists. (I think it does because I have heard set theorists talk about it, but I don't know what it is.) What a philosopher means by "set" is not what a mathematician means by "set."2011-01-11
  • 0
    @Qiaochu: I understand your point of me having no formalization here. From the same link in my last comment: "An enumerative definition of a concept or term is an extensional definition that gives an explicit and exhaustive listing of all the objects that fall under the concept or term in question. Enumerative definitions are only possible for finite sets and only practical for relatively small sets", although I doubt the last sentence and I think countable sets are qualified for "enumerative definitions"?2011-01-11
  • 0
    @Tim: that is the problem. I don't see what "explicit and exhaustive listing" could mean for a countable set except, as I mentioned in the comments to my answer, a notion which reduces to a special case of an intensional definition. For example, a Turing machine that prints out all of the members of the set. And if Wikipedia sets enumerative definitions are only possible for finite sets, and you are getting all of your information from Wikipedia, why are you disagreeing with it? What is _your_ definition?2011-01-12
  • 0
    See my comment after your reply. Simply put, I think definable by enumerative/extensional definition is same as countable.2011-01-12
  • 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! (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?2011-01-12
  • 0
    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).2011-01-12
  • 1
    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).2011-01-12
  • 0
    Thanks! For definition fallacy, I mean http://en.wikipedia.org/wiki/Fallacies_of_definition , and it is logical fallacy. For circular definition, I mean http://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)?2011-01-12
  • 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.

  • 2
    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.2011-01-11
  • 0
    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?2011-01-11
  • 0
    @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."2011-01-11
  • 0
    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? "2011-01-11
  • 0
    @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?2011-01-12
  • 0
    Sorry, I don't have a formalized one. What I think of describable by extensional definition is as enumerable same as countable. So in your definition, a set definable by an extensional definition if and only if the set is finite?2011-01-12
  • 0
    @Tim: no. The definition I'm thinking of is that there is a Turing machine that prints out its elements. Some of these sets are infinite, but any set with this property can also be described with a predicate. _Wikipedia's_ definition appears to restrict to finite sets. (To be more precise, in ZFC Wikipedia's definition should be restricted to hereditarily finite sets, of which there are countably many.)2011-01-12
  • 0
    Thanks! Could you show me where "in ZFC Wikipedia's definition" is?2011-01-12
  • 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