Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: deprecated: mathematics

Topic: endomorphism monoids of infinite sets

John Baez (Feb 03 2021 at 20:05):

Harvey Friedman has a new paper that he's hoping category theorists might find interesting. He has a bit of work to do if he wants to use standard terminology, but his results sound awesome:

• Harvey Friedman, Mappings of symmetric semigroups.

Abstract. The symmetric semigroups are the semigroups $D^D$ of all functions from a the set $D$ into $D$, under composition. The surjective equation preserving mappings of $D^D$ and the automorphisms of $D^D$ are the same, and are exactly the mappings of $D^D$ induced by bijections of $D$ by conjugation. Every infinite $D^D$ has a nonsurjective equation preserving mapping into itself (and which preserves the identity element). We seek nonsurjective mappings of $D^D$ with stronger preservation. Most notably, does every infinite $D^D$ have a non surjective mapping preserving the solvability of finite sets of equations with parameters (solvable equation preserving)? Even the existence of such $D^D$ is neither provable nor refutable from the usual ZFC axioms for mathematics, as such $D^D$ must be too large to fall within the grasp of ZFC (its cardinality must be far greater than a measurable cardinal). In fact, we show that the existence of such $D^D$ is equivalent to a very strong large cardinal hypothesis known as I2. I2 is far stronger than, say, the existence of a measurable cardinal.The existence of a nonsurjective mapping of some $D^D$ that preserves all first order statements (elementary embedding) is equivalent to the even stronger large cardinal hypothesis I1.

Matteo Capucci (he/him) (Feb 03 2021 at 20:33):

I read '12' instead of 'I2' in the penultimate sentence and I chuckled, I didn't expect ZF needed a separate axiom to count a dozen eggs

Matteo Capucci (he/him) (Feb 03 2021 at 20:34):

Can you translate a bit of the funky terminology here? Why is calling $D^D$ a semigroup? Isn't it a monoid?

Matteo Capucci (he/him) (Feb 03 2021 at 20:35):

Also the only way I understand 'equation preserving' is as 'injective', but then this would be a very large deviation from standard terminology :flushed:

Fawzi Hreiki (Feb 03 2021 at 21:11):

I guess its technically a semigroup too

Todd Trimble (Feb 03 2021 at 22:00):

Here and there he's referring to semigroup morphisms that aren't monoid morphisms, so presumably the distinction is important for what he's doing.

John Baez (Feb 03 2021 at 22:21):

Matteo Capucci (he/him) said:

Can you translate a bit of the funky terminology here? Why is calling $D^D$ a semigroup? Isn't it a monoid?

It's a monoid. I It's also a semigroup, and like most mathematicians, he's more familiar with the word "semigroup".

I don't think that required much translation. Which funky terminology are you interested in?

He's talking about endomorphisms of the semigroup $D^D$ with very strong properties.

John Baez (Feb 03 2021 at 22:22):

Here and there he's referring to semigroup morphisms that aren't monoid morphisms, so presumably the distinction is important for what he's doing.

You might be right, but I doubt it. I think he's only interested in monoid endomorphisms of $D^D$. He just doesn't like saying "monoid".

John Baez (Feb 03 2021 at 22:24):

I already told him category theorists would be thrown off by this, and now we see it happening. Nobody yet has commented on the actually interesting stuff. :upside_down:

Fawzi Hreiki (Feb 03 2021 at 22:28):

I more so just wish he used LaTeX

John Baez (Feb 03 2021 at 22:29):

I'd give up knowing LaTeX if I could prove theorems like this.

John Baez (Feb 03 2021 at 22:30):

Admittedly I'm better at some things than him. He gives a 7-line proof that conjugation by a bijection $f: D \to D$ gives an automorphism of the semigroup $D^D$, whereas I would do it in one word: "obvious".

John Baez (Feb 03 2021 at 22:32):

Okay, sticking to trivial stuff: on page 12 he admits:

Note that all symmetric semigroups are in fact monoids where the identity element is the identity function.

John Baez (Feb 03 2021 at 22:33):

Actually it's possible that he cares about semigroup endomorphisms of $D^D$ that aren't monoid endomorphisms....

Fawzi Hreiki (Feb 03 2021 at 22:52):

Well I guess that's why you can't prove theorems like this. No category theorist would ever really consider such maps.

John Baez (Feb 03 2021 at 23:12):

Heh. Harvey Friedman just confirmed my guess that in fact all his interesting results concern monoid endomorphisms of $D^D$.

John Baez (Feb 03 2021 at 23:13):

So he's just saying "semigroup" because he feels like it; he could say everything in terms of monoids.

John Baez (Feb 03 2021 at 23:13):

I think I've persuaded him to point out explicitly that his amazingly weird endomorphisms $D^D \to D^D$ are actually monoid endomorphisms.

John Baez (Feb 03 2021 at 23:14):

(Though I'm sure he won't say it that way, since he's not the kind of guy who says "monoid endomorphism", even though he's writing a paper about monoid endomorphisms of endomorphism monoids.)

John Baez (Feb 03 2021 at 23:29):

So here's one of his two amazing theorems. I will speak in terms of semigroups just to be sure I'm not making a mistake, but I bet I could talk about monoids here.

Definition. A semigroup homomorphism $j: G \to H$ is an elementary embedding if and only if any first order statement in the language of semigroups with parameters in $G$ holds in $G$ if and only if it holds in $H$ with the parameters replaced by their values under $j$.

This is a special case of the general concept of elementary embedding well-known in logic. (I'm linking to the nLab to give a slightly more category-friendly definition of this).

Theorem 3.2.48. There is a set $D$ and a nonsurjective semigroup homomorphism $j: D^D \to D^D$ that is an elementary embedding iff there is an $\mathrm{I}2$ cardinal.

John Baez (Feb 03 2021 at 23:36):

To see how cool this is, the main thing to know about $\mathrm{I}2$ cardinals is that they're insanely large cardinals. If you've heard of super-huge cardinals, measurable cardinals, etc., $\mathrm{I}2$ are all those things and much more. There are only two well-known kinds of large cardinals bigger than $\mathrm{I}2$ cardinals, and those are $\mathrm{I}1$ and $\mathrm{I}0$ cardinals:

• Wikipedia, Rank-into-rank.

John Baez (Feb 03 2021 at 23:37):

Friedman has a somewhat fancier version of Theorem 3.2.48 that replaces $\mathrm{I}2$ by $\mathrm{I}1$.

John Baez (Feb 03 2021 at 23:37):

I don't understand any of this stuff very well, btw.

John Baez (Feb 03 2021 at 23:51):

But basically he has shown that some shocking properties of the endomorphism monoid $D^D$ imply (and are implied by) seemingly much more shocking properties of the universe of sets!

For example: if you can find a nonsurjective elementary embedding of $D^D$ into itself for some set $D$, there's a cardinal $\lambda$ such that there's a nonsurjective elementary embedding of the von Neumann universe $V_\lambda$ into itself.

Todd Trimble (Feb 04 2021 at 02:41):

John Baez said:

Here and there he's referring to semigroup morphisms that aren't monoid morphisms, so presumably the distinction is important for what he's doing.

You might be right, but I doubt it. I think he's only interested in monoid endomorphisms of $D^D$. He just doesn't like saying "monoid".

On closer inspection, you're right -- I was giving Friedman too much credit in this particular respect.

John Baez (Feb 04 2021 at 02:55):

Friedman told me

I always heard and used the word semigroup. So I was reluctant to use the word monoid because i thought it would scare off a lot of people in fields far from category theory.

I convinced him to issue a new draft that makes it clearer that we might as well be talking about monoids... though he still says "semigroup" most of the time, for the above reason.

Nathanael Arkor (Feb 04 2021 at 03:01):

I'm surprised a mathematician could be scared off by one new definition.

John Baez (Feb 04 2021 at 03:10):

Friedman's goal is to bring logic to the masses, by finding easy-to-state theorems that require large cardinal axioms to prove. His is a mission of popularization. So he prefers to state a theorem that says

"blah blah blah.... familiar concept... blah blah blah..."

than a theorem that says

"blah blah blah.... unfamiliar concept... blah blah blah..."

And he thinks more mathematicians know about "semigroups" than "monoids". (I think he's probably right about that.)

dusko (Feb 04 2021 at 04:02):

thanks for sharing this. i am certainly no expert in this (or other things) but as far as i can tell, harvey friedman seems to be playing unusually simple game here. how far can we lift dedekind's definition of infinity, as properly injective embeddability? the first step is drop dead simple: take a proper embedding of an infinite set into itself, and make an inner automorphism from it. sure enough semigroup of endomorphisms of a dedekind infinite thing is still dedekind infinite. then the I2, I1, I0 game kicks in. it turns out that we need to assume that sufficiently infinite things exist in order to prove that these particular things are dedekind infinite. where "things" tend to be constructible universes at suitably unreachable levels. that is nice because it provides an opportunity for finetuning, like kunen's result. but that is a little bit like analyzing the assumptions needed for the existence of god. at the time when they discussed that in paris, galileo came up with the idea to turn one of the "spyglasses" that he was selling to generals and look at the sky, to see if he will see anything. and he saw something. instead of wondering in advance how big cardinals do we need (as suggested by fefferman in the arguments against maclane) we can simply construct stuff. after we construct it, we count it, and we see how big are the cardinals. it is a little bit like turing: he didn't want to say that the tape in his machine is infinite. he just said it was unbounded. and you all know that he was right. if you need more memory, you buy an external drive. i somehow think that we have bigger worries than whether categories or semigroups are insufficiently infinite.

dusko (Feb 04 2021 at 04:03):

oh and i think that the validity of friedman's results without the identity allows extending them to ideals, including within monoids or categories, and then to calculi of fractions.

David Michael Roberts (Feb 04 2021 at 07:40):

@John Baez can you fix the link in your first post? It seems to be broken, and all this talk of updating drafts makes me think the pdf linked there might have passed on.

Nathanael Arkor (Feb 04 2021 at 13:40):

The PDF link is working for me now.

John Baez (Feb 04 2021 at 16:17):

The link in my first post works for me - I tried it again just now:

https://u.osu.edu/friedman.8/files/2021/02/SymmetricSemigroups020221.pdf

But if you go to item 51 here:

https://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/

you'll see the current draft is at

https://u.osu.edu/friedman.8/files/2021/02/SymmetricSemigroups020321b.pdf

John Baez (Feb 04 2021 at 16:18):

He has now bent over backward, e.g. in the abstract, to satisfy people who prefer their semigroups to have identity elements, and their homomorphisms between semigroups to preserve identities.

John Baez (Feb 04 2021 at 16:20):

I think you were the first one who told me about rank-into-rank embeddings, @David Michael Roberts.

dusko (Feb 04 2021 at 18:58):

John Baez said:

He has now bent over backward, e.g. in the abstract, to satisfy people who prefer their semigroups to have identity elements, and their homomorphisms between semigroups to preserve identities.

this is interesing. the background of the effort seem to be laver's tables, which is a construction in the theory of braid groups which richard laver prudiced using a large cardinal assumption. dehornoy recently showed that the large cardinal assumption is not needed. friedman seems to have tried to broaden the framework and generalize the construction so that the large cardinal assumption would still be needed. so he broadened from braid groups to semigroups. it does seem potentially useful that his results do not require the unit (identities) because* the quest is for a right framework, and the quotienting by ideals (or "multiplicative systems") or calculi of fractions enter scene often. yet the interest of category theorists who say "hey we like units and our morphisms preserve the units" is worth more than that.

the effort to find constructions that require large cardinals goes back to the root of set theory. it started with cantor noticing that one infinity is not enough if you need to filter out the isolated points in the domain of convergence of a fourier series. so he started studying the hierarchy of infinities. the trouble (and the reason why i said yesterday that this is like the quest for the proof of the existence of god) is that it is not easy to find reasons why you need more infinities. ok, dedekind showed that you need an infinity to pack more visitors into (what came to be called) the hilbert hotel when it is full. but a hilbert hotel of hilbert hotel does not take you beyond that. laver's constructions with the left distributivity were a justification for the super-infinities. but bah, braid groups don't need them.

can it be that the large cardinal constructions will end up with functor categories as their sole remaining raison d'etre?

dusko (Feb 04 2021 at 19:08):

(i certainly don't think that latexing stuff should be a party duty, but pressing on through the text with a typewriter does risk leaving gaps behind. which happened before. and the desired result, that a large cardinal assumption is necessary, is bound to be through the eye of a needle. so if any of the young people would see it fit to carefully go through the text, it would be good to know that there are no assumptions left to be proved in the next paper.)

John Baez (Feb 04 2021 at 19:49):

Harvey Friedman loves to talk to people about his work, so it's also good to just ask him if there are assumptions left to be proved... in a friendly and if possible technical sort of way.

John Baez (Feb 04 2021 at 19:50):

the background of the effort seem to be laver's tables

Is there anything technical in Friedman's paper that suggest this, or is this just your knowledge of the history of this sort of endeavor?

John Baez (Feb 04 2021 at 19:53):

The really hard proofs in Friedman's paper start around section 3.2, and they're not the sort of thing I can read and understand without extreme pain.

John Baez (Feb 04 2021 at 20:37):

By the way, I wrote an article explaining the basics of Laver tables - even though I don't really understand much about them:

• Shelves and the infinite.

John Baez (Feb 04 2021 at 20:40):

It's about a sequence of natural numbers, defined in a fairly straightforward way, that's non-decreasing... but nobody knows if it reaches the value 32...

....unless we assume an extra axiom in set theory, asserting the existence of an $\mathrm{I3}$ cardinal.

Nathanael Arkor (Feb 04 2021 at 20:50):

John Baez said:

By the way, I wrote an article explaining the basics of Laver tables - even though I don't really understand much about them:

• Shelves and the infinite.

That's very interesting (and surprising)!

John Baez (Feb 04 2021 at 21:15):

Yeah, it's weird. I got interested, originally, because my student Alissa Crans came up with name "shelf" for a set with a binary operation that distributes over itshelf.

John van de Wetering (Feb 04 2021 at 23:17):

John Baez said:

By the way, I wrote an article explaining the basics of Laver tables - even though I don't really understand much about them:

• Shelves and the infinite.

Results like these make me appreciate how fundamentally weird mathematics can sometimes get. Like, people give quantum mechanics a hard time for being unintuitive, but it pails in comparison to this stuff.

John Baez (Feb 05 2021 at 00:44):

True!!! This is a great example of the weirdness lurking in math.

David Michael Roberts (Feb 05 2021 at 01:33):

@John Baez huh, that's cool. Thanks for checking the link. For some reason it didn't work for me, but I knew where Friedman's website with his preprints was, so I went and checked it out.

I think he buries the lede a little, in that the theorem about the equivalence of I2 (and its variants) gives more: if lambda is an I2 cardinal, then Hom(\lambda,\lambda) is the sort of monoid that he's interested in. Then if you have an one of these monoids M=Hom(D,D), then |D| is no smaller than the I2 cardinal \lambda he constructs. So these monoids are absolutely enormous.

John Baez (Feb 05 2021 at 02:05):

Yes, enormous. I just assumed |D| would be the I2 cardinal, since being I2 is all about "nonsurjective self-embeddings". So yes, this is not a case of large cardinals having implications for smaller mathematical objects (another thing Friedman loves).

Morgan Rogers (he/him) (Feb 05 2021 at 11:11):

John Baez said:

By the way, I wrote an article explaining the basics of Laver tables - even though I don't really understand much about them:

• Shelves and the infinite.

So, we can define
$f \rhd g = \bigcup_{\alpha < \lambda} f (g \cap V_\alpha)$
Laver showed that this operation distributes over itself:
$f \rhd (g \rhd h) = (f \rhd g) \rhd (f \rhd h)$
And, he showed that if we take one elementary embedding and let it generate a shelf by this this operation, we get the free shelf on one generator!

Because of the broad successes of categorical algebra, we (by which I mean "I") sometimes take for granted that free things exist. Of course, there is no free complete Boolean algebra on countably many generators, but I always thought that was attributable to weird second-order shenanigans. Being told that the existence of a free shelf, which seem so simple to describe, relies on large cardinal assumptions, is pretty mind-boggling.

Nathanael Arkor (Feb 05 2021 at 14:01):

Being told that the existence of a free shelf, which seem so simple to describe, relies on large cardinal assumptions, is pretty mind-boggling.

Is this what's happening? A shelf is a (finitary) algebraic structure, and all such algebraic structures may be freely generated. What am I misunderstanding?

Matteo Capucci (he/him) (Feb 05 2021 at 14:13):

That's also what I understood from John's article, which is mind-blowing, and, I have to say, very confusing to me. What's up with $\rhd$ that finitely many elements do not suffice?

Morgan Rogers (he/him) (Feb 05 2021 at 14:15):

That's a valid question... Shouldn't a free shelf be a quotient of a free magma, and so countable?

Morgan Rogers (he/him) (Feb 05 2021 at 14:22):

There doesn't happen to be a non-trivial elementary embedding $V_{\omega} \to V_{\omega}$, does there? :stuck_out_tongue_closed_eyes:

Amar Hadzihasanovic (Feb 05 2021 at 15:39):

I don't think John's post says anything about the existence of free shelves relying on large cardinal assumptions. Rather, a specific construction of the free shelf on one generator relies on a large cardinal assumption, and the proof that the sequence $P(n)$ diverges relies on this specific construction. That's what I understood, at least.

Amar Hadzihasanovic (Feb 05 2021 at 15:49):

I'll try to rephrase what I understood in case it helps...

You take the free shelf $F$ on one generator $1$, which has a countable carrier set. If we define inductively $k + 1 := k \triangleright 1$ for all natural numbers $k > 0$, distributivity implies that every element of $F$ is equal to some $k > 0$, so this is in fact a surjective assignment.

Then you let $F_n$ be the quotient of $F$ by the equation $2^n + 1 = 1$. The carrier set of this shelf has $2^n$ elements.

Now you consider the sequence $k \mapsto 1 \triangleright k$ in $F_n$. This sequence has a period $P(n)$ which depends on $n$. What relies on the existence of I3 is only the proof that $P(n)$ diverges for $n \to \infty$.

Morgan Rogers (he/him) (Feb 05 2021 at 15:51):

So the statement I quoted from John's article is inaccurate, I guess. That's a relief, I can begin the process of de-boggling my mind a little.

Amar Hadzihasanovic (Feb 05 2021 at 15:53):

The statement is

And, he showed that if we take one elementary embedding and let it generate a shelf by this this operation, we get the free shelf on one generator!

I read this as “the shelf constructed in this way is isomorphic to the free shelf on one generator”... it doesn't say that it is the only way to construct the free shelf on one generator (sure enough, there is a syntactic model).

Amar Hadzihasanovic (Feb 05 2021 at 15:54):

Do you see an “only if” anywhere? Maybe I missed it.

John Baez (Feb 05 2021 at 16:12):

I don't see any inaccuracy. I meant what Amar said: this construction using an elementary embedding is one way to construct the free shelf on one generator. You can also just construct it syntactically, by taking the set of expressions like

(1 ▹ 1) ▹ (1 ▹ (1 ▹ ((1 ▹ 1) ▹ 1)))

and quotienting by an equivalence relation: the distributive law.

John Baez (Feb 05 2021 at 16:17):

I'll add that nobody knows if large cardinal axioms are required to understand the sequence I described in terms of shelves. We can prove it approaches infinity using ZFC + the existence of an I3 cardinal. Nobody knows whether or not we can settle this question using ZFC. All we know is that approaches infinity very slowly.

Morgan Rogers (he/him) (Feb 05 2021 at 16:33):

Ah, silly silly me. I was reading $V_\lambda$ as the carrying set and $f$ as the operation, but that doesn't make any sense, since $f$ is unary and ${\rhd}$ is binary :see_no_evil: So the result is saying "Consider the shelf of all elementary embeddings on $V_{\lambda}$ with the given binary operation $\rhd$. Then any sub-shelf generated by a single, non-trivial element is free."

Morgan Rogers (he/him) (Feb 05 2021 at 16:34):

Which includes as a corollary that there are at least countably many such embeddings as soon as there is one, which is neat.

Morgan Rogers (he/him) (Feb 05 2021 at 16:39):

John Baez said:

I don't see any inaccuracy.

It's a good thing I don't mind looking like an idiot here. It's perfectly clear now that I've read it properly :upside_down:

John Baez (Feb 05 2021 at 19:38):

No problem! It's better to question things that seem weird, rather than quietly accept them or quietly decide someone else is saying nonsense. And a little confusion, and a little discussion, are a great way to get more people to think about this fascinating stuff.

dusko (Feb 06 2021 at 03:31):

John Baez said:

the background of the effort seem to be laver's tables

Is there anything technical in Friedman's paper that suggest this, or is this just your knowledge of the history of this sort of endeavor?

questions in the form "A or B" are easily misunderstood as tendentious. it is probably true that my knowledge at this age can only concern history, but the way in which the proper self-embeddings $V_\lambda$ arise from laver's tables was in dehornoy's famous self-distributivity book. it is actually even in his recent textbook on set theory. the "inner automorphism" type constructions which friedman is pursuing echo laver's iterated applications, except that those were not associative...

but i should stick with history :)

thanks for the reference to you your article. i will read it.

John Baez (Feb 06 2021 at 16:11):

I'm just wondering whether there's some technical connection between Friedman's work and Laver tables, or... not. (Yes, another either-or question.)

Matteo Capucci (he/him) (Feb 06 2021 at 23:01):

Morgan Rogers (he/him) said:

John Baez said:

I don't see any inaccuracy.

It's a good thing I don't mind looking like an idiot here. It's perfectly clear now that I've read it properly :upside_down:

That makes it two of us :face_palm:

John Baez (Feb 06 2021 at 23:08):

Clearly something about the way I wrote that was confusing.

John Baez (Feb 06 2021 at 23:09):

Maybe a minimal fix would be to change

And, he showed that if we take one elementary embedding and let it generate a shelf by this this operation, we get the free shelf on one generator!

to

And, he showed that if we take one elementary embedding and let it generate a shelf by this operation, the result is isomorphic to the free shelf on one generator!

John Baez (Feb 06 2021 at 23:10):

This means the same thing mathematically, but it might point people in a better direction...

I'm perfectly happy to make this or some other small change.

dusko (Feb 08 2021 at 10:21):

John Baez said:

I'm just wondering whether there's some technical connection between Friedman's work and Laver tables, or... not. (Yes, another either-or question.)

Yes.