Jason (jcreed) wrote,


To read: http://www.cs.cmu.edu/~bryant/pubdir/CMU-CS-92-160.ps
Aha! General u-structures don't have a Cantor-Bernstein-like
property. Consider

*->*->*... vs. ...*->*->*...
...*->*->*... ...*->*->*...
...*->*->*... ...*->*->*...
...*->*->*... ...*->*->*...
. .
. .
. .

There's an injective u-homomorphism from A to B
which takes every * across the picture to the one
in B -- it's not a bijection since it misses the
infinite head of the first copy of \Z in B.
There's also an injective u-homomorphism from
B to A, taking * across to the left and down one
row, which misses the \N-like row in A. Now suppose
there was a u-isomorphism f from A to B. The head
of the \N in A, say x, has to go somwhere f(x) in B,
and every element of B has a predecessor. So what's
f^{-1}(S^{-1}(f(x)))? Well, S(f^{-1}(S^{-1}(f(x))))=x
since f and f^{-1} are homomorphisms, but x was
chosen not to have a predecessor, contradiction.

I -think- I've got a proof that u-structures with
an injective successor map with no infinite predecessor
chains (loops are okay) -do- have a C-B-like property.

I also think the general u-structure counterexample
can be extended to show that it doesn't work for
monoids, either, but I'm not sure how to deal with groups.

Saw Liz Harvey play the underground.
Damn good music, donno about her politics.
Oh well.

Watched more Card Captor, KOR. Eugh. Baaad crack.

  • (no subject)

    Played some board games at the fb office with newly-arrived-to-nyc dan blandford and some friends-of-friends of his. Codenames and…

  • (no subject)

    This morning I suddenly had a memory of a game I used to play in the mid-late 90s over email. In it you "designed" animals by giving them, like, 4…

  • (no subject)

    Played some more Shenzhen I/O. The later puzzles are getting straight up hard. Had some fun optimizing the earlier ones, though.

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded