BRICS RS-94-24 S. Riis: A Fractal which violates the Axiom of Determinacy

BRICS

Basic Research in Computer Science

A Fractal which violates the Axiom of Determinacy

S�ren Riis

BRICS Report Series RS-94-24 ISSN 0909-0878 August 1994 Copyright \begin{matrix}c \\ ◯ \end{matrix} 1994, BRICS, Department of Computer Science

University of Aarhus. All rights reserved.

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

See back inner page for a list of recent publications in the BRICS Report Series. Copies may be obtained by contacting:

BRICS Department of Computer Science University of Aarhus Ny Munkegade, building 540 DK - 8000 Aarhus C Denmark

Telephone: +45 8942 3360
Telefax: +45 8942 3255
Internet: BRICS@daimi.aau.dk

A Fractal which violates the Axiom of Determinacy

Søren Riis^{∗} ; BRICS^{†}

June 1994

Abstract By use of the axiom of choice I construct a symmetrical and selfsimilar subset A ⊆ [0, 1] ⊆ ℝ. Then by an elementary strategy stealing argument it is shown that A is not determined. The (possible) existence of fractals like A clarifies the status of the controversial Axiom of Determinacy. ^{1}

In this note, I present an argument against the unrestricted axiom of determinacy (=AD).

Fix A ⊆ [0, 1] ⊆ ℝ. We define an infinite game G_{A} as follows. The initial position is I := [0, 1]. Each position will be an interval [a, b] ⊆ [0, 1], a, b ∈ \{\frac{p}{2^{k}} : p, k ∈ ℕ\}. In each position [a, b] there are always two legal moves. The player who has the turn can move “left” or can move “right”. If the player moves “left” the new position is [a, \frac{a+b}{2}]. If the player moves “right” the new position is [\frac{a+b}{2}, b]. Player A makes the first move. In each actual game, successively the players construct a sequence I = [0, 1] ⊇ I_{1} ⊇ I_{2} ⊇ .... of closed intervals. The interval I_{j+1} is either the left or the right closed interval of I_{j}. Each actual game produces a point p := ∩_{j∈ℕ} I_{j} ∈ [0, 1].

∗This work was initiated at University of Oxford England

†Basic Research in Computer Science, Centre of the Danish National Research Foundation.

11991 Mathematics subject classification. Primary 03E60, Secondary 04A25 Key words and phrases. Axiom of Determinacy, Axiom of Choice, Fractal.

According to the rules of G_{A} player A wins if p ∈ A. Otherwise (i.e. when p ∉ A) player B wins.

A player has a winning strategy if there is a protocol (i.e. a map from the set of positions to { ‘left’,‘right’}) which guarantees victory. The set of positions can be divided into 3 classes. The positions which are won for player A, the positions which are won for player B, and the controversial class of the positions which are undetermined. According to the axiom of determinacy the last class is always empty. Each actual game has a winner. So if the players are clever enough it must be determined who will win the game. The intuition behind AD is that if A and B have infinite powers the same player will win each game. If for instance A wins the first game, A ought also to win the second game. The argument is that if player B wins this new game, sometimes in the first game B could not have possibly played optimally ^{2} .

It is well-known that AC (the axiom of choice) and AD are contradictory. The usual proof uses a diagonal argument combined with the fact that the number of strategies is 2^{ℵ_{0}} [1], [2]. The status of AD has been examined in great depth [4],[5]. There seems to be two approaches. One can accept AC and ask which sets are determined. This leads to questions which are independent of the usual axiomatization of set theory [2],[4], [5]. The other and more radical approach is to discard the axiom of choice [3]. The main argument is that AD is deductively strong and has many nice consequences, [2],[4]. Still there is no doubt that most of us prefer AC.

Let ℚ denote the rational numbers. Theorem (AC) There exists a set A ⊆ [0, 1] such that A and A ∩ [0, \frac{1}{2}] are isomorphic under the map x → \frac{x}{2}, and A\ℚ and A^{c} \ℚ are isomorphic under the map x → 1 − x. Proof: Consider the collection J of pairs (A, B) where A, B ⊆ [0, 1] \ ℚ, where A ∩ B = ∅ and where A = A · ℚ ∩ [0, 1] \ ℚ and B = B · ℚ ∩ [0, 1] \ ℚ. The set J of such pairs are ordered inductively under inclusion. According to Zorn’s lemma (which is equivalent to AC) there must be a pair (A, B) ∈ J which is maximal with respect to inclusion. We claim that A∪B = [0, 1]\ℚ. Otherwise there would be x ∈ ([0, 1]\ℚ)\(A∪B). Notice that, (1−x)·ℚ∩A = ∅, x · ℚ ∩ (1 − x) · ℚ = ∅ and x · ℚ ∩ B = ∅. Thus (A ∪ x · ℚ, B ∪ (1 − x) · ℚ) is well-defined and belongs to J. This violates the maximality of (A, B). □ Theorem All the positions (I′, A ∩ I′) are isomorphic, when the points in ℚ are ignored. No move can make any difference to the outcome because all positions are isomorphic. Each game produces a winner. Proof: We ignore the points in ℚ. Notice that the two positions which can be reached from I both are isomorphic to I (when the role of A is changed with that of A^{c}). This is because f_{1} : x → 1 − 2x maps A^{c} ∩ [0, \frac{1}{2}] isomorphic onto A, and because f_{2} : x → 2 − 2x maps A^{c} ∩ [\frac{1}{2}, 1] isomorphic onto A. □ Corollary (AC) G_{A} is not determined. Proof: If player A has a winning strategy, player B can steal it. It is not difficult to show that the points in ℚ do not affect this argument. □

2Unless of course A first deviate from the line of play in the first play. But to deviate and lose does not seem wise.

References

[1] D.Gale, F.Steward ; Infinite games with perfect information, in Contributions to the Theory of Games II Ann. Math. Studies 28 (1953) p 245-266

[2] T.Jech ; Set theory, Academic press London (1978)

[3] J.Mycielski; On the axiom of determinateness; Fund. Math. 54 (1964) p 205-224 and Fund. Math. 59 (1966) p 203-212

[4] R.Soloway; A model of Set theory in which every set of reals is Lebesgue measurable, Ann. of Math. (1970) p 1-56

[5] S.Shelah, H.Woodin; Large cardinals imply that every reasonable set of reals is Lebesgue measurable; Israel J.Math. 70 (1990) p 381-394

Recent Publications in the BRICS Report Series

RS-94-24 S�ren Riis. A Fractal which violates the Axiom of Determinacy. August 1994, 3 pp.

RS-94-23 S�ren Riis. Finitisation in Bounded Arithmetic. August 1994, 31 pp.

RS-94-22 Torben Bra� uner. A General Adequacy Result for a Linear Functional Language. August 1994, 39 pp. Presented at MFPS ’94.

RS-94-21 S�ren Riis. Count(q) does not imply Count(p). July 1994, 55 pp.

RS-94-20 Peter D. Mosses and Mart��n Musicante. An Action Semantics for ML Concurrency Primitives. July 1994, 21 pp. To appear in Proc. FME ’94 (Formal Methods Europe, Symposium on Industrial Bene�t of Formal Methods), LNCS, 1994.

RS-94-19 Jens Chr. Godskesen, Kim G. Larsen, and Arne Skou. Automatic Veri�cation of Real�Timed Systems Using Epsilon. June 1994, 8 pp. Appears in: Protocols, Speci�- cation, Testing and Veri�cation PSTV ’94.

RS-94-18 Sten Agerholm. LCF Examples in HOL. June 1994, 16 pp. To appear in: Proceedings of the 7th International Workshop on Higher Order Logic Theorem Proving and its Applications, LNCS, 1994.

RS-94-17 Allan Cheng. Local Model Checking and Traces. June 1994, 30 pp.

RS-94-16 Lars Arge. External-Storage Data Structures for Plane-Sweep Algorithms. June 1994, 37 pp.

RS-94-15 Mogens Nielsen and Glynn Winskel. Petri Nets and Bisimulations. May 1994, 36 pp.

RS-94-14 Nils Klarlund. The Limit View of In�nite Computations. May 1994, 16 pp. To appear in the LNCS proceedings of Concur ’94, LNCS, 1994.