21 Nov 04
Originally posted by AcolyteOf 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.
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
Originally posted by pidermanEr, what do you mean by 'a certain subset'? You can't define a subset Y by means of a function X -> Y !
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
Originally posted by AcolyteLet 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.
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
Originally posted by royalchickenThe 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?
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
Originally posted by AcolyteRight. Watch this space. I'll be back soon to try and respond. Until then, is your title a piss-take about my countrymen 😠😛?
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
Originally posted by royalchickenActually, 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.
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
Originally posted by AcolyteUnderstood. 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!''
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.