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

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.

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. 😛

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.

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.

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.

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.

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.

"We somehow get even stranger things if we don't..." And now you have your sequel video to do because I am definitely intrigued.

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".

Only God can judge Alice and Bob

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."

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.

Thank you SackVideo

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.

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 animations showing internal/external rotation force when using a barbell were the best I've ever seen in a fitness video.

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.

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)

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!

It's a miracle that a chanel that show math in its pure and fun way in such a great manner is free.

15:18 I like the eyebrows' movement on mention of Vsauce

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.

"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

That was amazing! Thanks. Now I have to watch it all over again a few more times.

Your videos are great, keep it up!

Thank you! Love and blessings.

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

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.

Very well explained ! 😀

Thanks for the video, bro!)

Well done, great video

That seems like circular logic. Alice is stealing Bob's strategy while Bob is stealing Alice's strategy. How can you draw a logical conclusion from that?

An amazing video!!! Hope that it wins 🙏🏻

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.

A brilliant video!

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".

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?

Great vid, I thought this was an nice and gentle introduction to AD.

An alternative indeterminate game: pick a function f from the set of infinite sequences of {0,1} into {0, 1} such that changing one of the bits always changes the result (aka "infinite XOR"). Players 0 and 1, in their turns, can write any non-empty finite sequence of bits (e.g. player 0 writes "010", player 1 writes "111", player 0 writes "00000", so on). The winner is f(infinite sequence obtained via concatenation) (e.g. f(01011100000....)) (Seems quite similar actually.)

since the sum of all reciprocals diverges, any tail of that sum diverges, so there exists a point in every tail such that the sum of terms before it are bigger than any desired M, so alice would only need in her nth turn to pick the integer in a way so that the freshly colored in red terms reciprocals sum to something at least as big as the next term of her decided diverging series, perhaps 1+1+1+...

For the opposite of the 1/x->inf game where a set is good only if it's sum converges, Player 2 has a winning strategy. P1's best move is to always choose only the first element after P2's, so P2 can force P1 into taking, at most, the series 1+1/3+1/5+1/7+1/9+...

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).

Ok this was f-ing fascinating

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

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

Love it!

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 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 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.

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

“Alice and Bob color numbers forever and Alice wins iff she colors in the good numbers” is such a funny description

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.

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?

I wonder if there are alternatives to the Axiom of Choice and the Axiom of Determinacy.

The different axioms make me think of some made up DnD mathematician subclasses for some reason.

This game seems to have strong ties with Turing machines and the halting problem.

Great video I absolutely adore combinatorial game theory! Just one question (maybe I missed it in the video): Why can we apply the Zermelo Theorem if the theorem is only applicable for finite games? Games that do not end in a draw but take infinite steps are not finite or are they?

Nice video

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.

Can you do a video on ultra filters too please?

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 😁

Might the axium of choice vs the axium of determinacy have any implications for the real world, the universe, snd free will or not.

Sounds like the halting problem, revisited. Which is, of course, also the Goedel incompleteness theorem all over again.

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

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

“Most mathematicians still prefer to take the axiom of choice.” This is a very diplomatic way to not offend constructivists. Lmao

super cool

how come a set with infinte member and not a single one of them is same, yet every member of them is only different by a finite amount ?

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.

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.

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.

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 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

To win Chomp the first player must always force the remaining block to have an even number of required moves.

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).

I’m glad this was recommended to me! How did you achieve such clear speech in the video? Do you prepare a script, or understand it deeply?

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.

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.

man, "being fun" really is optional for a game in math world

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.

Has it been proven whether both the axiom of choice and the axiom of determination being false leads to a contradiction?

That was an automatic subscribe.

I think this becomes solveable if we assume that there is a final turn and we can determine who gets it. In that case, whoever gets the final turn loses, and the game plays out recursively. If we don't assume the game has a final turn then maybe we don't have to assume the game has a starting turn either? What would the ramifications of that be? Is that a silly thought?

Winning strategy for chomp: Start by eating the whole chocolate bar, and spit out the poisoned square.

I may have missed something but what is both the red and blue are "good" then Alice is garunteed a win, right?

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 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.

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.

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.

15:40 It's somehow stranger if we don't take the axiom of choice? Please make a video explaining this.

Same as the infinite powers of 2 - reciprocal will converge

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.

"almost the same" could be replaced with "similar"

Another paradox that may be right up your alley is "Skolem's Paradox". I wasn't able to fully wrap my head around it but it basically states that there may only exist countably many real numbers. (In the sense that it would be consistent. The bijection that would help us count them may not exist inside the model, so we couldn't catch it with Cantor's diagonalization.)

2:26 I have a counter example to the first player could have always made a move to make the same game state as after the second player's first move. If instead of the top right I go one to the left of the top right and then the second player plays one below the top right, the resulting game shape is an inverted L removed from the top right. There is no way to make an inverted L shape with one move...?

So for the infinite primes game, if Alice chooses all squares up to the next prime, then Bob chooses all squares up to the next prime, then both of them would have a Good set, and so the complement of a good set is not necessary bad. Am I missing something here?

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").

8:53 I'm confused about condition #1. Let's say that good=only odd numbers, and your set is all odd numbers. Then I can add a random even number and make the set bad.