An impossible game at the heart of math
Vložit
- čas přidán 17. 08. 2023
- Strategy stealing, the axiom of determinacy, and why it's incompatible with the axiom of choice. #SoME3
Resources to learn more and other interesting notes:
_____________________
Chomp:
Play online: www.math.ucla.edu/~tom/Games/...
Wikipedia article: en.wikipedia.org/wiki/Chomp
List of known best first moves: sites.math.rutgers.edu/~zeilb...
Also check out chapter 18 in the book "Winning Ways for Your Mathematical Plays"
Zermelo's Theorem: en.wikipedia.org/wiki/Zermelo...)
_____________________
The Axiom of Determinacy:
Wikipedia article: en.wikipedia.org/wiki/Axiom_o...
Borel Determinacy Theorem: en.wikipedia.org/wiki/Borel_d...
The argument in the video is essentially given as Proposition 28.1 in the book The Higher Infinite by Akihiro Kanamori, but it is stated in more complicated terms. You can also find some discussion of it at this link: mathoverflow.net/questions/49...
_____________________
The Axiom of Choice:
Wikipedia article: en.wikipedia.org/wiki/Axiom_o...
Banach-Tarski Paradox: en.wikipedia.org/wiki/Banach%...
Vsauce Video on Banach-Tarski Paradox: • The Banach-Tarski Paradox
Corrections:
fun fact: for the “infinitely many primes” game, alice doesn’t even need to know where the next prime number is. since it’s been proven that for any integer n there is at least one prime number between n and 2n, alice simply has to color up to 2n, where n is the current total number of squares colored
It's much easier to show that there must be a prime somewhere between n and n!+1, which also works as a strategy
@@BramCohen You don't have to prove the theorem to use the stragegy, though. You just need to know it's true, so the difficulty of the proof doesn't matter, really.
@@frenchimp and how do you know it's true, you'll have to understand the proof. It's much easier to understand the proof that there's a prime between n and n!+1
This strategy also works for the 1/n game 6:30
The other player can choose the same strategy and force a draw.
First example, Bob could also choose up to the next prime number and thus he will also have infinitely many primes.
Second example, Bob can also go 1 before the next 2^n thus also forcing Alice to have a 2^n every time.
Chomp is cool, I've never seen it before.
what's funny too is that you can ALWAYS beat that online one you shared.
You just have to cheat and open two windows/tabs and then just play the response of the 1st tab in the 2nd tab (start with the 1st tab and upper right corner).
It's strategy stealing at its laziest. 😛
If player 1 first chose one of the two adjacent to the poison square, then player 2's next turn can force player 1 to lose and player 1 could not have inflicted this situation in their turn. This is why I'm not convinced. It's an obvious counter example to what he said.
@@lyrimetacurl0 That's not exactly what the strategy stealing argument says. It's not just playing any move, then copying what p2 does in a new game. You specifically have to start with the upper right corner as it is a subset of all other possible moves.
@@lyrimetacurl0I'm not sure what your example counters. When saying "player 1 is guaranteed to win", it is understood that both play optimally. If there is a bad move for player 1, it can't be in the optimal strategy, unless there is nothing better. In your case, player 1 had better moves to choose.
@empmachine I understand the humor, but saying "if you play both sides in a two player game, you should be able to force a win" isn't very surprising. For the computer there is only one solid strategy: "the only winning move, is not to play" from the War Games (1983) movie.
If the actual goal is to win, cheating is always the optimal strategy.
This is evidenced in real life all the time.
A set is good if sum of reciprocal is infinite. Alice wins. Strategy: No matter what Bob chooses, choose the next consecutive series of numbers to get a total sum of 1 or more. This is always possible since sum(1/n) diverges.
I misunderstood the problem as the sum being converging. For that case, though I haven't checked, I think that all Bob has to do is ensure that his number of squares each turn is bounded.
Well stated.
Here’s a simple, precise rule:
If Bob’s last set ended at the number n, then Alice chooses the set from n+1 to 4n. Then the sum of reciprocals of elements of this set is guaranteed to be greater than
n*(1/(2n)) + (2n)*(1/(4n))
= 1/2 + 1/2.
@@seanb6636 I also made the same mistake. In this case Bob can win by choosing only one integer every time. If Alice's series is {a_n}, then a_n < 2n for every positive integer n. So (1/2)*sum(1/n) ≤ sum(1/a_n).
@@user-oe5eg5qx4cthat's a very nice proof. I had the same strategy idea but I didn't manage to prove it works
I remember taking a logic class a few years ago where i first saw a theorem proven by constructing a game where 1 player wins if and only if the theorem is true. And then showing that the player has a winning strategy.
At the time that proof went completely over my head sadly, and i had to drop the course, but still to this day it was the most magnificent proof technique ive ever seen.
Do you remember what theorem it was? Sounds neat
@@jarredallen3228 Unfortunately no. Like I said the topic went completely over my head at the time, and the class had no textbook, so I had to rely solely on my tear soaked notes.
There's a few I've seen that do that. MIP=RE is one
@@martinshoostermananother channel called Thomas Kern has a video on model theory with similar ideas
@@jarredallen3228I have also heard a lot about game theoretic semantics of logic. It's not just one proof but a whole area of semantics for logics, I haven't delved too deep into them but they are defo worth a look
Shockingly good video - pop science levels of understandability and intrigue, but real arguments, definition sketches, and proof ideas!
Fun fact / terminology: the choice of what sets are good or bad is known as an 'ultrafilter'. Definitely up there as coolest term in mathematics! But I had no idea about this strategy stealing property - thanks for the video. Excellent choice of topic - accessible to wide audience, unknown to most mathematicians (e.g. I did not know about it despite knowing about ultrafilters!) and mathematically super interesting.
Edit: I am likely incorrect about saying ultrafilters correspond to choice of which sets are good or bad. See comments.
And i didn't know about any of this after three semesters of Game Theory, was expecting him to whip out Sprague-Grundy but that was even more satisfying. Awesome entry!
For me, meaningless stuff like this is mathematically extremely uninteresting. I like problems that lead somewhere, not vague concepts which lead nowhere because they don't make sense or contradict themselves.
@@Gretchaninov It leads to the concept of measure and the lebegue integral, hilbert spaces, and fourier analysis.
@@stevenfallinge7149 Yes and no. To me, measure and Lebegue integrals were just stupid and unnecessary. Those concepts can largely be circumvented. It's like spending a really long time meticulously creating a bunch of theory JUST IN CASE someone wants to integrate an insanely complex function. But for 99.99% (or more) of all applications, you have smooth, continuous functions or a handful of discontinuities, etc. You make the theory far more awkward for no reason.
Fourier analysis can also be done in 99.99%+ cases just using "normal" maths. Eg) I could assert that every function and number you use must be Turing calculable (which to me is hardly a limitation) and it makes everything much simpler. Worrying about theoretical monsters with uncountably many discontinuities which you can't even explicitly express, etc. - that stuff is of questionable utility.
I don't see how an ultrafilter yields a choice of good and bad sets. For example, any principal ultrafilter doesn't fulfill the condition that changing finitely many elements won't change whether the set is good or bad.
"We somehow get even stranger things if we don't..."
And now you have your sequel video to do because I am definitely intrigued.
The axiom of choice helps you prove elementary, intuitive and useful properties. For instance, you need it to prove that every set has a cardinality, or that if there is a surjection from E to F then there is an injection from F to E. If you don't take the axiom of choice, you can't prove these, which in turn means that there can be set for which these properties fall short. These sets cannot be constructed, of course, but the possibility of their existence makes your nice properties impossible to prove. The intuitive insight to be gained is that the axiom of choice doesn't allow you to build "weird" sets, but forbids "weird" sets from existing in the first place. It forces sets to be nice enough that you can chose from them, giving them other nice properties. Sure, you can build suprising sets with it, but math is surprising at times.
You could go even further and ask for every sets to be constructible, i.e. being able to match every set to a property that define them, and that is even stronger than the axiom of choice. (the idea being that any set of properties can be well ordered, which tranfers to every set having a well ordereding)
6:43 Alice wins. Alice can just keep coloring until she adds at least 1 to her total sum. This is always possible because the harmonic series diverges to infinity. She’ll be doing a lot of coloring though.
does it have to be 1 though ? it could be any fixed real positive number right ?
@@sapri344 It can be any fixed positive number. 1 is the most natural choice in my opinion.
can't bob just do the same after that?
@@youssefchihab1613All that matters is that Alice’s set is good. No matter what Bob does, he can’t stop Alice from adding at least 1 to her total sum, so Alice wins.
the harmonic series diverges, so it diverges regardless of how much of its head is cut off. so Alice can always add an arbitrarily large term on her turn - she wins
I didn't immediately realize you were taking the axiom of choice, but I did see it before you mentioned it, which I'm proud of. I've never taken any classes which go over ZF set theory; all my math classes which used sets just gave an overview of naive set theory and then said "technically this version leads to paradoxes but within the context of what we're learning here, it'll work".
6:38 Red can always win. The key is that for all N ∈ ℕ there exists an M ∈ ℕ such that the sum from n = N to M of 1/n ≥ 1. Therefore red could always add at least 1 to the sum each turn.
And she doesn't have to select a sequence that sums to greater than one on every term. As long as the sums of the reciprocals equal or exceed the succeeding members of a harmonic series (or the reciprocals of the primes!), her sum will diverge.
i love M∈ℕ! 😊
@@colly6022same
Such games (in addition to obviously requiring an infinite amount of time) also require "supercommunication", that is, the ability to communicate infinite amounts of information (in fact, in this case, uncountably infinite amounts of information, in order to describe which sets are good and which are bad). This sort of setup often leads to independence results where the axioms of set theory don't prove or disprove either outcome.
Thank you SackVideo
Only God can judge Alice and Bob
which god in particular?
@@TheEvilCheesecake The only true God 😜
yes so which one?
@@TheEvilCheesecake You tell me
It seems like a never ending game, then. That god you speak of seems rather silent, If not non existent
My favorite quote about the axiom of choice: "The Axiom of Choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's Lemma."
It’s the well-ordering theorem (every set admits a well-ordering), not the well-ordering principle (the positive integers are well-ordered). The latter is obviously true.
What’s yellow and equivalent to the axiom of choice? Zorn’s Lemon.
On the other hand, if you think about how big ordinals are and that they aren't even a set, the well ordering of all sets makes sense. As long as one accepts it's possible to pick "where to go next" an infinite number of times, meaning the axiom of choice.
@@drdca8263 The version I heard of that was "What's small, furry, and equivalent to the axiom of choice? Zorn's Lemming." I like your lemon version better though. I still have no idea what a lemming is, I just know because of that joke that it's probably small and furry.
@@yf-n7710 Lemmings are a species of small mammal. There’s a myth that they follow each-other to the point of following another off of cliffs. This myth gave rise to the video game named after them.
They apparently have population dynamics such that the amount which the produce, combined with how strongly a too-high population impedes them, together results in their population size over time changing in a chaotic way? Or something like that, I might be incorrectly remembering the reason why.
The animations showing internal/external rotation force when using a barbell were the best I've ever seen in a fitness video.
I didn't (yet) get this video as an option in the SoME3 voting, but I will say that I'm pretty sure I would have voted for it. As a person with little math education beyond high school and a semester of college calculus, I found this very accessible and clear, and it was the first piece of math explanation that in any way explained an alternative to the axiom of choice (which I never quite understood why one would or wouldn't "take" it... with most of my prior research being prompted by random xkcd comics)
Absolutely absolutely amazing video! You get a ton of things about being a good math explainer correct, both on the technical “how to I instill this idea” side and the emotional “how do I make this content fun, engaging, and properly motivated” side. Please consider doing more videos on the fundamental axioms of math, it’s a very ripe topic for educational videos.
The "I knew you would've done that so I did the thing that would counter the thing that you would've done", but infinitely and thus first player being unable to make a move, or let's say the winning move .
Also both players having the playbooks reminded me of satire to heist movies in Rick and Morty (S4E3).
I am curious on how axiom of determinancy results in "strange" consequences.
Thanks for the video as always.
Do you know about the game of chance called aviator, using the countering strategy and knowing how some of the scenarios play out in the long term with the odds, could a winning strategy be created?
"For each pair of groups, pick one to be good, and the other to be bad"
me: "hmm, that's gonna be a lot of weird sets, and I have to make a choice for all of them? - oh!"
Feels pretty good that I got there early on this haha
It's a miracle that a chanel that show math in its pure and fun way in such a great manner is free.
Finally a good video explaining AD, but the reason I philosophically feel AD is better is because AD=>ADC=>AC_w. So Axiom of Choice is actually over uncountable sets but AD means we can do Countable Choice & Dependent Choice. So it mostly works
AD is axiom of determinacy, right? But what do ADC and AC_w stand for?
@@yf-n7710 Axiom of Countable Choice is AC_w, The axiom of countable choice or axiom of denumerable choice, denoted AC_ω, is an axiom of set theory that states that every countable collection of non-empty sets must have a choice function.
The axiom of dependent choice, denoted by, is a weak form of the axiom of choice that is still sufficient to develop most of real analysis.
@@yf-n7710 The axiom of dependent choice implies the axiom of countable choice and is strictly stronger.
@@azoshin Ah, ok. Thanks! I'm hoping to learn more about set theory soon; most of my experience so far has been naive set theory because the professors just wanted to rush through it to get to the primary topic of the class.
This is a really great video! I love the subtle connection between taking the top right square in chomp, whether to include the number one in the list of composites, and whether Alice chooses the number 1 in the complement of the determinacy game. These little parallels really help with understanding!
This problem feels basically related to the halting problem and/or incompleteness theorem--It's always possible to pose questions that can't be answered.
Can God create a math problem that he cannot solve? I feel like God could definitely solve the halting problem no problem.
This game reminds me of the prisoner problem where prisoners are lined up, each has a white or black hat, each can see the hats in front of them, and they must guess the color of their own hat. If the prisoners get to plan a strategy beforehand, then for finitely many prisoners, all but the first prisoner can guess correctly. The first prisoner guesses "white" or "black" depending on whether he sees an odd or even number of black hats in front of him, and iteratively the rest of the prisoners in line can figure out their own hat color.
For infinitely many prisoners, they can still do it, but only with AoC. You think of the line of white & black hats as a binary decimal representation of a number in [0,1]. Consider two numbers in [0,1] as almost the same if they differ in only finitely many binary places. The prisoners have to choose a representative from each equivalence class. As soon as the prisoners are lined up, each prisoner can see all but finitely many hats, so each prisoner knows what equivalence class the line of hats is in. The first prisoner says "white" or "black" depending on whether the decimal represented by the line differs from the equivalence class representative in an even or odd number of places. That gives enough information for the rest of the line to iteratively figure out their own hat color.
Of course, the problem is that this requires actually specifying one representative from each equivalence class of [0,1] up to AS. With no systematic way to make such choices, no amount of prep time will save the prisoners.
The finite version can be extended from 2 colors (black and white) to any finite set S of N colors. The prisoners agree on a bijection S→{1, ..., N} and proceed via "summing" the colors they see mod N, etc.
the infinite version can be also extended to N colors by working in base N.
15:18 I like the eyebrows' movement on mention of Vsauce
Your videos are great, keep it up!
Thank you! Love and blessings.
That was amazing! Thanks. Now I have to watch it all over again a few more times.
I'm a fan of Koenig's Lemma: any tree with infinitely many nodes and finite branching has an infinite branch. It's equivalent to what I call the Bush Theorem: any tree with finite branching and finite branches has finitely many nodes. I consider that intuitive. Koenig's Lemma implies the Compactness Theorem: for any set of statements, if every finite subset is consistent, then the set as a whole is consistent. This in turn implies nonstandard analysis, which has genuine infinitesimals. It also implies the Lowenheim-Skolem Theorem, which says that set theory has countable models. Since I've had it up to here with transfinite cardinals, this appeals to me.
Koenig's Lemma is a weak version of the Axiom of Choice. My question is: is Koenig's Lemma consistent with the Axiom of Determinacy?
Apparently Konig's lemma requires only countable choice. AD implies countable choice.
Thanks for the video, bro!)
Very well explained ! 😀
Well done, great video
Haven't watched the video yet, but I still remember the degree to which various "games" were used in a lecture series I've attended about (descriptive) set theory was both surprising and enjoyable.
since the sum of all reciprocals diverges, any tail of that sum diverges, so there exists a point in every tail such that the sum of terms before it are bigger than any desired M, so alice would only need in her nth turn to pick the integer in a way so that the freshly colored in red terms reciprocals sum to something at least as big as the next term of her decided diverging series, perhaps 1+1+1+...
For the opposite of the 1/x->inf game where a set is good only if it's sum converges, Player 2 has a winning strategy. P1's best move is to always choose only the first element after P2's, so P2 can force P1 into taking, at most, the series 1+1/3+1/5+1/7+1/9+...
1+1/3+1/5+1/7+1/9+... is still a divergent series. You can decrease the series by making each of the summands smaller, which could be done by increasing each summand's denominator by 1. Doing this, you get 1/2+1/4+1/6+1/8+1/10+..., from which you can factor 1/2 to get 1/2 (1+1/2+1/3+1/4+1/5+...), which is 1/2 multiplied by a divergent series.
That being said, it's still possible for P2 to find a winning strategy if P1 always chooses just one element, because P2 could always force the next element's index to be the next square number, so the total sum would become 1+1/4+1/9+1/16+1/25+..., which is equal to π²/6. But this just shows that "always choose just one element" is not a good strategy for P1, because when P1 is left with choosing index N as their first element, they can just choose N more elements. Each of the elements they choose will be at least 1/2N, because the sequence is decreasing and 1/2N will be the last element they choose, so in total, their choice that turn will be greater than N * 1/2N = 1/2. Because they'll have infinite turns and each turn will get them more than 1/2, they'll be able to force it to diverge with that strategy..
An amazing video!!! Hope that it wins 🙏🏻
A brilliant video!
That seems like circular logic. Alice is stealing Bob's strategy while Bob is stealing Alice's strategy. How can you draw a logical conclusion from that?
The logic is as follows:
Alice can't have a winning strategy because otherwise Bob could steal it.
Bob can't have a winning strategy because otherwise Alice could steal it.
Hence neither player can have a winning strategy.
It's: assume that Alice knows how to garuntee a win.
The rules say that for Alice to win she needs to have a set that's almost the same as some set.
This means that Bob would have the complement of that set.
But Bob can choose to take a set that's almost the same as the set that Alice would have taken, forcing her to lose instead, contradicting our assumption that she can guarantee a win for herself.
Likewise, we can make the assumption that Bob can garuntee a win for himself, but Alice can choose to make moves based on what Bob would have done to take that win for herself. So that assumption leads to a contradiction and so cannot be true.
@@ASackVideo do you mean to say that determining goodness is nontransitive?
To me, it's more surprising that games of this type are *ever* determined than that you can make one which isn't. For definitions of 'good' which involve infinity, in some sense, the first N moves are completely irrelevant, no matter what N is, even for much more reasonable definitions of good like the one where a set is good if it contains infinitely many primes. Like, you could make an arbitrary number of moves completely at random and it would fundamentally have no impact on the game because infinitely many moves remain. In that context, its almost like the game never even starts! After any number of moves, if you ask Alice and Bob how the game is going, they'll both tell you 'I'm infinitely far from winning'.
Perhaps another way to think about it, is there's uncountably many possible definitions of 'good' (though we can only describe countably many of them with language; you need to rely on the axiom of choice to access the rest). There's countably infinitely many possible strategies, so you can't have a winning strategy for every game, because there aren't enough to go around. (There's a lot more work to formalize this because a single strategy can work for multiple games, but this feels like a good intuition).
I think the number of strategies is uncountably infinite. If F is a function from positive integers to positive integers, there is a strategy instructing alice to always add F(n) new numbers to her set, where n is the smallest number she can add. Therefore there are at least as many strategies as there are functions from positive integers to positive integers. The set of such functions is uncountable.
Your intuition is correct that the number of possible definitions of 'good' being larger than the number of possible strategies. However, they are both uncountable! I think it is the following:
- number of possible strategies has same size as the set of reals.
- number of possible definitions of good has same size as the set of all subsets of the reals.
In mathematical notation, you would say the sizes are 2^aleph_0 and 2^(2^aleph_0)
@@TheManxLoiner Ah of course that's right. I was thinking about the number of *computable* strategies, but there's no reason a strategy has to be computable in a game as abstract as this.
One thing which is important in my opinion when it comed to banach tarski paradox. While initially the sphere is being cut in 5 pieces which then get rearranged, at some point the process goes beyond just rotation and translation precisely twice. One time when we "add" the missing center of the sphere and another time when we extend a circle with one point missing to a whole circle. On infinitely many circles. So in a way we literally add a surface worth of "stuff" plus we add a point. Those operations dont conserve neither volume not surface area. Also the center point of the sphere is added from a set of infinitely many lines with one point missing, which are arguibly equal to whole lines, but my point is, instead of 0D point we add 1D "still-point" which along the 2D "surface-worth" of points gives us exactly what we are missing. A 3D manifold with a 2D manifold as a boundry.
On the topic of the game: the logic goes along with the idea, that there is a book available to the player/players with the winning strategy for every move their opponent makes. One might argue that such book can not exist at all or at least there cant be two books with both having the property of containing the "perfect strategy".
Here's a "Makes A Set Good" for Red: "Good" is if the Red Set contains a string of numbers that, if appended together, is evenly divisible by all numbers in the Blue set.
Love it!
Interesting video. Another channel just came out with a good video on infinite chess which I've seen come up in introductions to tge axiom of determinacy. Also you should tag this with #some3 to boost it
The channel for the video you are talking about is Naviary, i am assuming.
A few notes:
1. The 1/x always diverges because of the limit definition. For any given finite number there exists a strategy for Red such that the sum of Red cells will be greater than chosen number.
2. Is the condition «There are more Red elements than Blue elements» determant? Who wins such game?
Your condition (2) is very easy for Bob, isn't it? No matter what strategies each player uses, both sets will be countably infinite, and all countably infinite sets are the same size. So red can't be larger than blue, even if Bob always chooses to color just a single element.
A winning player 1 strategy for chomp is to pick the square diagonally up and right of the poison one, splitting the bar into two play areas,. This is a guaranteed win on any square starting set up, as no matter how many pieces player 2 removes from one area, player 1 removes the same from the other area until both areas are gone, leaving player 2 with the last piece. On a non-square set up the aim is to get an equal number of pieces in each area to guarantee the win.
I appreciate the video was not specifically about this game, but I thought I'd help you get a little payback with the online version 😁
That doesn't work for a non-square set, as after player 1 chomps the square diagonally up and to the right of the poison one, then player 2 can make the two "arms" - which were unequal in size after player 1's first move - equal with a single chomp.
Great vid, I thought this was an nice and gentle introduction to AD.
An alternative indeterminate game: pick a function f from the set of infinite sequences of {0,1} into {0, 1} such that changing one of the bits always changes the result (aka "infinite XOR"). Players 0 and 1, in their turns, can write any non-empty finite sequence of bits (e.g. player 0 writes "010", player 1 writes "111", player 0 writes "00000", so on). The winner is f(infinite sequence obtained via concatenation) (e.g. f(01011100000....))
(Seems quite similar actually.)
0:05 me when my favorite game is seeing how many times I can punch a pair of kitchen scissors before my hand becomes permanently mushed into the perfect shape >:)
I was aware of strategy stealing, because I'm aware of it in the context of actual games and game design (not just theoretical games), but I was not aware of this particular application and surrounding axioms. Interesting.
I can win chomp pretty much every time. The win condition I noticed was having the opponent to play, and only the left two columns are filled in except for the top right most square (7 blocks in total left). To get to the win condition, take out top right corner pieces until the bot removes the top square on the second from left column.
I've never understood why the Banach Tarski Theorem is so weird or scary to people, and yet if you tell someone to scale a rectange by a factor of 2 in the Y direction they arent blown away that you suddenly have two rectangles of the original size. Its basically the same thing, youre just translating all of the points from (x,y) -> (x,2y), youre not "adding" any new points, just moving them, yet you get twice the area. But people dont seem to find that as surprising as banach tarski.
But here, aren’t we breaking the rectangle into uncountable many sets, rearranging them, and getting a new area? Whereas with B-T we are breaking a sphere into finitely many sets rearranging them and getting a new volume.
The latter seems much weirder than the former.
Indeed, isn’t it the case that there is no equivalent to B-T in the plane?
Note I am almost as far from being an expert on these topics as it is possible to be. I did them at university about 35 years ago and didn’t really understand them then. So everything I say could be rubbish!
Scaling seems more obvious a process that changes volume, but isnt with BT the strangeness that all the individual steps would seem to preserve volume?
The equivalent to B-T on (let's say) a unit square wouldn't be simply stretching it by 2 in one dimension and then cutting it in half to make two unit squares. A better analogy would be:
- color every point in the unit square, using a finite number of colors
- for each set of all points of a given color, you may move that set around by translation and rotation *only*. (No stretching.)
- move the sets to make two complete unit squares.
The thing that I think saves AC is that basically all the weirdness it produces only shows up in situations that are already outside human intuition. B-T already requires the idea that you can get a finite volume from an uncountablely infinite collection of items that each have zero volume. If I'm willing to accept that, then B-T doesn't seem *that* strange. Most other AC strangeness I've looked into runs into the same kind of "but first ..." assumptions.
The act of sussing out (or deducing, or stealing) an opponent's strategy is referred to as 'leveling' in the game of poker. Obviously, nearly all other games also make use of such tactics. But the manner in which this was covered in the video really reinforced that leveling is a good (and tidy) word for such ongoing machinations. That said...whatever the game...always be careful with your leveling lest you level yourself.
Ok this was f-ing fascinating
Great video I absolutely adore combinatorial game theory! Just one question (maybe I missed it in the video): Why can we apply the Zermelo Theorem if the theorem is only applicable for finite games? Games that do not end in a draw but take infinite steps are not finite or are they?
Thanks! Correct, Zermelo's theorem doesn't apply to the determinacy game. That's why the Borel determinacy theorem is an extension of it and why we'd need the axiom of determinacy for all determinacy games.
“Alice and Bob color numbers forever and Alice wins iff she colors in the good numbers” is such a funny description
for your challenge i think alice can always get a good set by going from N to 2N therefore increasing it by a half or more
We could just say red is a good set if it contains more numbers than the blue set. Then both blue and red would have a winning strategy by just choosing an amount of numbers bigger than the difference to the other set
6:41 This does not actually require calculus, except for the definition of a diverging series which does not depend on much calculus.
Alice wins. This is surprising on some level because the harmonic series converges with quite a few ways to take out infinitely many terms, but because the entire series diverges, at any point you can always choose enough terms to add to 1. Alice just needs to choose some number (1 in my example but any positive real would work, or even any diverging series) and ensure that each term she grabs enough numbers to add to at least that much.
In this video, you have shown Determinacy NAND Choice. But then you spoke as though we had Determinacy XOR Choice. Is ZF, no Choice no Determinacy, thought to be consistent?
Nice video
14:10 "If you want to make infinitely many choices you have to use the axiom of choice" - not necessarily. The axiom of choice is that you can _always_ make infinitely many choices. For some sets you can prove that you can make infinitely many choices without the axiom of choice, like the natural numbers: you can always choose one natural number from a set of natural numbers by picking the smallest one.
It's not even necessarily true that you can't specify how to make the choices in this particular case. There is a formula that might define, for _every_ set, a way to pick one element from it ("might" in the sense that you can't prove it does but also can't prove it doesn't (assuming ZF is consistent)). It's just that there's no formula that _provably_ defines a way to choose which sets are good and bad (assuming ZF with the axiom of determinacy is consistent, this might be provable from weaker assumptions but I don't know how).
Hello. May I add this incompatibility argument to wikipedia: Axiom of determinacy? (After the existing argument, which uses the very technical well ordering of the continuum.) I would probably not give any attribution, as the current argument does not give any attribution.
If you'd like a source, I'd recommend Proposition 28.1 of The Higher Infinite by Akihiro Kanamori. This argument actually shows something slightly stronger than AD and AC are incompatible: It shows that AD implies there are no non-principal ultrafilters over ω. (In the video, we use AC to construct a non-principal ultrafilter. However, the existence of a non-principal ultrafilter is weaker than AC.)
@@ASackVideo Added. I also added a talk section to try to smooth things over with the estabilshed math editors.
Correct me if I’m wrong, but would the determinacy game not open a can of worms of self reference? Like saying a set is good only if it causes Bob to win? Or am I just going off the rails because I haven’t seen the whole video/read the whole ruleset.
No there is not a self reference thing going on here. You specify upfront which sets are good and which are bad, and then ask if Alice or Bob have winning strategies.
Has it been proven whether both the axiom of choice and the axiom of determination being false leads to a contradiction?
6:39 alice wins. Since the harmonic series diverges she can always color enough squares to equal (exceed) 1 at every step, no matter how much bob colors before. 1+1+1+1+1...=infinity
Might the axium of choice vs the axium of determinacy have any implications for the real world, the universe, snd free will or not.
That first part was confusing. I would say: assume that player 2 can win whenever player one plays anything other than the top right corner. Then if player one plays on the top right corner, he forces player 2 to make one of the moves which he would have needed to make, so that he (player 1) becomes the one with the winning move.
That means it's impossible for player 2 to have a winning move for any possible play by player 1.
Despite trying a lot and even looking up a paper on how to win at chomp, we can't for the life of us manage to beat the CPU in that online chomp game you linked. If anyone else is able to beat them please let us know how, it's so frustrating hearing that it's possible but not being able to see how
alice wins the reciprocal game,
whatever bob chooses, alice can keep picking until the sum of reciprocals increases by 1 or some other fixed number, so every turn she gets +1 and since there are infinite moves, her sum diverges
I wonder if there are alternatives to the Axiom of Choice and the Axiom of Determinacy.
I came up with a weird example for Alice and Bob coloring the number line and I'm not sure how (or if) Alice or Bob can obtain a winning strategy.
The goal is similar to the video's challenge problem where Alice's set is "good" when the set of reciprocals of Alice's red numbers must diverge to infinity. However the key difference is where Alice wants both her set and Bob's set to diverge to infinity when summing the reciprocals. All Bob needs to do to win is ensure at least his or her set converges to a finite value when summing the reciprocals.
I haven't spent too much thinking on this problem, but it seems like there isn't a winning strategy for either side.
Alice wins by adopting the following strategy:
1) On each turn, color just 1 number until Bob has colored numbers summing to over 1.
2) On one turn, color enough numbers to sum to 1.
Repeat.
super cool
“Most mathematicians still prefer to take the axiom of choice.” This is a very diplomatic way to not offend constructivists. Lmao
Can you do a video on ultra filters too please?
Sounds like the halting problem, revisited. Which is, of course, also the Goedel incompleteness theorem all over again.
I feel like I missed some parts of the video, but I can't find them. Can someone give me a timestamp for:
Where the axiom of choice was described
Where determinacy and choice were proved to be incompatible
It's near the end
The different axioms make me think of some made up DnD mathematician subclasses for some reason.
No doubt members of the Fraternity of Order from the old Planescape song.
I’m glad this was recommended to me! How did you achieve such clear speech in the video? Do you prepare a script, or understand it deeply?
Thank you for the nice comment!
I script out my videos and then film each line a few times until it sounds right. This video took about 3 hours to film and a lot longer to edit. The script changes a little while I film because some things sound normal written down and sound less natural when spoken.
Thank you!
@@angry4rtichoke646Also the microphone quality itself is really good which, at least for me, can make these kinds of videos much more approachable.
I believe Alice wins the determinacy game at 6:37
The sum of all reciprocals of positive integers greater than some number _N_ diverges. That means that Alice can always reach or exceed some finite value _Z_ on their turn. Make Z be equal to 1/t, where t is what turn Alice is on. Since the sum of all reciprocals of positive integers diverge, and since Alice's series is greater than that sum, it also diverges.
The banach tarski paradox provides a counter intuitive consequence of accepting the axiom of choice... is there a counterintuitive consequence of the axiom of determinacy?
This game seems to have strong ties with Turing machines and the halting problem.
Yes and no.
You could probably write an entire thesis, or several thesises on why the ideas here are both kind of related, kind of the exact same thing, but also kind of completely unrelated, independent phenomenon.
@@martinshoosterman I feel like they are essentially the same problem...if you have some reasoning as to why they are different then say so, but to me they appear to be the same.
@@kingacrisius I'm glad you feel that way. I would encourage you to explore the topic deeper and try to see for yourself.
It's an extraordinarily deep topic, and also very technical. There is no simple answer.
@kingacrisius yes I think so as well, simply assign each Turing machine to a natural number, and let's say the good set is the set that only contains finitely many TMs that halt on input 0. Then Alice's and Bob's strategy books must not exist, therefore there are no winning strategies.
That is unless they are both using Oracle machines in their strategy books, then the Oracle machines can answer the halting problem and deduce which set of numbers to pick.
@@byprinciple4681 the second you talk about having infinitely many Turing machines, you no longer are talking about anything related to the halting problem.
2:26 I have a counter example to the first player could have always made a move to make the same game state as after the second player's first move. If instead of the top right I go one to the left of the top right and then the second player plays one below the top right, the resulting game shape is an inverted L removed from the top right.
There is no way to make an inverted L shape with one move...?
The claim is that player 1 has at least one first move that can guarantee a win, not that every first move player 1 makes can guarantee a win.
Is the "Plan", where we assume A~B →Good(A)=Good(B) and that Good(A)=!Good(Comp(A)), the constraints on what games the argument applies to? The way they are introduced kinda sounds like it's saying that those are always true for *all* games, but that's clearly not true (it's not true for any game that can be won by either player in finitely many steps, e.g. "good if contains 6").
Sorry if it's unclear: The goal in that section is to build a game for which the plan holds.
@@ASackVideo Cool. While writing that comment I actually went back and realized it didn't say it's true for all games, thus my question.
FWIW, I've run into more than a few cases my self where the fact I already knew what I was saying made it hard to figure out how people could/would misread what I was saying. What little progress I've made on that problem has usually involved repeatedly realizing I'd yet again stubbed my toe on it.
I think this becomes solveable if we assume that there is a final turn and we can determine who gets it. In that case, whoever gets the final turn loses, and the game plays out recursively.
If we don't assume the game has a final turn then maybe we don't have to assume the game has a starting turn either? What would the ramifications of that be? Is that a silly thought?
8:52 why the 2nd claim tho?! Doesn't the earlier "infinitely many powers of 2" description for a "good set" mean that it's perfectly possible to have both A and A' as good? (Bonus, this would allow for a winning strategy for the first player, too!)
It’s possible in general for both a good set and its complement to be good. (For example, take the game where every set is good.)
We want to build a special game where good and bad sets are always complements
I may have missed something but what is both the red and blue are "good" then Alice is garunteed a win, right?
1:24 It's kind of jumping to conclusions there. That just means it guaranteed won't be a draw. There's no way to tell if you can force a win or loss besides knowing the actual game rules.
Unless there's some proof that you can swing the odds to 100%. I mean I can see increasing them some but not guaranteed having a win. For example one game might have player 1 go first, if the scores tie then player 2 wins, and they do whatever actions to earn points.
how come a set with infinte member and not a single one of them is same, yet every member of them is only different by a finite amount ?
I am a bit confused by the example of the finite and cofinite separation. Obviously, if the good sets are all finite sets, then Alice doesn't have a winning strategy, and Bob is guranteed to win, right? Since she has to choose an infinite number of numbers. So what exactly is the paradox in that situation
In the game we built, we wanted the complement of any good set to be a bad set and the complement of every bad set to be a good set.
If you take the only good sets to be all finite sets, then the set of primes is bad, but so is its complement.
8:53 I'm confused about condition #1. Let's say that good=only odd numbers, and your set is all odd numbers. Then I can add a random even number and make the set bad.
This property doesn't hold for all determinacy games, only for the special one that we build to be undetermined.
Winning strategy for chomp: Start by eating the whole chocolate bar, and spit out the poisoned square.
15:40 It's somehow stranger if we don't take the axiom of choice? Please make a video explaining this.
To win Chomp the first player must always force the remaining block to have an even number of required moves.
There is one thing that was unclear for me. At 11:14, when you say that you’re telling them which sets are good and which are bad, do you mean across all possible pairs of groups?
Yes. (Or we tell them which sets individually are good/bad, where a set is good if the group it's in is good.)
Okay so i didnt study math as a career i mostly learn from youtube videos. As i understood the harmonic series diverges to infinity cause you can proof thar a series lower than it also does it. That series being 1+1/2+1/4+1/4+1/8+1/8+1/8+1/8+1/16... where you are always summing half with each 2^n terms (yeah i dont know the name of this series and i dont know how to write it in math terminology). The question now is, some comments say that you can always make plus one with a set which is true. But the comments state that the set has to add to 1 or more. Why? Wouldnt 0.1 work too? Or whatever number as long as its always the same? Because the game is played over infinite numbers you can just make each set add to 0.1 because 0.1*infinity is infinity. You could say its 10 times slower but yeah i dont understand the +1 or more
Would the case of "A set is good if red has more squares than blue" ne indeterminate, since both players can always make their set larger than their opponents, or is that not the case?
What does it mean to have more red squares than blue if both have infinitely many?
Please forget my lack of mathematical rigor, but I'll try proving that A and the complementary of A are essentially different.
1/ let's note the complementary of A A'
2/ let's chose A={ }, so A'=Z+
3/ making A and A' equals mean either removing all positive integers from A', or adding all positive integers to A
4/ Z+ is infinite, so either way it would take infinitely many steps
5/ in this configuration A and A' are essentially different
6/ now take any positive integer n from A' and move it to A, meaning we remove n from A' and add n to A
7/ now A={n} and A'=Z+/{n}, so they are still complementary
8/ similarly to 3/, making A and A' equals means either removing n from A and all positive integers except n from A+, or adding n to A' and all positive integers except n to A
9/ because Z+ is infinite, there are infinitely many positive integers greater than n
10/ so the set "all the positive integers except n" is also infinite
11/ so similarly to 4/ making A and A' equal would take infinitely many steps
12/ so A and A' are still essentially different in this new configuration
13/ ok I'm stuck here, right at the conclusion. My instincts tell me than we can go from the empty set to any subset of Z+ by just finitely or infinitely adding positive integers to it, meaning that by repetition of the step 6/ we could "hit" any possible configuration of A and A'=Z+/A, and by virtue of the step 12/ they'll always be essentially different.
But I've read anything I could find about this, and it's either false/not proven/not provable, or I lack the specific terms to look for it.
This is continuous math. The set of red positive integers is the same as an assignment of one bit to each positive integer. The number of sequences of aleph-null bits is c, the number of reals. In terms of cardinalities, a rule about which sets of positive integers are good is the same as a rule about which real numbers are good. So, continuous math. The game bent my mind at first, because I was erroneously thinking of it as all about countable cardinalities. Intuition does not cover continuous math, so whatever happens should not bend ones mind.
So for the infinite primes game, if Alice chooses all squares up to the next prime, then Bob chooses all squares up to the next prime, then both of them would have a Good set, and so the complement of a good set is not necessary bad. Am I missing something here?
Bob wins if the red set is bad, not if the blue set is good. The complement of a good set is not always bad, but we built the "undetermined" game specifically to have that property.
That was an automatic subscribe.