The issue with recursive definitions is they create a vicious circle. To get around this, you need to specify a base case, and constructively build out your definition from there.
...no. Frequently, recursive definitions don’t require a base case—you can find a (or the) object that makes the definition work, usually via a fixed point theorem.
In the Sierpinski case, we want to find a fixed point of the function that takes a subset of the triangle and maps it to the union of the 3 shrinked versions positioned in the appropriate way. We don’t want the empty set, nor the thing we’d get if we iterated a single point—we want the largest fixed point. First, note that the iteration function is monotonic under the subset relation. Next, we can apply the Knaster-Tarski fixed point theorem to prove that for some ordinal w, the wth iteration of the triangle is the greatest fixed point (where a limit ordinal means we take the infimum of all previous). Now in this case, if w is the integers, we see that the intersection of all the finite iterates in fact a fixed point. Thus we get Sierpinksi’s triangle.
In fact, we can instead just take three points A,B,C that are corners of a triangle and use the dilations d_A, d_B, d_C where e.g. d_A moves a point p halfway towards A. If we require the input to be a nonempty compact (aka closed bounded) set, and use the Hausdorff metric’s limits for iteration, we will get the Sierpinski triangle. That is, each individual dilation is a contraction map, and the iteration that unions each dilation (as a function from subsets to subsets) is easily shown to be a contraction map—and since the Huasdorff metric is complete on compact sets, the contraction mapping theorem gives us a unique fixed set that we can get via taking the limit of iteration.
All we need to do is find the group, the “base case” of reality, our elementary particles represent
The group isn’t the base case, it’s the iteration.
I was wondering why we go from the group of symmetries to the universal cover. I don’t think the story about loops you gave is why, unless there’s an equivalent way to make that interpretation cash out physically. The explanation I am finding (though there’s others for other more general cases that involve math I don’t know at all like group cohomology): What we really want is projective representations (just because we are doing quantum physics, and the wavefunction is only defined up to a scalar factor). Now, it turns out you can lift these. It looks like you need to pass to the lie algebra representations, then you can deprojectivize by choosing traceless representatives. Then you can lift to the lie group, except now it’s the universal cover. So you get determinant one reps. You can do the converse too. In nice cases you have that all reps of the universal cover are det one so you don’t have to worry about that; otherwise you need to look only at irreps.
I don’t see why rational alpha is needed to have a finite number of rules for a cellular automata. After all, who said your rules perform one of the group representation operations! Just take, like, any quantum gate on qubits. Also, like, who said the states are wavefunctions in 1D? I should be able to build a quantum turing machine operating on a linear tape of hydrogen atom states (or more realistically spin states) to give me a perfectly cromulent cellular automaton whose rules aren’t a representation of the poincare group, let alone the 1D one.
My perspective is that logical truth is the ability to write a proof, and since humans (or computers) can only do finite computations, the proof must be finite. Now, we can smuggle in infinities with—proofs. A short example: for any , we can find an such that, for any
and the proof of this “for any … for any” is finite:
This is why I initially said you had to define a base case, and build out the Serpinski triangle as a limit of this base case. I think we have almost the same thing in mind in your second construction: take three points as the corners of a triangle, iteratively refine the set with dilations, and use an—proof to show this converges to a fixed set of points.
However, you are right that we don’t actually need the base case! I don’t know enough about how the Knaster-Tarski fixed point theorem is defined or proven. It can probably be written constructively, but I’m not sure. An easier construction for me is to define iterate and then apply a fixed point combinator. So, we have a finite program defining
iterate(S) = S + three smaller copies
and then we define the Serpinski triangle as
Y(iterate)
No need for an initial set of points to feed into this object, unless there are properties we care about like the boundary being a triangle. I think you also have to be careful to make sure this actually converges, but I’m sure that can be worked out.
As for the rest of your comment, note that this post was written in around a day, after I figured out Wigner’s classification by thinking really hard (I only learned it was called Wigner’s classification during the writeup). Looking back on it, there are things that are not quite right, and things that could be explained better. I am writing an updated version that’s more careful with how things are being defined, where things come from, and what actually follows from what, but this has been in the works for many months and I’ve just never really gotten around to finishing it.
The idea behind the universal cover is that, if you had a loop of simplices and hopped around it in a circle, when you get back to where you started you should have the same “value”. The representations tell you how this value changes as you hop around (translate/rotate). If you can continuously deform every loop into a point, or a point into any loop, then any representation will satisfy this “same value” property. So you lift to a universal cover and then ask for the representations.
This isn’t quite right. Why stop at 1D loops, not go further in the Postnikov tower? What actually are these simplices and their boundaries? Also, what actually are rotations? Why not just redefine them as a bigger, lifted group that looks like SO(3, 1) when projected down?
As for rational , yes the idea was that the representations were the rules. This was over a year ago, and I’m also a little confused why I said that. My best guess is I thought the problem assumed the cellular automaton implemented the same rule for every group of three qubits, so something with superposition and Schroedinger’s equation (like here) somehow implies we can break the combined wavefunction of all the qubits into a bunch of 1D waves. But I’m not entirely sure what my train of thought was, and there was probably a mistake.
The idea behind the universal cover is that, if you had a loop of simplices and hopped around it in a circle, when you get back to where you started you should have the same “value”. The representations tell you how this value changes as you hop around (translate/rotate). If you can continuously deform every loop into a point, or a point into any loop, then any representation will satisfy this “same value” property. So you lift to a universal cover and then ask for the representations.
This can’t be why it shows up. Let’s take the group action of the circle on R^2 that just rotates. The circle is not simply connected, yet when I go in a loop my representation will continuously go back to where I started, as must be the case simply because I have a loop and a continuous group action.
In general, lie group representations should always lift to the universal cover I think; the whole point here is I think that there’s a correspondence the other way, and that’s only there because we’re looking at a projective representation.
Lastly I think using the Y combinator is probably a bad idea, because you could get fixed points that don’t correspond to a set in whatever your interpretation of lambda functions as sets is. And also, how are you interpreting, exactly??
I believe I needed the axiom of choice for Knaster-Tarski and possibly somewhere in the contraction mapping theorem, but not sure.
You kind of just have to assume that the interpreter works, and your computer wasn’t hit by a cosmic ray that flipped a random bit invalidating your proof. You can try some sort of probabilistic thing, but with what interpreter do you define your probabilities? There is no probabilistic Loeb’s theorem. Once you take the leap of faith though, you can build your interpreter by assuming you have some number of bits and NAND gates, and asking what circuits you can make. Then you can write finite programs that prove things about the relationships between different strings of bits. There are many similar kinds of interpreters (e.g. rather than NAND gates, a human chooses a set of ‘logical operators’, writes them down on paper, and runs the program through with their brain).
Yes, the correspondence is the other way. See the paragraph after the one you quoted. I think my earlier self was wrong, though there is the possibility I just cannot reconstruct their thought process.
I don’t understand why you are talking about interpreters. Do you agree that the Y combinator, when applied to a lambda function, might not be a lambda function corresponding to a number? Or, say, a lambda function that encodes the set in question? I still don’t see how you are encoding the set in question—are you literally manipulating first order logic strings encoded as numbers? If so, then once again you might get a fixed point that corresponds to no number—and even if you get a number, the encoded string might not correspond to a set.
To clarify 2 (though I think we don’t disagree here) - the reason you stop at the universal cover is simply because that’s where you get a bijection.
I thought you were asking about interpreters: “And also, how are you interpreting, exactly??” I guess not. So, I think there’s some confusion about the Y combinator here. Consider the factorial function:
iter(n) = n * iter(n-1) if n > 0 else 1
factorial = Y(iter)
You might encode n as a Church numeral. In this particular case, factorial(n) can also be beta-reduced to a Church numeral. Note though, that factorial itself is not a Church numeral. Now, consider the Serpinski triangle
iter(S) = S + (1 + w + w^2)(S/3) ; S + three dilated copies
serpinski = Y(iter)
You have some notion of how sets S should be encoded, and you are worried that serpinski(S) may not beta-reduce to fit that notion. Perhaps then you’ve got the wrong notion of sets, and should expand it to include objects like serpinski(S). But perhaps that leads to nasty problems like Russell’s paradox. I’m not sure, but I suspect you won’t run into this problem.
“To clarify 2 (though I think we don’t disagree here) - the reason you stop at the universal cover is simply because that’s where you get a bijection.”
Sorry, what bijection? Between the lifted rotations and… what?
Well, you really have F = lambda f,n: n * f(n-1) if n > 0 else 1, and then (YF)(n) beta-reduces to a church numeral. Our fixed point is the factorial function.
Trying to duplicate this with the sets in question: how should sets be encoded? I suspect that for any reasonable notion, you will have a problem where the fixed point might be some terrible thing.
As an example, suppose you try the most obvious way: a set is represented by a function that returns true for all elements in the set, and false otherwise. But how are we to plug in real numbers? Well, we could take computable approximations to the reals… but then we can’t even define the set {0} as a computable function! Even if we don’t allow something as pathological as the reals, decidable sets are much lesser than all the sets.
Any other way would, I think, have to basically be manipulating formal logic strings represented via e.g. a godel numbering and church numerals. Then, one defines the iteration as a function that takes in a string defining a set in first order logic, then outputs a first order logic string defining of the next iteration. But then, there’s no guarantee that the fixed point is a number, let alone a number corresponding to a logical formula that defines a set.
About the representations: in the finite dimensional case, there is a bijection between projective irreps of G and determinant 1 ordinary irreps of the universal cover of G. Apparently in the infinite dimensional case, you can only lift projective irreps to ordinary irreps in certain cases which include the Poincare group. I can’t tell if you would get a bijection in those cases.
I would be surprised if the motivation for projective irreps does not also motivate extending higher up the Postnikov tower; you don’t just stop at the universal cover.
As for sets, suppose you went with the definition: any function that takes in a rational number and spits out a boolean. So the Dedekind cut for could be expressed as
sqrt2 = lambda x. (x * x < 2)
I expect that
((serpinski sqrt2) 3/4)
could indeed be -reduced to a boolean, if you choose the right path. So basically, (serpinski S) is also a set if S is a set.
...no. Frequently, recursive definitions don’t require a base case—you can find a (or the) object that makes the definition work, usually via a fixed point theorem.
In the Sierpinski case, we want to find a fixed point of the function that takes a subset of the triangle and maps it to the union of the 3 shrinked versions positioned in the appropriate way. We don’t want the empty set, nor the thing we’d get if we iterated a single point—we want the largest fixed point. First, note that the iteration function is monotonic under the subset relation. Next, we can apply the Knaster-Tarski fixed point theorem to prove that for some ordinal w, the wth iteration of the triangle is the greatest fixed point (where a limit ordinal means we take the infimum of all previous). Now in this case, if w is the integers, we see that the intersection of all the finite iterates in fact a fixed point. Thus we get Sierpinksi’s triangle.
In fact, we can instead just take three points A,B,C that are corners of a triangle and use the dilations d_A, d_B, d_C where e.g. d_A moves a point p halfway towards A. If we require the input to be a nonempty compact (aka closed bounded) set, and use the Hausdorff metric’s limits for iteration, we will get the Sierpinski triangle. That is, each individual dilation is a contraction map, and the iteration that unions each dilation (as a function from subsets to subsets) is easily shown to be a contraction map—and since the Huasdorff metric is complete on compact sets, the contraction mapping theorem gives us a unique fixed set that we can get via taking the limit of iteration.
The group isn’t the base case, it’s the iteration.
I was wondering why we go from the group of symmetries to the universal cover. I don’t think the story about loops you gave is why, unless there’s an equivalent way to make that interpretation cash out physically. The explanation I am finding (though there’s others for other more general cases that involve math I don’t know at all like group cohomology): What we really want is projective representations (just because we are doing quantum physics, and the wavefunction is only defined up to a scalar factor). Now, it turns out you can lift these. It looks like you need to pass to the lie algebra representations, then you can deprojectivize by choosing traceless representatives. Then you can lift to the lie group, except now it’s the universal cover. So you get determinant one reps. You can do the converse too. In nice cases you have that all reps of the universal cover are det one so you don’t have to worry about that; otherwise you need to look only at irreps.
I don’t see why rational alpha is needed to have a finite number of rules for a cellular automata. After all, who said your rules perform one of the group representation operations! Just take, like, any quantum gate on qubits. Also, like, who said the states are wavefunctions in 1D? I should be able to build a quantum turing machine operating on a linear tape of hydrogen atom states (or more realistically spin states) to give me a perfectly cromulent cellular automaton whose rules aren’t a representation of the poincare group, let alone the 1D one.
My perspective is that logical truth is the ability to write a proof, and since humans (or computers) can only do finite computations, the proof must be finite. Now, we can smuggle in infinities with—
and the proof of this “for any … for any” is finite:
This is why I initially said you had to define a base case, and build out the Serpinski triangle as a limit of this base case. I think we have almost the same thing in mind in your second construction: take three points as the corners of a triangle, iteratively refine the set with dilations, and use an—
However, you are right that we don’t actually need the base case! I don’t know enough about how the Knaster-Tarski fixed point theorem is defined or proven. It can probably be written constructively, but I’m not sure. An easier construction for me is to define
iterateand then apply a fixed point combinator. So, we have a finite program definingiterate(S) = S + three smaller copiesand then we define the Serpinski triangle as
Y(iterate)No need for an initial set of points to feed into this object, unless there are properties we care about like the boundary being a triangle. I think you also have to be careful to make sure this actually converges, but I’m sure that can be worked out.
As for the rest of your comment, note that this post was written in around a day, after I figured out Wigner’s classification by thinking really hard (I only learned it was called Wigner’s classification during the writeup). Looking back on it, there are things that are not quite right, and things that could be explained better. I am writing an updated version that’s more careful with how things are being defined, where things come from, and what actually follows from what, but this has been in the works for many months and I’ve just never really gotten around to finishing it.
The idea behind the universal cover is that, if you had a loop of simplices and hopped around it in a circle, when you get back to where you started you should have the same “value”. The representations tell you how this value changes as you hop around (translate/rotate). If you can continuously deform every loop into a point, or a point into any loop, then any representation will satisfy this “same value” property. So you lift to a universal cover and then ask for the representations.
This isn’t quite right. Why stop at 1D loops, not go further in the Postnikov tower? What actually are these simplices and their boundaries? Also, what actually are rotations? Why not just redefine them as a bigger, lifted group that looks like SO(3, 1) when projected down?
As for rational
This can’t be why it shows up. Let’s take the group action of the circle on R^2 that just rotates. The circle is not simply connected, yet when I go in a loop my representation will continuously go back to where I started, as must be the case simply because I have a loop and a continuous group action.
In general, lie group representations should always lift to the universal cover I think; the whole point here is I think that there’s a correspondence the other way, and that’s only there because we’re looking at a projective representation.
Lastly I think using the Y combinator is probably a bad idea, because you could get fixed points that don’t correspond to a set in whatever your interpretation of lambda functions as sets is. And also, how are you interpreting, exactly??
I believe I needed the axiom of choice for Knaster-Tarski and possibly somewhere in the contraction mapping theorem, but not sure.
You kind of just have to assume that the interpreter works, and your computer wasn’t hit by a cosmic ray that flipped a random bit invalidating your proof. You can try some sort of probabilistic thing, but with what interpreter do you define your probabilities? There is no probabilistic Loeb’s theorem. Once you take the leap of faith though, you can build your interpreter by assuming you have some number of bits and NAND gates, and asking what circuits you can make. Then you can write finite programs that prove things about the relationships between different strings of bits. There are many similar kinds of interpreters (e.g. rather than NAND gates, a human chooses a set of ‘logical operators’, writes them down on paper, and runs the program through with their brain).
Yes, the correspondence is the other way. See the paragraph after the one you quoted. I think my earlier self was wrong, though there is the possibility I just cannot reconstruct their thought process.
I don’t understand why you are talking about interpreters. Do you agree that the Y combinator, when applied to a lambda function, might not be a lambda function corresponding to a number? Or, say, a lambda function that encodes the set in question? I still don’t see how you are encoding the set in question—are you literally manipulating first order logic strings encoded as numbers? If so, then once again you might get a fixed point that corresponds to no number—and even if you get a number, the encoded string might not correspond to a set.
To clarify 2 (though I think we don’t disagree here) - the reason you stop at the universal cover is simply because that’s where you get a bijection.
I thought you were asking about interpreters: “And also, how are you interpreting, exactly??” I guess not. So, I think there’s some confusion about the Y combinator here. Consider the factorial function:
You might encode
nas a Church numeral. In this particular case,factorial(n)can also be beta-reduced to a Church numeral. Note though, thatfactorialitself is not a Church numeral. Now, consider the Serpinski triangleYou have some notion of how sets
Sshould be encoded, and you are worried thatserpinski(S)may not beta-reduce to fit that notion. Perhaps then you’ve got the wrong notion of sets, and should expand it to include objects likeserpinski(S). But perhaps that leads to nasty problems like Russell’s paradox. I’m not sure, but I suspect you won’t run into this problem.“To clarify 2 (though I think we don’t disagree here) - the reason you stop at the universal cover is simply because that’s where you get a bijection.”
Sorry, what bijection? Between the lifted rotations and… what?
Well, you really have F = lambda f,n: n * f(n-1) if n > 0 else 1, and then (YF)(n) beta-reduces to a church numeral. Our fixed point is the factorial function.
Trying to duplicate this with the sets in question: how should sets be encoded? I suspect that for any reasonable notion, you will have a problem where the fixed point might be some terrible thing.
As an example, suppose you try the most obvious way: a set is represented by a function that returns true for all elements in the set, and false otherwise. But how are we to plug in real numbers? Well, we could take computable approximations to the reals… but then we can’t even define the set {0} as a computable function! Even if we don’t allow something as pathological as the reals, decidable sets are much lesser than all the sets.
Any other way would, I think, have to basically be manipulating formal logic strings represented via e.g. a godel numbering and church numerals. Then, one defines the iteration as a function that takes in a string defining a set in first order logic, then outputs a first order logic string defining of the next iteration. But then, there’s no guarantee that the fixed point is a number, let alone a number corresponding to a logical formula that defines a set.
About the representations: in the finite dimensional case, there is a bijection between projective irreps of G and determinant 1 ordinary irreps of the universal cover of G. Apparently in the infinite dimensional case, you can only lift projective irreps to ordinary irreps in certain cases which include the Poincare group. I can’t tell if you would get a bijection in those cases.
I would be surprised if the motivation for projective irreps does not also motivate extending higher up the Postnikov tower; you don’t just stop at the universal cover.
As for sets, suppose you went with the definition: any function that takes in a rational number and spits out a boolean. So the Dedekind cut for
I expect that
could indeed be
(serpinski S)is also a set ifSis a set.