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?

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?

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

Er, what do you mean by 'a certain subset'? You can't define a subset Y by means of a function X -> Y !

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.

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?

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.

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.

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

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 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?

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 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 ðŸ˜ ðŸ˜›?

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

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!''

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.