(5) Bonus question: countability via games. Recall that a set S is countable if there exists...

Transcribed Image Text:

(5) Bonus question: countability via games. Recall that a set S is countable if there exists a bijection (one-to-one correspondence) f: S→ N from S to the natural numbers. Equivalently, S is countable if it can be written as S = {$1,S2,...}. Recall also that the interval [0,1] is not countable (Cantor, 1874). We will prove this using a game. This proof is due to Grossman and Turett (1998). Consider the following game. Fix a subset S≤ [0,1], and let ao = 0 and bo = 1. The players Al and Betty take alternating turns, starting with Al. In an-1, but Al's nth turn he has to choose some an which is strictly larger than strictly smaller than bn-1. At Betty's nth turn she has to choose a bn that is strictly smaller than bn-1 but strictly larger than an. Thus the sequence {an} is strictly increasing and the sequence {bn} is strictly decreasing, and furthermore an<bm for every n,m € N. Since an is a bounded increasing sequence, it has a limit a = limn an. Al wins the game if a € S, and Betty wins the game otherwise. th (a) 1 point. Let S = {$1₁, 82,...} be countable. Prove that the following is a winning strategy for Betty: in her n turn she chooses bn = sn if she can (i.e., if an < Sn <bn-1). Otherwise she chooses any other allowed number. (b) 1 point. Explain why this implies that [0, 1] is uncountable. (5) Bonus question: countability via games. Recall that a set S is countable if there exists a bijection (one-to-one correspondence) f: S→ N from S to the natural numbers. Equivalently, S is countable if it can be written as S = {$1,S2,...}. Recall also that the interval [0,1] is not countable (Cantor, 1874). We will prove this using a game. This proof is due to Grossman and Turett (1998). Consider the following game. Fix a subset S≤ [0,1], and let ao = 0 and bo = 1. The players Al and Betty take alternating turns, starting with Al. In an-1, but Al's nth turn he has to choose some an which is strictly larger than strictly smaller than bn-1. At Betty's nth turn she has to choose a bn that is strictly smaller than bn-1 but strictly larger than an. Thus the sequence {an} is strictly increasing and the sequence {bn} is strictly decreasing, and furthermore an<bm for every n,m € N. Since an is a bounded increasing sequence, it has a limit a = limn an. Al wins the game if a € S, and Betty wins the game otherwise. th (a) 1 point. Let S = {$1₁, 82,...} be countable. Prove that the following is a winning strategy for Betty: in her n turn she chooses bn = sn if she can (i.e., if an < Sn <bn-1). Otherwise she chooses any other allowed number. (b) 1 point. Explain why this implies that [0, 1] is uncountable.

Answer rating: 100% (QA)

a To prove that the strategy is winning for Betty we need to show that no matter how Al plays Betty ... View the full answer