Timeline for Combinatorially defined effectively closed set
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 28, 2020 at 1:37 | comment | added | Bjørn Kjos-Hanssen | I'm guessing that "naturally occurring in mathematics" can substitute for "combinatorial". In that case, arguably separating A and B is not natural, since what we really want to do is compute A and B themselves. | |
| Feb 27, 2020 at 11:34 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
added 26 characters in body
|
| Feb 27, 2020 at 11:10 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
added 2158 characters in body
|
| Feb 27, 2020 at 10:27 | comment | added | Joel David Hamkins | The method of the answer is completely general, and works with any computably inseparable pair. So all you need are "combinatorial" computably inseparable sets. But I don't believe that you have a robust concept of what counts as combinatorial, if you exclude all logic and computability theory. | |
| Feb 27, 2020 at 4:13 | comment | added | Jiayi Liu | Thanks for responding @JoelDavidHamkins~ But this definition isn't purely combinatorial. I will add more explanation in my question. | |
| Feb 26, 2020 at 21:05 | comment | added | Noah Schweber | I don't object - I didn't downvote after all - I only meant to get ahead of what I suspect will be the OP's response. | |
| Feb 26, 2020 at 20:59 | comment | added | Joel David Hamkins | So why object then? We can say what counts as combinatorial, and I affirm that the operation of Turing machines counts as combinatorial. | |
| Feb 26, 2020 at 20:44 | comment | added | Noah Schweber | I mean, I would agree, but I find all computability to be combinatorial. :) | |
| Feb 26, 2020 at 20:22 | comment | added | Joel David Hamkins | It seems perfectly combinatorial to my way of thinking, since it is about the nature of a finitary discrete process. I suppose one could ask what are the most natural computably inseparable sets? Another good example is where A is the set of theorems of PA (or consistent c.e. theory of arithmetic) and B is the set of negations of theorems. | |
| Feb 26, 2020 at 18:35 | comment | added | Noah Schweber | I suspect that this won't match the OP's criterion of "combinatorially defined" (although it's unclear what that means right now). | |
| Feb 26, 2020 at 18:32 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
added 3 characters in body
|
| Feb 26, 2020 at 18:27 | history | answered | Joel David Hamkins | CC BY-SA 4.0 |