1
$\begingroup$

Let's say two mathematicians play a game. One of them picks an arbitrary element from a countably infinite set (perhaps the integers, as per the title), and the other one guesses what it is. The second player has as many guesses as they need, and after each guess, they are simply told whether they were correct or not.

Would this game never end, or would it last an arbitrarily large but finite amount of time?

What if the first mathematician selects from an uncountably infinite set, such as the real numbers?

$\endgroup$
  • $\begingroup$ I believe I have a proof that the game has a finite length when the set is countably infinite, but I'm not sure about when the set is uncountably infinite. $\endgroup$ – Kevin Mar 6 '15 at 19:44
  • 1
    $\begingroup$ If you're guessing from the real numbers, how does one finish guessing the number in the first place? the set of numbers one can describe in finite time is itself countable, and thus a much smaller set than the real numbers themselves... $\endgroup$ – Dan Uznanski Mar 6 '15 at 19:55
2
$\begingroup$

If player A picks a number from a countable set, then player B will definitely get there by guessing systematically. Suppose we're playing it, and the number I pick is 9000000000000: you start guessing at 1, then 2, 3, etc., you'll eventually get to 9000000000000. So the game will last a finite amount of time.

If player A picks a number from an uncountably infinite set, then player B will (most likely) never get there by guessing systematically. Suppose we're playing it, and the number I pick is 2. If you start guessing 1, 0.1, 0.01, 0.001, 0.0001, etc. then you will never get to 2. The chance of correctly guessing my number is arbitrarily small, though I hesitate to say that you'll never guess my number (because we could play the game, I could pick a given number, and you could simply guess it). So in this case the game may last forever.

What this game really gets at is that there's a bijection from the natural numbers to any countably finite set, but there's no bijection from the naturals to the reals.

$\endgroup$
1
$\begingroup$

In the first case, one constructs a bijection $f$ from the natural numbers into said countable set. Then you guess $f(1),f(2), \dots$ and eventually (after finitely many steps) you guess correctly.

In the second case, with probability 100% you will always guess incorrectly, so usually the game will go on forever. (You can make only countably many guesses anyway)

$\endgroup$
  • $\begingroup$ I don't think that the cardinality of the set makes a difference with regards to the probability in this case. Once the set is infinite, the probability of guessing correctly is $0$. $\endgroup$ – barak manos Mar 6 '15 at 19:50
  • $\begingroup$ Probability 100%? Why? I think the probability is arbitrarily close to 100%, but I don't think it's 100%. (We could play the game, I could pick e.g. 5 as my real number, and you could guess it. Unlikely, but possible!) $\endgroup$ – Newb Mar 6 '15 at 19:52
  • $\begingroup$ @Newb If you are given a square and a point on it, what is the probability that you hit a specific point on it? Thats 1 point out of infinitely (uncountably, thought it doesnt really matter) many point, and probability is $0$. In this case we say " you will never hit the point almost surely" because as you suggested, when you try infinitely many times, we cannot say for sure that you will never hit it. $\endgroup$ – user160738 Mar 6 '15 at 19:56
  • $\begingroup$ @Newb Probability 1 events don't always happen! $\endgroup$ – Potato Mar 6 '15 at 19:56
  • $\begingroup$ @Newb Probability 100% doesn't mean it necessarily happens, this only always works in finite probability spaces. Also: A number arbitrarily close to 100%, but less, isn't a real number and I at least don't know, how probability with infinitesimals works. $\endgroup$ – Stefan Perko Mar 6 '15 at 20:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.