Three-player perfect information games are usually undetermined

September 7, 2009

Recently, I gave the talk Undeterminacy and choice (Indeterminación y elección), at the XVII Colombian Mathematical Congress, in Cali. Slides can be found at my talks page.

The talk addressed the results of my recent paper on {\sf AD}^+ with Richard Ketchersid, mentioned in my previous entry, and some extensions, about which I expect to be posting soon. Afterwards, somebody asked me how much of the theory of determinacy can be extended to three-player (or more) perfect information games. Not much.

The following easy example was suggested by Richard Ketchersid: There is an undetermined one-move game where players I, II, III play 0 or 1, with I playing first, then II, and finally III. To see this, say that n_I, n_{II}, and n_{III} are the numbers played, and that:

  • Player I wins iff n_{II} \neq n_{III}.
  • Player II wins iff n_{II} \neq n_I and n_{II}= n_{III}.
  • Player III wins if n_I = n_{II}=n_{III}.

(One may think of this game as a perfect information version of paper-rock-scissors.) I imagine this observation is ancient, and would be grateful for a reference.

502 – Propositional logic

September 7, 2009

1. Introduction

These notes follow closely notes originally developed by Alexander Kechris for the course Math 6c at Caltech.

Somewhat informally, a proposition is a statement which is either true or false. Whichever the case, we call this its truth value.

Example 1 “There are infinitely many primes”; “{5>3}”; and “14 is a square number” are propositions. A statement like “{x} is odd,” (a “propositional function”) is not a proposition since its truth depends on the value of {x} (but it becomes one when {x} is substituted by a particular number).

Informally still, a propositional connective combines individual propositions into a compound one so that its truth or falsity depends only on the truth or falsity of the components. The most common connectives are:

  • Not (negation), {\lnot,}
  • And (conjunction), {\wedge,}
  • Or (disjunction), {\vee,}
  • Implies (implication), {\rightarrow,}
  • Iff (equivalence), {\leftrightarrow.}

Read the rest of this entry »