Timeline for What is the minimal size of a partial order that is universal for all partial orders of size n?
Current License: CC BY-SA 2.5
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 4, 2020 at 8:14 | answer | added | Louis Esperet | timeline score: 6 | |
| May 25, 2010 at 15:15 | answer | added | Travis Service | timeline score: 5 | |
| May 25, 2010 at 15:08 | answer | added | Fedor Petrov | timeline score: 27 | |
| May 25, 2010 at 14:41 | comment | added | Joel David Hamkins | Correction: my student's lower bound is $n\log(n)-n$. | |
| May 25, 2010 at 14:09 | comment | added | Joel David Hamkins | The concept of universal structures is important in model theory and used in set theory (although usually for infinite structures). Also, the easiest way to show that every countable partial order embeds into the Turing degrees is to consider orders that are universal for countable orders (and there are countable such orders). For the warm-up to that theorem, we first embedded the finite powersets into the Turing degrees, and then concluded that all finite orders embed by universality. | |
| May 25, 2010 at 13:58 | comment | added | Pete L. Clark | Neat question. I guess the logic tag is because it came up in your logic class? | |
| May 25, 2010 at 13:55 | history | asked | Joel David Hamkins | CC BY-SA 2.5 |