What helped me start to understand the basics of Model Theory was reading about it in the book by John Newsome Crossley titled "What is Mathematical Logic?". When he showed that there exists many nonisomorphic models(structures satisfying the same axioms) of the natural numbers with the strictly less than relation, it blew my mind. It finally made sense why we needed to define a concept called a model of a theory. Axioms are not enough to pin down every mathematical structure! It is possible for a human to have a model in their mind while an alien has another nonisomorphic model in their mind which satisfies the same axioms. Information about the number of/properties of unintended models can bring great insight into problems in different fields. Check out the work done by Ehud Hrushovski, Boris Zilber, Anand Pillay and Saharon Shelah(to mention a few).
This is what I love about #SOME; learning about some area of math that I didn't know existed before and getting to hear about it from a creator I also didn't know. Thanks for that and thanks for your very explanation. I agree with you that w+*w (pretend those are the small gamma) is pretty darn cool.
Great exposition! I have seen the EF game before in the context of graph theory, but I didn't really get how direct the translation was from a formula to a strategy until just now!
It's worse than just "some bijections are available to the metatheory that aren't available to our countable model of ZFC" -- different models of ZFC can have distinct notions of what omega is! (I mention this briefly in my Permutation Models video at 18:50)
Very cool topic and video. I had never heard of linear orderings before, but when you presented them I could easily understand them and they made sense -- and I realized I had played around with them (well, mostly just the Rationals using things like the Stern-Brocot tree) quite a bit previously, without knowing what they were called. That ability to present an abstract concept in an intuitive way is IMHO one of the best things about Math Exposition, so thank you very much for making this video! Great job!
i have not seen any logic class, just a bit about discrete maths but your explanation of a bit of model theory aswell the way to see it and play it is incredible!
I really enjoyed this one! I think it was presented super well. My only comment was going to be that it took me a while to peice together the "purpose" of the EF Game (which could of course just be a me problem), but then when you got to 17:35 it finally clicked. Great work!
Thank you for explaining the ∀ and ∃ symbols and then using them for the rest of the video and even reading off the axioms while circling the element/symbol you are currently talking about. A lot of videos have been glossing over what symbols mean. One thing you didn’t mention though, or I didn’t notice, is what are R and Q are at 16:33? I happen to know R is the set of all real numbers and just found out what Q is, but it would be nice if it was noted on the slide. I like your visualization representing numbers as dots. It’s very simple but gets the point across well. Thanks for a good video on a field I know little about.
This is amazing, my personal favourite of SoMe2! Thanks for this great introduction to model theory 🙂 For others, I was struggling to find constructive reasons for linear orders until I found out that all these orders are countable. You can implement different comparators in a programming language over the integers. The last three orders in the video can be constructed as such: w+w^*: 1 < 3 < 5 < 7 < ... ... < 6 < 4 < 2 w: 1 < 2 < 3 < ... w+ζ: 1 < 4 < 7 < 10 < ... ... < 8 < 5 < 2 < 3 < 6 < 9 < 12 < ... However, if you want to distinguish two comparisons *without* looking at the the number, at the structure of the element, only by comparison, you cannot do this for the last two sequences using FOL which is equivalent to not being able to guaranteedly beat the Ehrenfeucht-Fraïssé in finite time. However, even after one input of the duplicator the spoiler will be able to prove in a bounded number of turns that the sequences are not the same 🤯 Kind of makes you wonder if there is a fixed point version of FOL? What logic can prove this? Any pointers would be appreciated. I am continuing your video tour in the description! Thanks 🙏
I'm currently not aware of a fixed point version of FOL, but I wouldn't be surprised if there was one. I'd suggest asking on the math stackexchange. Note that not all linear orderings are countable (the real numbers, or large ordinals, for example), but since every linear ordering is FOL-indistinguishable from a countable one, this isn't a big deal.
Great video. I'm not sure I get the point around 19:19 in. "Any two sufficiently large linear orderings look the same up to n-variables." What is meant by "sufficiently large" here? Unless I'm wrong, every linear ordering should be indistinguishable from a countable linear ordering. And with countable linear orderings, we can distinguish some of them in 3 - 4 variables. Say take omega and omega^* and look for a least element or maximum element.
Try playing the EF game between a 3 point linear ordering and any infinite linear ordering. In 3 turns you'll run out of points, so there's a 4-variable formula distinguishing the 3 point linear ordering from any infinite linear ordering. This formula is "There exists x, y, z which are all unequal and any w is one of x, y, or z", and in fact it is only true of 3 point linear orderings, distinguishing them from any other linear orderings, finite or infinite. This generalizes to any n point linear ordering, but one can actually do much better with more complicated formulas: there's a roughly log_2(n)-variable formula which is only true of the n point linear ordering.
Nice video. I've seen these games mentioned on Wikipedia articles but never looked into what they are. Also, this gives a name for me to reference for that thing in computer science where "PSPACE = quantified Boolean formulas = finite games." Btw, you might want to see if you can set up a software noise filter. There was a lot of noise on your audio here.
Not the flashiest SoME submission (flashy = animation), but very interesting! Well done! EDIT: So I guess one consequence of that conclusion is that there's no way to express "There is/isn't an infinite descending sequence" in this language. EDIT2: I wonder if there's some sort of "topological first-order language" - then we can ask whether the sphere and the torus are logically indistinguishable. One thing I know is, the proposition "For any two disjoint closed sets, if the complement of each one individually is connected then the complement of their union is connected" is true of the sphere but not of the torus... I wonder what sort of language we could set up to allow that? (Things like "The space is simply connected (meaning every image of a loop is the boundary of the image of a disk)" strike me as 'higher-order', somehow.)
There is an approach to topology called "pointless topology" in which the elements of the structures being considered are open sets within a topological space, and points are completely ignored. Perhaps this, or some similar type of structure in which sets of points are treated as first-order objects would work.
@@trkern Oh - this is purely the language of posets, isn't it! In the corresponding Ehrenfeucht-Fraïssé game, we take turns choosing open subsets of either the sphere or the torus - you spoiling and me duplicating - such that I must match all inclusion relations. You then have a winning strategy (which is fun to puzzle through!).
Great video! I love it when two systems which initially look entirely unrelated turn out to just be two ways of expressing the same idea. I have a question: since you can show that certain infinite orderings are logically indistinguishable from one another, are there a finite number of 'classes' of indistinguishability or can you always construct a new ordering which behaves differently from all the others?
All finite linear orderings are distinguishable with large enough formulas. However, for fixed number of turns/quantifier depth, there are only finitely many distinguishability classes since one can capture all information about the game in a giant but bounded-size game tree data structure describing what moves are available as responses to what. Trevor Green's "Properties of Chain Products and Ehrenfeucht-Fraisse Games on Chains" (2002) counts the exact number of equivalence classes for depth 2 (there are 7) and equivalence classes for depth 3 (there are 281). Since every infinite linear ordering is logically indistinguishable from a countable linear ordering (Lowenheim-Skolem) there are continuum many equivalence classes modulo full indistinguishability.
For every natural number x, we can construct a predicate "has a sequence of exactly x points in a row with nothing in between them (that can't be extended to a sequence of x+1 points in a row with nothing in between them)". Given a subset N of the natural numbers larger than 2, we can construct a linear ordering that satisfies exactly that subset of these predicates by inserting the appropriate finite linear orderings within a larger dense linear ordering, call it L(N). Then for every pair N, M of distinct subsets of the naturals larger than 2, L(N) will be logically distinguishable from L(M), because they disagree on the predicate for x in the symmetric difference of N and M. (This is Theorem 6.15 in Rosenstein)
If you allow countably infinitely many turns, spoiler can fully exhaust a subset of Q while continuing to pick points that would have to fall within the range of that subset, thus distinguishing Q from R. But "countably infinitely many turns" is a problem in itself there.
EF-games with infinitely many turns are studied and correspond to logics with infinitely many quantifiers. In other words, Q and R are distinguishable in these logics. I'm not sure of the exact details myself, though.
Not that I'm aware of, they're just drawings of linear orderings. Of note is that any countable linear ordering can be represented by a subset of [0,1].
@@trkern further if it's (countably) nonfinite, its subspace topology from R is totally disconnected but nondiscrete. (just learning topology so no idea what the implications of this are yet!)
Here I'm using the term "bounded" to mean not growing or changing. For instance, for a particular version of a programming language you can present a complete description of the language and it won't change over time. This is to contrast with, for example, the English language, where new words and meanings are being added all the time, making it impossible to reason mathematically about what you can and cannot say.
Good question! I'm not sure: I remember feeling like descriptive set theory was more expressive than model theory when I took it, but that was long ago. Does anyone else know?
Yes, but there's a subtlety here. If we're interested in first order logical (in)distinguishability, spoiler not only has to be able to win, but to win in a called-in-advance number of turns. Actually allowing infinitely many turns I believe corresponds to infinite quantifier logics, but I'm not sure of the exact details.
What helped me start to understand the basics of Model Theory was reading about it in the book by John Newsome Crossley titled "What is Mathematical Logic?". When he showed that there exists many nonisomorphic models(structures satisfying the same axioms) of the natural numbers with the strictly less than relation, it blew my mind. It finally made sense why we needed to define a concept called a model of a theory. Axioms are not enough to pin down every mathematical structure! It is possible for a human to have a model in their mind while an alien has another nonisomorphic model in their mind which satisfies the same axioms. Information about the number of/properties of unintended models can bring great insight into problems in different fields. Check out the work done by Ehud Hrushovski, Boris Zilber, Anand Pillay and Saharon Shelah(to mention a few).
This is what I love about #SOME; learning about some area of math that I didn't know existed before and getting to hear about it from a creator I also didn't know.
Thanks for that and thanks for your very explanation. I agree with you that w+*w (pretend those are the small gamma) is pretty darn cool.
You got a like from me the moment (12:40) you read off the strategy from the formula directly - that was wild
Great exposition! I have seen the EF game before in the context of graph theory, but I didn't really get how direct the translation was from a formula to a strategy until just now!
Really wonderful introduction! But by far the best moment was 21:30 "the argument works for any value of a hundred" ;)
Thanks, beautiful!
The thing that gets me about model theory is Skolem's paradox.
It's worse than just "some bijections are available to the metatheory that aren't available to our countable model of ZFC" -- different models of ZFC can have distinct notions of what omega is! (I mention this briefly in my Permutation Models video at 18:50)
This such a beautiful piece, I hope you do a great job please never stop with these videos.
this was one of my fav internet math journeys. very well explained!
TH-cam algorithm on spot
Fantastic video!
Very cool topic and video. I had never heard of linear orderings before, but when you presented them I could easily understand them and they made sense -- and I realized I had played around with them (well, mostly just the Rationals using things like the Stern-Brocot tree) quite a bit previously, without knowing what they were called. That ability to present an abstract concept in an intuitive way is IMHO one of the best things about Math Exposition, so thank you very much for making this video! Great job!
Thank you, you're a blessing on Earth 🙏🙏
i have not seen any logic class, just a bit about discrete maths but your explanation of a bit of model theory aswell the way to see it and play it is incredible!
I really enjoyed this one! I think it was presented super well. My only comment was going to be that it took me a while to peice together the "purpose" of the EF Game (which could of course just be a me problem), but then when you got to 17:35 it finally clicked. Great work!
Excellent talk! Easy to understand from an undergrad level, a welcome addition to SoME2.
Absolutely phenomenal
Thank you for explaining the ∀ and ∃ symbols and then using them for the rest of the video and even reading off the axioms while circling the element/symbol you are currently talking about. A lot of videos have been glossing over what symbols mean. One thing you didn’t mention though, or I didn’t notice, is what are R and Q are at 16:33? I happen to know R is the set of all real numbers and just found out what Q is, but it would be nice if it was noted on the slide.
I like your visualization representing numbers as dots. It’s very simple but gets the point across well.
Thanks for a good video on a field I know little about.
This is amazing, my personal favourite of SoMe2! Thanks for this great introduction to model theory 🙂
For others, I was struggling to find constructive reasons for linear orders until I found out that all these orders are countable. You can implement different comparators in a programming language over the integers. The last three orders in the video can be constructed as such:
w+w^*: 1 < 3 < 5 < 7 < ... ... < 6 < 4 < 2
w: 1 < 2 < 3 < ...
w+ζ: 1 < 4 < 7 < 10 < ... ... < 8 < 5 < 2 < 3 < 6 < 9 < 12 < ...
However, if you want to distinguish two comparisons *without* looking at the the number, at the structure of the element, only by comparison, you cannot do this for the last two sequences using FOL which is equivalent to not being able to guaranteedly beat the Ehrenfeucht-Fraïssé in finite time. However, even after one input of the duplicator the spoiler will be able to prove in a bounded number of turns that the sequences are not the same 🤯
Kind of makes you wonder if there is a fixed point version of FOL? What logic can prove this? Any pointers would be appreciated.
I am continuing your video tour in the description! Thanks 🙏
I'm currently not aware of a fixed point version of FOL, but I wouldn't be surprised if there was one. I'd suggest asking on the math stackexchange. Note that not all linear orderings are countable (the real numbers, or large ordinals, for example), but since every linear ordering is FOL-indistinguishable from a countable one, this isn't a big deal.
this is a great video, the connection between orders and games is very cool
Super interesting. Thanks for sharing!
excellent explanation .. thanks a lot ..
That's cool!!!
Great video. I'm not sure I get the point around 19:19 in. "Any two sufficiently large linear orderings look the same up to n-variables." What is meant by "sufficiently large" here? Unless I'm wrong, every linear ordering should be indistinguishable from a countable linear ordering. And with countable linear orderings, we can distinguish some of them in 3 - 4 variables. Say take omega and omega^* and look for a least element or maximum element.
Try playing the EF game between a 3 point linear ordering and any infinite linear ordering. In 3 turns you'll run out of points, so there's a 4-variable formula distinguishing the 3 point linear ordering from any infinite linear ordering. This formula is "There exists x, y, z which are all unequal and any w is one of x, y, or z", and in fact it is only true of 3 point linear orderings, distinguishing them from any other linear orderings, finite or infinite. This generalizes to any n point linear ordering, but one can actually do much better with more complicated formulas: there's a roughly log_2(n)-variable formula which is only true of the n point linear ordering.
Nice video. I've seen these games mentioned on Wikipedia articles but never looked into what they are. Also, this gives a name for me to reference for that thing in computer science where "PSPACE = quantified Boolean formulas = finite games."
Btw, you might want to see if you can set up a software noise filter. There was a lot of noise on your audio here.
Thanks! I noticed the noise, but couldn't figure out a way to get rid of it. Any suggestions for good software noise filters?
loved the video you should make more videos on model theory.
Not the flashiest SoME submission (flashy = animation), but very interesting! Well done!
EDIT: So I guess one consequence of that conclusion is that there's no way to express "There is/isn't an infinite descending sequence" in this language.
EDIT2: I wonder if there's some sort of "topological first-order language" - then we can ask whether the sphere and the torus are logically indistinguishable. One thing I know is, the proposition "For any two disjoint closed sets, if the complement of each one individually is connected then the complement of their union is connected" is true of the sphere but not of the torus... I wonder what sort of language we could set up to allow that? (Things like "The space is simply connected (meaning every image of a loop is the boundary of the image of a disk)" strike me as 'higher-order', somehow.)
There is an approach to topology called "pointless topology" in which the elements of the structures being considered are open sets within a topological space, and points are completely ignored. Perhaps this, or some similar type of structure in which sets of points are treated as first-order objects would work.
@@trkern Oh - this is purely the language of posets, isn't it!
In the corresponding Ehrenfeucht-Fraïssé game, we take turns choosing open subsets of either the sphere or the torus - you spoiling and me duplicating - such that I must match all inclusion relations. You then have a winning strategy (which is fun to puzzle through!).
Good video you win thumbs up 👍
I truly believed I could come up with a formula to distinguish an ordering with a dense limit point from a finite ordering, but I ran out of literals.
Great video! I love it when two systems which initially look entirely unrelated turn out to just be two ways of expressing the same idea.
I have a question: since you can show that certain infinite orderings are logically indistinguishable from one another, are there a finite number of 'classes' of indistinguishability or can you always construct a new ordering which behaves differently from all the others?
All finite linear orderings are distinguishable with large enough formulas.
However, for fixed number of turns/quantifier depth, there are only finitely many distinguishability classes since one can capture all information about the game in a giant but bounded-size game tree data structure describing what moves are available as responses to what.
Trevor Green's "Properties of Chain Products and Ehrenfeucht-Fraisse Games on Chains" (2002) counts the exact number of equivalence classes for depth 2 (there are 7) and equivalence classes for depth 3 (there are 281).
Since every infinite linear ordering is logically indistinguishable from a countable linear ordering (Lowenheim-Skolem) there are continuum many equivalence classes modulo full indistinguishability.
@@trkern I see why there are at most a continuous of classes but not why those are more than countably many
For every natural number x, we can construct a predicate "has a sequence of exactly x points in a row with nothing in between them (that can't be extended to a sequence of x+1 points in a row with nothing in between them)". Given a subset N of the natural numbers larger than 2, we can construct a linear ordering that satisfies exactly that subset of these predicates by inserting the appropriate finite linear orderings within a larger dense linear ordering, call it L(N). Then for every pair N, M of distinct subsets of the naturals larger than 2, L(N) will be logically distinguishable from L(M), because they disagree on the predicate for x in the symmetric difference of N and M. (This is Theorem 6.15 in Rosenstein)
If you allow countably infinitely many turns, spoiler can fully exhaust a subset of Q while continuing to pick points that would have to fall within the range of that subset, thus distinguishing Q from R. But "countably infinitely many turns" is a problem in itself there.
EF-games with infinitely many turns are studied and correspond to logics with infinitely many quantifiers. In other words, Q and R are distinguishable in these logics. I'm not sure of the exact details myself, though.
do the diagrams shown at 5:40 have a special name? fun to extend to 2D
Not that I'm aware of, they're just drawings of linear orderings. Of note is that any countable linear ordering can be represented by a subset of [0,1].
@@trkern further if it's (countably) nonfinite, its subspace topology from R is totally disconnected but nondiscrete. (just learning topology so no idea what the implications of this are yet!)
thank u helped me a lot
What's a "bounded language"? Didn't find any good material explaining this term. The wiki page is too vague.
Here I'm using the term "bounded" to mean not growing or changing. For instance, for a particular version of a programming language you can present a complete description of the language and it won't change over time. This is to contrast with, for example, the English language, where new words and meanings are being added all the time, making it impossible to reason mathematically about what you can and cannot say.
@@trkern I get it now. Thanks!
Is this related to descriptive set theory?
Good question! I'm not sure: I remember feeling like descriptive set theory was more expressive than model theory when I took it, but that was long ago. Does anyone else know?
So if the two orderings are identical, does that mean the game goes on infinitely, and the duplicator "wins"?
Yes, but there's a subtlety here. If we're interested in first order logical (in)distinguishability, spoiler not only has to be able to win, but to win in a called-in-advance number of turns. Actually allowing infinitely many turns I believe corresponds to infinite quantifier logics, but I'm not sure of the exact details.
liner ordering to sets are like an interfaces for objects in programmig
Hi there, is there a way I can contact you personally (for example, a DM on Twitter or an email address)? Great job.