Timeline for When more is less in logic
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 27, 2022 at 10:12 | comment | added | wlad | A more basic example - computability related - is finding a line between two points $p$ and $q$ in $\mathbb R^2$. This is uncomputable - but if you add the condition $p \neq q$, then it's computable. The above quaternion example is equivalent to it. | |
| Dec 27, 2022 at 10:07 | comment | added | wlad | Another example - computability related - is finding the square root of a quaternion $q$ instead of a complex number. The problem is uncomputable. But add the condition $q$ is not in $\mathbb R^-$ (the negative part of the real line) and it's computable. | |
| Dec 27, 2022 at 10:04 | comment | added | wlad | In the sheaf topos $\operatorname{Sh}(\mathbb C)$ the statement "all complex numbers have a square root" is false, but the statement "all non-zero complex numbers have square roots" is true. More generally, the statement "all non-zero complex numbers have square roots" is true in every topos with a NNO. | |
| Dec 13, 2022 at 23:08 | history | became hot network question | |||
| Dec 13, 2022 at 22:00 | comment | added | Sridhar Ramesh | If we take any case where a theorem is provable in a strong system S, but is not provable in a weaker system W, then as we step through a proof of this theorem in system S, we will find some primitive steps trivially licensed in system S but not in system W. Adding the specific license to infer those particular steps as "trivial" extra conditions (as these are indeed trivial one-step inferences in system S) will then make the theorem provable in system W. | |
| Dec 13, 2022 at 21:43 | answer | added | Joel David Hamkins | timeline score: 5 | |
| Dec 13, 2022 at 21:06 | answer | added | Timothy Chow | timeline score: 7 | |
| Dec 13, 2022 at 20:06 | comment | added | Sam Sanders | @TimothyChow: I actually wanted to add "examples from set theory are explicitly welcomed", but thought better of it. So by all means go ahead. | |
| Dec 13, 2022 at 18:30 | comment | added | Timothy Chow | I can think of some examples involving the axiom of choice; e.g., theorems which can be proved in ZF if the hypothesis is "trivially" strengthened from "infinite" to "Dedekind-infinite." But it sounds like maybe you're interested in much weaker base theories than ZF? | |
| Dec 13, 2022 at 15:04 | history | asked | Sam Sanders | CC BY-SA 4.0 |