- 21 Nov '04 12:35Suppose X is a definable set, ie one which can be specified uniquely by means of a finite mathematical definition (eg the real numbers or the set of zeroes of the Riemann zeta function). Suppose in addition that X is countable.

Is it the case that every finite subset of X is definable? - 21 Nov '04 15:51

Of course. You only need to make a mapping from the complete X to a certain subset. Since X is countable you can perfectly do this.*Originally posted by Acolyte***Suppose X is a definable set, ie one which can be specified uniquely by means of a finite mathematical definition (eg the real numbers or the set of zeroes of the Riemann zeta function). Suppose in addition that X is countable.**

Is it the case that every finite subset of X is definable? - 21 Nov '04 17:27

Er, what do you mean by 'a certain subset'? You can't define a subset Y by means of a function X -> Y !*Originally posted by piderman***Of course. You only need to make a mapping from the complete X to a certain subset. Since X is countable you can perfectly do this.**

One way of trying to define every finite subset of X is to construct a surjective map from N to X, and then defining each finite subset of X as the image of some finite subset of N. This is equivalent producing a definable sequence which contains every element of X. However, I don't see how it's 'obvious' that this can always be done*in a definable way*; for example, Q can be written as a definable sequence, but there's no 'natural' way of doing this, and giving a concrete example of such a sequence is harder than showing the existence of such sequences. - 21 Nov '04 23:42

Let P be the property which defines X. Then since X is countable, we can meaningfully label X(n) as the nth element of X according to some bijection mapping N to X; X(n) is the nth object with the property P.*Originally posted by Acolyte***Suppose X is a definable set, ie one which can be specified uniquely by means of a finite mathematical definition (eg the real numbers or the set of zeroes of the Riemann zeta function). Suppose in addition that X is countable.**

Is it the case that every finite subset of X is definable?

For some finite subset X' of X, pick the subset N' of N corresponding to X'. If N' is definable, say by some property Q, then X' is as well: X' is the set of objects with property P corresponding to the natural numbers with property Q. Therefore, if every finite subset of N is definable, then every finite subset of X is as well. Every finite subset of N, when ordered least-to-greatest, is the decimal expansion of some rational number, so each finite subset of N is definable (eg n in N is the 5th number in the d.e. of 0.123456789), and thus each finite subset of X is as well. - 22 Nov '04 14:45

The rest is straightforward, but why must this be the case? There must exist a way of counting or well-ordering X, but why must at least one of these well-orderings be definable? What if we only know the set is countable thanks to some obscure non-constructive argument, eg P = 'the largest countable set with property Q' and we used Zorn's lemma to prove its existence?*Originally posted by royalchicken***Let P be the property which defines X. Then since X is countable, we can meaningfully label X(n) as the nth element of X** - 22 Nov '04 17:56

Right. Watch this space. I'll be back soon to try and respond. Until then, is your title a piss-take about my countrymen ?*Originally posted by Acolyte***The rest is straightforward, but why must this be the case? There must exist a way of counting or well-ordering X, but why must at least one of these well-orderings be definable? What if we only know the set is countable thanks to some obscure non-constructive argument, eg P = 'the largest countable set with property Q' and we used Zorn's lemma to prove its existence?** - 23 Nov '04 11:20

Actually, it's a reference to one of my (British) friends' frustration with my scepticism. It should read 'Why can't you just believe?' but that was too long.*Originally posted by royalchicken***Right. Watch this space. I'll be back soon to try and respond. Until then, is your title a piss-take about my countrymen ?** - 23 Nov '04 12:35

Understood. Heh, I had an argument with someone the other night; at about 7:00 his position had finally changed to ''Things are right or wrong based on what I say, so ha!''*Originally posted by Acolyte***Actually, it's a reference to one of my (British) friends' frustration with my scepticism. It should read 'Why can't you just believe?' but that was too long.**

On further looking at the question at hand, I think you're right but I don't have a proof that there exists an undefinable subset of some X.