ฝัง
- เผยแพร่เมื่อ 22 พ.ย. 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
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.
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".
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
Thank you SackVideo
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
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 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
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)
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.
I think Alice has a wining strat for the divergent series game: let’s say bob picks n the previous turn, if Alice picks 2n you can show that the partial sum(or Cauchy slice as the kids say) of 1/k from n to 2n is more than 1/2. Thus Alice’s series diverges
"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
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!
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.
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.
It's a miracle that a chanel that show math in its pure and fun way in such a great manner is free.
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 am a mathematician and already knew about Determinacy ... and still, I think this is a brilliantly informative video.
This is the first time I heard about this conflict I wish I knew earlier. Very well explained, well done.
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."
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.
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.
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.
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.
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
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.)
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.
The animations showing internal/external rotation force when using a barbell were the best I've ever seen in a fitness video.
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..
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 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.
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".
That was amazing! Thanks. Now I have to watch it all over again a few more times.
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.
Your videos are great, keep it up!
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.
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.
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+...
I LOVE this channel soo much!
Thank you! Love and blessings.
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
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.
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
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.
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.
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.
For the chomp game, I feel like the size of the board wouldn't matter based on the rule that a bite removes all squares above and to its right. That would imply that there's invariance along the diagonal direction. And since it's between two players, each possible next move between the players alternates between the optimal and worst next move. Both having just the left-most column including the poison as your next turn is best as well as having just the bottom-most row is also best, assuming you wisely bite off the piece adjacent the poison. So the game is reduced to whoever gets the winning position first because it's possible for them to jump to the last possible winning position or gradually converge to it as long as they don't make a (knowable) unwise move.
For example, if it's your move, you'd want to bite the upper right diagonal piece beside the poison, forcing the opponent to take their best (but still not globally best) move of the adjacent piece above or right of the piece, always leaving you the final winning move. So the outcome of the game with two fully rational players is decided simply by whoever goes first (who can always be forced to be the loser).
Sounds like the halting problem, revisited. Which is, of course, also the Goedel incompleteness theorem all over again.
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!
An amazing video!!! Hope that it wins 🙏🏻
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:29 First player picks a number out of (0, 1) and keeps it secret. Second player picks from the same pool and both numbers are uncovered.. If the numbers are equal, the first player wins. Otherwise, the second player wins.
Finite? Definitely, there's one turn. Draws? No, two numbers are either equal or not.
Suppose either player has a winning strategy, picking a number based on everything he knows which doesn't include the other's pick. The other one could pick randomly and if lucky (50%) they can still win no matter the other's pick which contradicts the supposition. So neither player can have a winning strategy.
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.
0:10 I bet there were people thinking of game theory.
“But it’s a theory, A GAME THEORY!”
Thank you so much for this great 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).
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
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.
10:51 Axiom of Choice! [meme with Dicaprio pointing at tv]
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?
“Most mathematicians still prefer to take the axiom of choice.” This is a very diplomatic way to not offend constructivists. Lmao
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.
“Alice and Bob color numbers forever and Alice wins iff she colors in the good numbers” is such a funny description
15:18 I like the eyebrows' movement on mention of Vsauce
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 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.
Very well explained ! 😀
Alice can always win the determinacy game where her set must have a diverging reciprocal sum.
Let's say alice goes first. Let's set a benchmark minimum sum that Alice gains each move must be: 1/2. This is easy enough for her first move, because 1's reciprocal is 1, so she just picks 1. Next, Bob can pick any number. It doesn't matter how big it is. For our sake we'll call it 100. Alice can then simply add together reciprocals of numbers greater than that until the reciprocal sum of the new numbers is greater than 1. I can guarantee that all numbers between 100 and 2*100 have a reciprocal greater than 1/200, so that means the sum must be 100*(1/200) or 1/2. Because she can always pick an infinite number of terms, she can simply choose the range between Bob's last choice and twice Bob's last choice, and be sure she has a reciprocal sum greater than 1/2, incrementing her total by over 1/2 over time. (Actually, in the limit, it's increasing by ln2 each time, but yeah). Adding a lower bound of 1/2 forever will diverge to infinity. ez
Random other thing, but if the question was reversed to where Alice had to have a finite reciprocal sum, Bob could always win. He can simply choose the next integer after Alice's choice, causing her leftover set to have a fastest possible growth of 2n. Since the reciprocal sum of any linear sequence is infinite, the limit is infinite and she loses
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.
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?
On any finite turn, either player can just be like "ok I'm ignoring all previous turns and pretending like this is the first turn", because the previous turns will amount to finite (trivial) differences in the set they're building and the real bulk of the game is the infinite turns following. If both players had the same win condition, this would allow them to steal each other's strategy at ANY point in the game just as effectively as if they had known to do that strategy from turn 1.
However, both players do not have the same win condition, which is where it falls apart. The game is determined. If Alice's win condition is having a good set, and a good set is a set that is "almost the same as the set of all primes"... all Bob has to do is make sure he takes an infinite amount of primes so that her set differs from the set of all primes by an infinite amount. If Alice tries to steal his strategy, and also takes an infinite amount of primes for herself, they will both end up with a set that is essentially different from the good sets. They can both have bad sets, in which case Bob wins.
Ok this was f-ing fascinating
Thanks for the video, bro!)
Well done, great video
yup, it's much stranger when the axiom of choice doesn't hold. one funny fact is that without choice, it's possible that a product of things greater than 1 can actually be 0. in fact, the axiom of choice is equivalent to every product of cardinals greater than 1 being nonzero.
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?
A brilliant video!
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.
I wonder if there are alternatives to the Axiom of Choice and the Axiom of Determinacy.
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
Love it!
Loved this video!
Doesn't Bob's set in the power-of-two example also include infinitely many powers of two?
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?
Can you do a video on ultra filters too please?
Same as the infinite powers of 2 - reciprocal will converge
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.
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.
How can the game ever be over? The game never ends.
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)
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.
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.