Timeline for Order-independent properties arising naturally in mathematics
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 6, 2023 at 10:46 | comment | added | The Amplitwist | Reposting the link mentioned in the previous comment so that it appears in the "Linked" questions list: Objects which can't be defined without making choices but which end up independent of the choice | |
| Jun 25, 2013 at 3:02 | review | First posts | |||
| Jun 25, 2013 at 7:27 | |||||
| May 30, 2013 at 21:44 | answer | added | Noah Schweber | timeline score: 1 | |
| May 29, 2013 at 9:28 | answer | added | Jason Rute | timeline score: 1 | |
| May 28, 2013 at 17:19 | answer | added | Timothy Chow | timeline score: 4 | |
| May 28, 2013 at 17:12 | comment | added | Timothy Chow | Somewhat related MO question: mathoverflow.net/questions/131255/… | |
| May 28, 2013 at 15:24 | answer | added | Boris Novikov | timeline score: 0 | |
| May 28, 2013 at 12:44 | comment | added | user34458 | Yes, this is of course the background of this question. As you surely now, there are rather "artificial" constructions (which embed graphs into more complicated structures in such a way that it becomes possible to simulate monadic second-order logic on the graph) which show that first-order logic with an arbitrary linear order is more expressive than first-order logic without the order. As the example above shows, for first-order logic with modulo counting, there is a very "natural" property, which can be found in nearly every basic book on algebra, which proves the analogous statement. | |
| May 28, 2013 at 11:45 | comment | added | Emil Jeřábek | The question is quite interesting for logics between first and second order. In particular, inflationary fixed-point logic characterizes classes of structures recognizable in deterministic polynomial time in the presence of a linear order, but it is strictly weaker in general, and it is an open problem whether there exist a logic characterizing polynomial time on unordered structures at all. | |
| May 28, 2013 at 10:19 | comment | added | user34458 | While my phrasing of the question above was intentionally imprecise/non technical, I had something rather concrete on my mind. I am mostly interested in the case where some property which otherwise could not be stated in first-order logic becomes first-order definable (potentially with some generalized quantifiers as in the example above) in the presence of a linear order. For, say, second-order logic, the question becomes rather uninteresting, as you can always say "there exists some linear order such that ...". | |
| May 28, 2013 at 9:52 | comment | added | Ryan Budney | Your question generalizes quite naturally: throughout all mathematics, there tends to be pleasant formulations of theory whenever you have some kind of monoidal or group-like structure around. | |
| May 28, 2013 at 9:20 | history | asked | user34458 | CC BY-SA 3.0 |