Timeline for What oracles make finding isomorphism (of finite structures) easy?
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 25 at 16:48 | vote | accept | Noah Schweber | ||
| Oct 24 at 16:11 | history | edited | Noah Schweber | CC BY-SA 4.0 |
added 244 characters in body
|
| Oct 23 at 12:35 | answer | added | Emil Jeřábek | timeline score: 5 | |
| Oct 22 at 23:34 | comment | added | Noah Schweber | @cody Just literally the join of the reals coding them. Roughly, this is the binary sequence whose $2k$th bit is 1 iff the first structure satisfies the $k$th second-order sentence, and whose $2k+1$th bit is 1 iff the second structure satisfies the $k$th second-order sentence. (This isn't quite right because I actually want to look at second-order formulas being satisfied at tuples of elements, but meh.) So roughly, I'm asking about how being able to query each structure's second-order theory differs from being able to query the second-order theory of the "sum" of the structures. | |
| Oct 22 at 22:05 | comment | added | cody | Non expert question: what is the "join" of two second-order theories? | |
| Oct 22 at 17:52 | history | asked | Noah Schweber | CC BY-SA 4.0 |