Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. Donation Acolyte
    Now With Added BA
    21 Nov '04 12:35
    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?
  2. 21 Nov '04 15:51
    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.
  3. Donation Acolyte
    Now With Added BA
    21 Nov '04 17:27
    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.
  4. Standard member royalchicken
    CHAOS GHOST!!!
    21 Nov '04 23:42
    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.
  5. Donation Acolyte
    Now With Added BA
    22 Nov '04 14:45
    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?
  6. Standard member royalchicken
    CHAOS GHOST!!!
    22 Nov '04 17:56
    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 ?
  7. Donation Acolyte
    Now With Added BA
    23 Nov '04 11:20
    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.
  8. Standard member royalchicken
    CHAOS GHOST!!!
    23 Nov '04 12:35
    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.