[FOM] 360:Finite Linear/Limited Memory Games
Harvey Friedman
friedman at math.ohio-state.edu
Mon Aug 31 17:43:42 EDT 2009
We continue from http://www.cs.nyu.edu/pipermail/fom/2009-August/013979.html
HOWEVER, this extended abstract is SELF CONTAINED.
Firstly, there were two places where, in section 1, I wrote f when I
obviously meant T. Also there was one place where, in section 2, I
wrote f when I obviously meant P.
These games will be conveniently restated very concisely in sections
B2-B4 below.
We also give the Linear Copy/Inversion game, which replaces the notion
of PL function (piecewise linear) with a more down to earth elementary
notion - a notion which is of interest in its own right.
We follow this with the General Copy/Inversion games that involve an
arbitrary function f:N^k into N. Here the theorem that is independent
of ZFC involves bounded memory for Bob.
NOTE: I have a target of Thanksgiving for a circulated manuscript - to
make sure this stuff is OK.
###############################
As usual, SMAH+ = ZFC + "for all k there is a strongly k-Mahlo
cardinal". SMAH = ZFC + {there is a strongly k-Mahlo cardinal}_k. That
various solitaire games can be won, is provable in SMAH+ but not in ZFC.
QUICK HIGHLIGHT: Look at sections B2-B5, which contain one game each.
A. Infinite Games of Finite Length.
A1. Infinite Copy/Inversion games.
A3. Infinite PL Copy/Inversion games.
A5. Infinite Polynomial PL Copy/Inversion games.
A6. Infinite Order Invariant Copy/Inversion games.
A7. Infinite Linear Copy/Inversion games.
B. Finite Games of Finite Length.
B1. Finite Copy/Inversion games.
B2. Finite PL Copy/Inversion game.
B3. Finite Polynomial PL Copy/Inversion game.
B4. Finite Order Invariant Copy/Inversion game.
B5. Finite Linear Copy/Inversion game.
A. INFINITE GAMES OF FINITE LENGTH.
We run into independence from ZFC in A1 using memory considerations.
In the remaining sections, we run into independence from ZFC without
using memory considerations.
A1. INFINITE COPY/INVERSION GAMES.
We let N be the set of all nonnegative integers. Let f:N^k into N. An
f inversion at x in N consists of y_1,...,y_k < x such that
f(y_1,...,y_k) = x.
We define an infinite two person game, with Alice and Bob making n
alternating plays, n >= 1. Alice will always play nonnegative
integers. Bob will either play a nonnegative integer or k nonnegative
integers. In the latter case, each of these k integers are considered
to be a play of Bob.
At any stage, Alice plays any nonnegative integer x. In response, Bob
either plays x or an inversion of f at x.
Bob is declared the winner if and only if none of Bob's plays has an f
inversion among Bob's plays.
THEOREM A1.1. For all f:N^k into N and n >= 1, Bob wins this game. In
fact, Bob can win this game looking only at Alice's previous play, and
not even the play number. I.e., Bob wins even with zero memory.
We now consider some variants of this game. We keep the same winning
criterion.
i. At any stage, Alice plays any nonnegative integer x. Bob plays x or
an f inversion of x. Bob also plays an integer > x.
ii. At any stage, Alice plays any nonnegative integer x. Bob plays x
or an f inversion of x. Bob also plays an odd integer > x.
THEOREM A1.2. For all f:N^k into N and n >= 1, Bob wins game i. In
fact, Bob can win game i looking only at Alice's previous play, and
not even the play number.
THEOREM A1.3. There exists f:N into N such that Alice wins game ii
with n = 2. We can take f to be a Presburger function. We can find PL
(piecewise linear) f:N^2 into N such that Alice wins game ii with n = 2.
How can we fix ii so that Bob can win? We give Bob more flexibility.
Bob doesn't have to copy/invert everything Alice plays. There are many
variants of this idea that can be cataloged and analyzed. We choose
the following version because Bob can win the game with "zero memory".
In other versions, it is obvious that Bob needs memory.
iii. At any stage, Alice plays any nonnegative integer x. If x is the
sum of a pair of previous plays by Bob, then Bob plays x or an f
inversion of x. Otherwise, Bob plays x or an f inversion of x, or
plays an odd integer > x.
I.e., if Alice strays too far away from Bob's previous plays, then Bob
is not required to, but is allowed to, copy/invert.
THEOREM A1.4. For all f:N^k into N and n >= 1, Bob wins game iii.
PROPOSITION A1.5. For all f:N^k into N and n >= 1, Bob wins game iii
looking only at Alice's previous play, and not even the play number.
I.e., Bob is given only zero memory.
PROPOSITION A1.6. Let r >= 1. For all f:N^k into N and n >= 1, Bob
wins game iii looking only at Alice's r+1 previous plays, and not even
the play number. I.e., Bob is given memory r.
THEOREM A1.7. Theorems A1.1, A1.2, A1.3 are provable in RCA_0. Theorem
A1.4 is provable in RCA_0 + "for all n, every subset of N has an n-th
Turing jump", and implies 1-Con(PA) over RCA_0. Proposition A1.5 is
provable in SMAH+ but not in any consistent fragment of SMAH.
Proposition A1.5 is provably equivalent, in ACA, to 1-Con(SMAH). For
each fixed r, Proposition A1.6 has the same status as Proposition A1.5.
A2. INFINITE PL GAMES OF FINITE LENGTH.
We say that T:N^k into N is PL if and only if it is piecewise linear
with integer coefficients. I.e., T can be defined by various affine
functions with integer coefficients on each of finitely many pieces,
where each piece is defined by a finite set of linear inequalities
with integer coefficients.
We consider games i,ii,iii as in section A1. The only difference now
is that we restrict to PL functions T. The results from section A1 are
the same.
Now we consider a new game. Let T:N^k into N be PL, and n,m >= 1. The
game has length n (n plays by Alice and n plays by Bob). There are
many variants of this that can be cataloged and analyzed.
iv. At any stage, Alice plays any nonnegative integer x. If x is the
sum of a pair of previous plays by Bob, then Bob plays x or a T.
Otherwise, Bob plays m^x.
Bob is declared the winner if and only if no play of Bob has a T
inversion among Bob's plays.
PROPOSITION A2.1. Let T be in PL and n >= 1. If m is sufficiently
large then Bob wins game iv.
THEOREM A2.2. Proposition A1.5 is provable in SMAH+ but not in any
consistent fragment of SMAH. Proposition A1.5 is provably equivalent,
in ACA, to 1-Con(SMAH). The least m as a function of f,n is a provably
recursive function of SMAH+ that eventually dominates all provably
recursive functions of SMAH. For each n, Proposition A2.2 is provable
in RCA_0, but the proofs grow in length as n increases, according to a
provably recursive function of SMAH+ that eventually dominates all
provably recursive functions of SMAH. Winning strategies are in linear
time log space in base 2 representations.
A3. INFINITE POLYNOMIAL GAMES OF FINITE LENGTH.
We modify the games i,ii,iii for polynomials P:Z^n into Z. A special P
inversion at x in Z consists of 0 < y_1,...,y_n < x/2 such that
P(y_1,...,y_n) = x.
i. At any stage, Alice plays any nonnegative integer x. Bob plays x or
a special P inversion of x. Bob also plays an integer > x.
ii. At any stage, Alice plays any nonnegative integer x. Bob plays x
or a special P inversion of x. Bob also plays an odd integer > x.
iii. At any stage, Alice plays any nonnegative integer x. If x is the
sum or difference or product of a pair of previous plays by Bob, then
Bob plays x or a P inversion of x. Otherwise, Bob plays x or a P
inversion of x, or an odd integer > x.
Bob is declared the winner if and only if no play of Bob has a special
P inversion among Bob's plays.
The results are the same as in section A1. We now come to the
adaptation of iv. There are many variants of this that can be
cataloged and analyzed.
iv. At any stage, Alice plays any nonnegative integer x. If x is the
sum or difference or product of previous plays by Bob, then Bob plays
x or a special P inversion of x. Otherwise, Bob plays (mx)!.
We obtain the same results as in section A2.
A4. INFINITE ORDER INVARIANT GAMES OF FINITE LENGTH.
Let R be contained in N^2k. An R inversion of x_1,...,x_k consists of
some y_1,...,y_k such that max(y_1,...,y_k) < max(x_1,...,x_k) and
R((x_1,...,x_k,y_1,...,y_k).
We play some games of length n. At any stage, Alice and Bob play k
nonnegative integers x_1,...,x_k. We refer to the x_1,...,x_k as the
plays, and the vector (x_1,...,x_k) as the responses (of course Alice
goes first). Thus each player at each stage "plays k integers" or
"responds with one k tuple", depending on how you want to look at it.
i. At any stage, Alice plays any x_1,...,x_k in N. Bob plays
x_1,...,x_k or an R inversion of x_1,...,x_k.
Bob is declared the winner if and only if no response of Bob has an R
inversion among Bob's responses.
THEOREM A4.1. For all R contained in N^k x N^k and n >= 1, Bob wins
game i.
We now go directly to the exotic game.
Let m >= 1.
ii. At any stage, Alice plays any x_1,...,x_k in N. If the x's are
among Bob's previous plays and their successors, then Bob plays
x_1,...,x_k or an R inversion of x_1,...,x_k. Otherwise, Bob plays
m^x_1,...,m^x_k.
Bob is declared the winner if and only if no response of Bob
mentioning the successor of a play of Bob has an R inversion among
Bob's responses.
PROPOSITION A4.2. Let m > (8kn)!, and R contained in N^2k be order
invariant. Then Bob wins game ii.
THEOREM A4.3. Proposition A4.2 is provable in SMAH+ but not in any
consistent fragment of SMAH. Proposition A4.2 is provably equivalent,
in ACA, to Con(SMAH). Winning strategies are in linear time log space
in base 2 representations.
A5. INFINITE LINEAR GAMES OF FINITE LENGTH.
This is a modification of section A3 in more down to earth linear terms.
DEFINITION. We say that x,y in N^k are additively equivalent if and
only if the following holds. Suppose some given length <= k sum of
coordinates of x is less than another given length <= k sum of
coordinates of x. Then the corresponding length <= k sum of
coordinates of y is less than the corresponding length <= k sum of
coordinates of y.
Here is a game based on additive equivalence. Let v_1,...,v_p be in
N^k and n,m >= 1. The game has length n.
v. At any stage, Alice plays any nonnegative integer. If x is the sum
of a pair of previous plays by Bob, then Bob plays x or some y in N^k
that sums to x and is additively equivalent to some v_j. Otherwise,
Bob plays m^x.
Bob is declared the winner if and only if no play of Bob is the sum of
a k tuple of plays of Bob that is additively equivalent to some v_j.
PROPOSITION A5.1. Let v_1,...,v_p be in N^k and n >= 1. If m is
sufficiently large then Bob wins game v.
THEOREM A5.2. Proposition A4.1 is provable in SMAH+ but not in any
consistent fragment of SMAH. Proposition A4.1 is provably equivalent,
in ACA, to 1-Con(SMAH). The least m as a function of f,n is a provably
recursive function of SMAH+ that eventually dominates all provably
recursive functions of SMAH. For each n, Proposition A4.1 is provable
in RCA_0, but the proofs grow in length as n increases, according to a
provably recursive function of SMAH+ that eventually dominates all
provably recursive functions of SMAH. Winning strategies are in linear
time log space in base 2 representations.
B. FINITE GAMES OF FINITE LENGTH.
We run into independence from ZFC in A1 using memory considerations.
In the remaining sections, we run into independence from ZFC without
using memory considerations.
B1. FINITE COPY/INVERSION GAMES.
We define a finite two person game, with Alice and Bob making n
alternating plays, n >= 1. Let f:[0,s]^k into [0,s]. An f inversion at
x in N consists of y_1,...,y_k < x such that f(y_1,...,y_k) = x.
At any stage, Alice plays any nonnegative integer x <= s. In response,
Bob copies or inverts. I.e., Bob must play x or an f inversion of x.
Bob is declared the winner if and only if no play of Bob has an f
inversion among Bob's plays.
THEOREM B1.1. For all f:0,x]^k into [0,s] and n >= 1, Bob wins this
game. In fact, Bob can win this game looking only at Alice's previous
play, and not even the play number. I.e., Bob wins even with zero
memory.
We now consider some variants of this game. We won't change the
criterion for winning.
i. At any stage, Alice plays any nonnegative integer x <= s. Bob plays
x or an f inversion of x. Bob also plays an integer <= s greater than
his previous plays.
ii. At any stage, Alice plays any nonnegative integer x. Bob plays x
or an f inversion of x. Bob also plays an odd integer <= s greater
than his previous plays.
THEOREM B1.2. Let s >= 8^(k^n) and f:[0,s]^k into [0,s]. Then Bob wins
game i. In fact, Bob can win game i looking only at Alice's previous
play, and not even the play number.
How can we fix ii so that Bob can win? We give Bob more flexibility.
Bob doesn't have to copy/invert everything Alice plays. There are many
variants of this idea that can be cataloged and analyzed. We choose
the following version because Bob can win the game with "zero memory".
In other versions, it is obvious that Bob needs some memory.
iii. At any stage, Alice plays any nonnegative integer x <= s. If x is
the sum of a pair of previous plays by Bob, then Bob plays x or an f
inversion of x. Otherwise, Bob plays x or an f inversion of x, or an
odd integer <= s greater than his previous plays.
I.e., if Alice strays too far away from Bob's previous plays, then Bob
is not required to copy/invert.
We use the same winning condition.
THEOREM B1.3. Let s >> k,n >= 1. For all f:[0,s]^k into [0,s], Bob
wins game iii.
PROPOSITION B1.4. Let s >> k,n >= 1. For all f:[0,s]^k into [0,s], Bob
wins game iii looking only at Alice's previous play, and not even the
play number.
PROPOSITION B1.5. Let r >= 1. Let s >> k,n,r >= 1. For all f:[0,s]^k
into [0,s], Bob wins game iii looking only at Alice's r previous
plays, and not even the play number.
THEOREM B1.6. Theorems B1.1, B1.2 are provable in RCA_0. Proposition
B1.5 can be proved in SMAH+ but not in any consistent fragment of
SMAH. Proposition B1.4 is provably equivalent, in ACA, to 1-Con(SMAH).
Theorem B1.3 is provably equivalent, in EFA, to 1-Con(PA). Proposition
B1.4 is provable in SMAH+ but not in any consistent fragment of SMAH.
Proposition B1.4 is provably equivalent, in ACA, to 1-Con(SMAH). For
each fixed r, Proposition B1.5 has the same status as Proposition B1.4.
B2. FINITE PL COPY/INVERSION GAME.
Let T be in PL (piecewise linear with integer coefficients). We play a
finite game with n alternating moves. Alice will play nonnegative
integers. Bob will play one or more nonnegative integers. The plays of
Bob consist of the nonnegative integers that are played by Bob.
Let n,m,s >= 1. At any stage, Alice plays any nonnegative integer x <=
s. If x is the sum of a pair of previous plays by Bob, then Bob plays
x or a T inversion of x. Otherwise, Bob plays m^x.
Bob is considered the winner if and only if no play of Bob has a T
inversion among Bob's plays.
Note that all plays in this game lie in [0,m^s].
PROPOSITION B2.1. Let T:N^k into N be in PL, and n >= 1. Let m,s be
sufficiently large. Then Bob wins this game.
THEOREM B2.2. Proposition B2.1 is provable in SMAH+ but not in any
consistent fragment of SMAH. Proposition B2.1 is provably equivalent,
in ACA, to 1-Con(SMAH). The "sufficiently large" describes a provably
recursive function of SMAH+ that eventually dominates every provably
recursive function of SMAH. For each fixed n, Proposition B2.1 is
provable in a tiny fragment of arithmetic, but the lengths of proofs
grow in the same wild way as a function of n, even if these are proofs
in ZFC.
B3. FINITE POLYNOMIAL COPY/INVERSION GAME.
Let P:Z^k into Z be a polynomial with integer coefficients. A special
P inversion of x consists of 0 < y_1,...,y_k < x/2 such that
P(y_1,...,y_k) = x.
We play a finite game with n alternating moves. Alice will play
nonnegative integers. Bob will play one or more nonnegative integers.
Let n,m,s >= 1.
At any stage, Alice plays any nonnegative integer x <= s. If x is the
sum or difference or product of a pair of previous plays by Bob, then
Bob plays x or a T inversion of x. Otherwise, Bob plays (mx)!.
Bob is considered the winner if and only if no play of Bob has a
special P inversion among Bob's plays.
Note that all plays in this game lie in [0,(ms)!].
PROPOSITION B3.1. Let P:Z^k into Z be a polynomial with integer
coefficients, and n >= 1. Let m,s be sufficiently large. Then Bob wins
this game.
THEOREM B3.2. Proposition B3.1 is provable in SMAH+ but not in any
consistent fragment of SMAH. Proposition B2.1 is provably equivalent,
in ACA, to 1-Con(SMAH). The "sufficiently large" describes a provably
recursive function of SMAH+ that eventually dominates every provably
recursive function of SMAH. For each fixed n, Proposition B2.1 is
provable in a tiny fragment of arithmetic, but the lengths of proofs
grow in the same wild way as a function of n, even if these are proofs
in ZFC.
B4. FINITE ORDER INVARIANT COPY/INVERSION GAME.
Let R be contained in [0,m^s]^2k. An R inversion of x_1,...,x_k
consists of some y_1,...,y_k such that max(y_1,...,y_k) <
max(x_1,...,x_k) and R(x_1,...,x_k,y_1,...,y_k).
We play some games of length n. At any stage, Alice and Bob play k
nonnegative integers x_1,...,x_k. We refer to the x_1,...,x_k as the
plays, and the vector (x_1,...,x_k) as the responses (of course Alice
goes first). Thus each player at each stage "plays k integers" or
"responds with one k tuple", depending on how you want to look at it.
At any stage, Alice plays any nonnegative x_1,...,x_k <= s. If the x's
are among Bob's previous plays and their successors, then Bob plays
x_1,...,x_k or an R inversion of x_1,...,x_k. Otherwise, Bob plays
m^x_1,...,m^x_k.
Bob is declared the winner if and only if no response of Bob
mentioning the successor of a play of Bob has an R inversion among
Bob's responses.
PROPOSITION B4.1. Let m,s >= (8kn)!, and R contained in [0,m^s]^2k be
order invariant. Then Bob wins this game.
Note that Proposition B4.1 is explicitly Pi01.
THEOREM B4.2. Proposition B4.2 is provable in SMAH+ but not in any
consistent fragment of SMAH. Proposition B4.2 is provably equivalent,
in ACA, to Con(SMAH).
B5. FINITE LINEAR COPY/INVERSION GAME.
Recall the definition of additive equivalence of vectors from section
A5.
Here is a game based on additive equivalence. Let v_1,...,v_p be in
N^k and n,m,s >= 1. The game has length n.
At any stage, Alice plays a nonnegative integer <= s. If x is the sum
of a pair of previous plays by Bob, then Bob plays x or some y in N^k
that sums to x and is additively equivalent to some v_j. Otherwise,
Bob plays m^x.
Bob is declared the winner if and only if no play of Bob is the sum of
a k tuple of plays of Bob that is additively equivalent to some v_j.
PROPOSITION B5.1. Let v_1,...,v_p be in N^k and n >= 1. If m,s are
sufficiently large then Bob wins this game.
THEOREM B5.2. Proposition B5.1 is provable in SMAH+ but not in any
consistent fragment of SMAH. Proposition B5.1 is provably equivalent,
in ACA, to 1-Con(SMAH). The least m as a function of f,n is a provably
recursive function of SMAH+ that eventually dominates all provably
recursive functions of SMAH. For each n, Proposition B5.1 is provable
in RCA_0, but the proofs grow in length as n increases, according to a
provably recursive function of SMAH+ that eventually dominates all
provably recursive functions of SMAH.
**********************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 359th in a series of self contained numbered
postings to FOM covering a wide range of topics in f.o.m. The list of
previous numbered postings #1-249 can be found at
http://www.cs.nyu.edu/pipermail/fom/2005-June/008999.html in the FOM
archives, 6/15/05, 9:18PM. NOTE: The title of #269 has been corrected
from the original.
250. Extreme Cardinals/Pi01 7/31/05 8:34PM
251. Embedding Axioms 8/1/05 10:40AM
252. Pi01 Revisited 10/25/05 10:35PM
253. Pi01 Progress 10/26/05 6:32AM
254. Pi01 Progress/more 11/10/05 4:37AM
255. Controlling Pi01 11/12 5:10PM
256. NAME:finite inclusion theory 11/21/05 2:34AM
257. FIT/more 11/22/05 5:34AM
258. Pi01/Simplification/Restatement 11/27/05 2:12AM
259. Pi01 pointer 11/30/05 10:36AM
260. Pi01/simplification 12/3/05 3:11PM
261. Pi01/nicer 12/5/05 2:26AM
262. Correction/Restatement 12/9/05 10:13AM
263. Pi01/digraphs 1 1/13/06 1:11AM
264. Pi01/digraphs 2 1/27/06 11:34AM
265. Pi01/digraphs 2/more 1/28/06 2:46PM
266. Pi01/digraphs/unifying 2/4/06 5:27AM
267. Pi01/digraphs/progress 2/8/06 2:44AM
268. Finite to Infinite 1 2/22/06 9:01AM
269. Pi01,Pi00/digraphs 2/25/06 3:09AM
270. Finite to Infinite/Restatement 2/25/06 8:25PM
271. Clarification of Smith Article 3/22/06 5:58PM
272. Sigma01/optimal 3/24/06 1:45PM
273: Sigma01/optimal/size 3/28/06 12:57PM
274: Subcubic Graph Numbers 4/1/06 11:23AM
275: Kruskal Theorem/Impredicativity 4/2/06 12:16PM
276: Higman/Kruskal/impredicativity 4/4/06 6:31AM
277: Strict Predicativity 4/5/06 1:58PM
278: Ultra/Strict/Predicativity/Higman 4/8/06 1:33AM
279: Subcubic graph numbers/restated 4/8/06 3:14AN
280: Generating large caridnals/self embedding axioms 5/2/06 4:55AM
281: Linear Self Embedding Axioms 5/5/06 2:32AM
282: Adventures in Pi01 Independence 5/7/06
283: A theory of indiscernibles 5/7/06 6:42PM
284: Godel's Second 5/9/06 10:02AM
285: Godel's Second/more 5/10/06 5:55PM
286: Godel's Second/still more 5/11/06 2:05PM
287: More Pi01 adventures 5/18/06 9:19AM
288: Discrete ordered rings and large cardinals 6/1/06 11:28AM
289: Integer Thresholds in FFF 6/6/06 10:23PM
290: Independently Free Minds/Collectively Random Agents 6/12/06
11:01AM
291: Independently Free Minds/Collectively Random Agents (more) 6/13/06
5:01PM
292: Concept Calculus 1 6/17/06 5:26PM
293: Concept Calculus 2 6/20/06 6:27PM
294: Concept Calculus 3 6/25/06 5:15PM
295: Concept Calculus 4 7/3/06 2:34AM
296: Order Calculus 7/7/06 12:13PM
297: Order Calculus/restatement 7/11/06 12:16PM
298: Concept Calculus 5 7/14/06 5:40AM
299: Order Calculus/simplification 7/23/06 7:38PM
300: Exotic Prefix Theory 9/14/06 7:11AM
301: Exotic Prefix Theory (correction) 9/14/06 6:09PM
302: PA Completeness 10/29/06 2:38AM
303: PA Completeness (restatement) 10/30/06 11:53AM
304: PA Completeness/strategy 11/4/06 10:57AM
305: Proofs of Godel's Second 12/21/06 11:31AM
306: Godel's Second/more 12/23/06 7:39PM
307: Formalized Consistency Problem Solved 1/14/07 6:24PM
308: Large Large Cardinals 7/05/07 5:01AM
309: Thematic PA Incompleteness 10/22/07 10:56AM
310: Thematic PA Incompleteness 2 11/6/07 5:31AM
311: Thematic PA Incompleteness 3 11/8/07 8:35AM
312: Pi01 Incompleteness 11/13/07 3:11PM
313: Pi01 Incompleteness 12/19/07 8:00AM
314: Pi01 Incompleteness/Digraphs 12/22/07 4:12AM
315: Pi01 Incompleteness/Digraphs/#2 1/16/08 7:32AM
316: Shift Theorems 1/24/08 12:36PM
317: Polynomials and PA 1/29/08 10:29PM
318: Polynomials and PA #2 2/4/08 12:07AM
319: Pi01 Incompleteness/Digraphs/#3 2/12/08 9:21PM
320: Pi01 Incompleteness/#4 2/13/08 5:32PM
321: Pi01 Incompleteness/forward imaging 2/19/08 5:09PM
322: Pi01 Incompleteness/forward imaging 2 3/10/08 11:09PM
323: Pi01 Incompleteness/point deletion 3/17/08 2:18PM
324: Existential Comprehension 4/10/08 10:16PM
325: Single Quantifier Comprehension 4/14/08 11:07AM
326: Progress in Pi01 Incompleteness 1 10/22/08 11:58PM
327: Finite Independence/update 1/16/09 7:39PM
328: Polynomial Independence 1 1/16/09 7:39PM
329: Finite Decidability/Templating 1/16/09 7:01PM
330: Templating Pi01/Polynomial 1/17/09 7:25PM
331: Corrected Pi01/Templating 1/20/09 8:50PM
332: Preferred Model 1/22/09 7:28PM
333: Single Quantifier Comprehension/more 1/26/09 4:32PM
334: Progress in Pi01 Incompleteness 2 4/3/09 11:26PM
335: Undecidability/Euclidean geometry 4/27/09 1:12PM
336: Undecidability/Euclidean geometry/2 4/29/09 1:43PM
337: Undecidability/Euclidean geometry/3 5/3/09 6:54PM
338: Undecidability/Euclidean geometry/4 5/5/09 6:38PM
339: Undecidability/Euclidean geometry/5 5/7/09 2:25PM
340: Thematic Pi01 Incompleteness 1 5/13/09 5:56PM
341: Thematic Pi01 Incompleteness 2 5/21/09 7:25PM
342: Thematic Pi01 Incompleteness 3 5/23/09 7:48PM
343: Goedel's Second Revisited 1 5/27/09 6:07AM
344: Goedel's Second Revisited 2 6/1/09 9:21PM
345: Thematic Pi01 Incompleteness 4 6/15/09 1:15PM
appears misnumbered as 344.
346: Goedel's Second Revisited 3 6/16/09 11:04PM
347: Goedel's Second Revisited 4 6/20/09 1:25AM
348: Goedel's Second Revisited 5 6/22/09 11:00AM
349: Pi01 Incompleteness/set series 7/20/09 11:21PM
350: one dimensional set series 7/23/09 12:11AM
351: Mapping Theorems/Mahlo/Subtle 8/6/09 10:59PM
352: Mapping Theorems/simpler 8/7/09 10:06PM
353: Function Generation 1 8/9/09 12:09PM
354: Mahlo Cardinals in HIGH SCHOOL 1 8/9/09 6:37PM
355: Mahlo Cardinals in HIGH SCHOOL 2 8/10/09 6:18PM
356: Simplified HIGH SCHOOL and Mapping Theorem 8/14/09 9:31AM
357: HIGH SCHOOL Games/Update 8/20/09 10:42AM
358: clearer statements of HIGH SCHOOL Games 8/23/09 2:42AM
359: finite two person HIGH SCHOOL games 8/24/09 1:28PM
Harvey Friedman
More information about the FOM
mailing list