An impossible game at the heart of math
Вставка
- Опубліковано 25 вер 2024
- 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....
Wikipedia article: en.wikipedia.o...
List of known best first moves: sites.math.rut...
Also check out chapter 18 in the book "Winning Ways for Your Mathematical Plays"
Zermelo's Theorem: en.wikipedia.o...)
_____________________
The Axiom of Determinacy:
Wikipedia article: en.wikipedia.o...
Borel Determinacy Theorem: en.wikipedia.o...
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.n...
_____________________
The Axiom of Choice:
Wikipedia article: en.wikipedia.o...
Banach-Tarski Paradox: en.wikipedia.o...
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.
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.
@@sussybawka9999 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).
@@周品宏-o7wthat's a very nice proof. I had the same strategy idea but I didn't manage to prove it works
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.
Shockingly good video - pop science levels of understandability and intrigue, but real arguments, definition sketches, and proof ideas!
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
"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)
Just one simple example of something you'd have to discard without choice is the "Trichotomy Law", which says that for all numbers x and y, either x
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.
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".
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.
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
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.
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.
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 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)
Has it been proven whether both the axiom of choice and the axiom of determination being false leads to a contradiction?
If the Axiom of Choice is true then there exist sets that are neither Good nor Bad.
It is consistent that neither AC nor AD is true. They are contrary, but not opposite.
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?
"When you told me to meet you at Castle Terserus, I simply travelled back in time a hundred years and I bribed the architect. Say hello to the spikes of doom!"
"Say hello to the sofa of reasonable comfort. Naturally I anticipated your journey back in time, and so I travelled slightly further back and bribed the architect first."
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
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!
I think I get the idea of backwards induction to win Chomp.
You need to achieve a board state where:
1. There are only two non poisoned blocks left
2. It's your opponent's turn to move
Lets call this S1
Then you have to achieve the following:
1. It's your opponent's turn to move
2. All of their moves will either lead to an immediately llosing state or allow you to achieve S1 on the next move. We'll call this S2... And so on
6:38 Since the sum of the reciprocals of the natural numbers diverges (harmonic series), it's always possible for Alice to choose enough numbers each turn such that the sum of their reciprocals is greater than any finite number you choose. As long as they are consecutive (because of the way the game works, they must be) and she chooses enough of them (there is no limit to how many she can choose), it doesn't matter how large the numbers get. So no matter how many numbers Bob chooses, Alice can always choose enough numbers to increase her sum of reciprocals by some number greater than 1 for example, guaranteeing her sum diverges and her set is good.
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.
Thank you SackVideo
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.
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.
It's a miracle that a chanel that show math in its pure and fun way in such a great manner is free.
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.
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.
@@ictogon yes he can create such a problem
@@ictogononly with infinite time could you solve the halting problem, as you can simply wait and see if they halt or not, but that obviously takes a while
@@gabes6108 yes but God can think infinitely fast
"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
I am a mathematician and already knew about Determinacy ... and still, I think this is a brilliantly informative video.
The animations showing internal/external rotation force when using a barbell were the best I've ever seen in a fitness video.
I LOVE this channel soo much!
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.
Your videos are great, keep it up!
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.
That was amazing! Thanks. Now I have to watch it all over again a few more times.
Thank you so much for making this video! I've tried to understand the axiom of determinacy before but the wikipedia page always loses me haha
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..
Thank you! Love and blessings.
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.
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.)
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.
“Most mathematicians still prefer to take the axiom of choice.” This is a very diplomatic way to not offend constructivists. Lmao
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.
Alice and Bob, the eternal victims of mathematical games.
I think that what Banach-Tarski actually shows us is that our human intuitions when it comes to measure theory when applied to infinite sets are screwy. There's no paradox at all. It's just that infinities don't work the way that finite numbers work, and our minds are not used to dealing with infinities.
I am not actually certain that there are any infinities in the real world. There may be a smallest unit of time, a smallest unit of space, and the universe may be finite. It can be very large but still be finite. Infinities would still be very handy tools for calculation in such a world. But otherwise they may just be mathematical games. Or maybe there are infinities, but we still don't normally deal with those in our everyday lives on the level on which we live.
Thanks for the video, bro!)
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.
10:51 Axiom of Choice! [meme with Dicaprio pointing at tv]
“Alice and Bob color numbers forever and Alice wins iff she colors in the good numbers” is such a funny description
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?
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.
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.
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.
How can the game ever be over? The game never ends.
Loved this video!
A set is good if, for a set n, the following is true: for numbers k1, k2 both less than an odd number 2n+1, k1 (let's say this is chosen by Alice) is either the same parity as (and smaller than) k2, or the other parity and bigger.
Assuming k1 and k2 are different, these are the conditions for Alice to win. The conditions for Bob to win are just swapping k1 for k2.
However, this is not determinate: if k1=k2, that's a tie.
You might recognize this game- it's Rock Paper Scissors (the case of n=1) and beyond!
A brilliant video!
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.
Great vid, I thought this was an nice and gentle introduction to AD.
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+...
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".
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.
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.
Thank you so much for this great video!
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
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.
Actually, condition (2) doesn't necessarily result in a defined winner, and thus isn't a proper way of defining good/bad sets. The ratio of Red to Blue might not converge, and can oscillate back and forth forever between favoring Red or Blue; for example, if the players pick subsequent powers of 2, the ratio oscillates between 1/3 Red and 2/3 Red (and more extreme strategies can push this closer to 0 and 1, respectively).
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.
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
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.
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.
Doesn't Bob's set in the power-of-two example also include infinitely many powers of two?
I feel a need to point out that *actually* playing any of these determinacy games in finite time needs to be a supertask or it would take infinite amounts of time to play out.
I wonder if there are alternatives to the Axiom of Choice and the Axiom of Determinacy.
To win Chomp the first player must always force the remaining block to have an even number of required moves.
An amazing video!!! Hope that it wins 🙏🏻
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
That was an automatic subscribe.
0:03 That’s dangerous!!!
Love it!
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
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
"A set is good if Alice goes last."
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?
I protest the alice & bob coloring game proof
The chance bob colors a prime for a range n is always non zero, since there are infinitely many primes in the real number line. The competition isn't who has more primes, it's whether their set has infinitely many of them, and infinity / 2 is still infinity
There's a really nice problem that demonstrates this perfectly: The Infinite Monkeys Theorem. It basically says if there's ANY non zero chance of something happening, but that chance happens infinitely many times, it is guaranteed to happen as the limit approaches 100%
The powers of two game is also completely false, because if Alice just does the same, BOTH are guaranteed to lose
In the primes game, Alice wins if the red set has infinitely many primes and Bob wins if it does not. The blue set doesn’t need infinitely many primes for him to win.
Similarly, for the powers of 2, Alice wins if the red set has only finitely many powers of 2 and Bob wins if it does not. It doesn’t matter what’s in the blue set.
Ok this was f-ing fascinating
15:18 I like the eyebrows' movement on mention of Vsauce
i think this video would've been better if a brief exposition of equivalence relations and classes was given. i dont think equivalence relations are an especially difficult topic that wouldve taken too long to cover, and it would avoid having to use nonstandard terminology. for a viewer who is not very familiar with higher mathematics, i'm sure the video was good, but it was more difficult to follow as someone somewhat familiar with the topic, as the terminology was changes to make it more accessible (also didn't help that i was listening to it while driving, so it wasn't getting my full attention).
other than that, it was a good video.
I can't help but think of Sudoku when people talk about axioms, because some of the layouts you end up with in a game of Sudoku leave you with many cells in superpositions, and they can't be resolved until you follow a long line of implications that eventually lead to the contradiction you need, which finally allows you to eliminate at least one possibility from one of the cells. Sudoku boards are finite, though, and math isn't so finite, so I don't expect many foundational axioms to become perspective-agnostic theorems. I've only just become aware of the axiom of determinacy, and of the fact that a well established axiom is incompatible with the AoC, because of this video, so that's neat.
12:30 okey yeah but then maybe bob has a second book (and an infinite family of them) in case Alice changes the roles once (and many times after)
I just don’t understand why you need the axiom of choice to describe good and bad sets of natural numbers. Specifying which sets are good and bad amounts to having a function
f : P(N)\{{}} -> {good, bad},
where the domain is the power set of the natural numbers minus the empty set. This exists by the axiom of the power set.
There are many such functions that can be precisely described by a rule, such as the examples in your video. Some rules are decidable in finite time, some are not. But that’s another matter.
This is not equivalent to specifying which sets are good and which sets are bad. For example, the constant function sending everything to be good is such a function, but does not work with our construction.
In the almost-same game, is it possible to come up with a finite description for even one way of categorizing good/bad sets, which fully characterizes which sets are good and bad? I've tried, and can't seem to do it without breaking the game's rules. Is it absolutely required to make an uncountably infinite number of arbitarary decisions (as per the Axiom of Choice) to even come up with one good/bad set categorization?
Yes that's correct, you need to make uncountably many choices. The Axiom of Determinacy implies the Axiom of Countable Choice in fact.
@@ASackVideo Thanks for your answer. I wonder if you could please just clarify, do the choices have to be arbitrary? Is it in fact impossible for them to follow the logic dictated by a finite set of instructions on how to make all the choices? And if so, is there a proof for why that is the case in this game?
I'm not a logician so I may be mistaken but I believe that you're essentially asking for a choice function constructible in ZF, and I believe that is impossible in this case.
For a similarly impossible task, try construction a rule that can pick an element out of an arbitrary set of real numbers.
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.
Very well explained ! 😀
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
What that tells us is that the property of "having more red than blue" can be undefined (by not converging). To define good/bad sets this way, you'd also have to define non-converging sets to be one or the other. Say we define them to be "good". Then picking an exponentially bigger number each time would only be a winning strategy for Alice, and Bob has no winning strategy, because if tries to win using Alice's strategy, the ratio of red to blue won't converge and she'll win, and if he manages to cooperate with Alice to make the ratio converge, it'll have more red than blue and Alice will still win.
@@davidellsworth4203 there isn't really a reason to assume converging being good (or bad) though. Imo opinion it would make more sense to have it be it's own category
@@thetruetri5106 By the rules of the game, all sets have to be good or bad. But I also just realized that, since the complement of a good set must be bad (also by the rules of the game), this means non-converging can't simply be categorized as good or bad, because the complement of a non-converging red/blue ratio set is also non-converging.
Come to think of it, I can't think of *any* way to characterize, with a finite description, one particular categorization of good/bad sets consistent with the rules of the game. Maybe the only way to come up with such a characterization is with an uncountably infinite number of arbitrary decisions, and it's impossible to finitely describe even one way of doing this?
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.
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.
Well done, great video
Sounds like the halting problem, revisited. Which is, of course, also the Goedel incompleteness theorem all over again.
I may have missed something but what is both the red and blue are "good" then Alice is garunteed a win, right?