Timeline for How to tell if a proof relativizes?
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 25, 2020 at 15:30 | comment | added | DeeDee | Yuval + @NoahSchweber sick, thank you ! | |
| May 25, 2020 at 15:28 | comment | added | Yuval Filmus | Yes, that is the conclusion. | |
| May 25, 2020 at 15:27 | comment | added | DeeDee | "If your proof relativizes, then what you prove also relativizes." So then because others have already shown that what was proved (the statement) does not relativize my proof is either wrong or cannot relativize. | |
| May 25, 2020 at 15:23 | comment | added | Noah Schweber | @RingRing Adding to Yuval's comment: conversely, a non-relativizing proof won't show that the statement doesn't relativize. A non-relativizing proof simply doesn't give any information about whether the result in question relativizes or doesn't. | |
| May 25, 2020 at 15:21 | comment | added | Yuval Filmus | If your proof relativizes, then what you prove also relativizes. The opposite doesn't necessarily hold. You could prove a statement that happens to relativize using a non-relativizing proof. Your proof won't show that the statement relativizes. | |
| May 25, 2020 at 15:14 | comment | added | DeeDee | okay sorry, so then how can i call on a result that C=B with respect to oracle O in order to show that my statement C!=B does not relativize (you said this is all i need to do in your first comment)? It would seem to me that it would be possible, based on what you are saying, that my result of C!=B could have been proven by a method that relativizes. If this is so then how does citing the existence of O, relative to which C = B, say that my proof doesn't relativize? sorry this is what I'm still confused about. | |
| May 25, 2020 at 15:06 | comment | added | Yuval Filmus | A proof can be relativizing, and a statement can be relativizing. If your prove a statement using a relativizing proof, then the statement is also relativizing. | |
| May 25, 2020 at 15:05 | comment | added | DeeDee | @NoahSchweber "So how can I reference the fact that other proofs of a statement relativize / don't relativize to help me prove my own relativization result about my proof of that statement?" This is the bottom paragraph in my question. How do I reconcile what you are saying with what Yuval is saying. You are saying relativization is a feature of the proof of a statement, not the statement. Yuval is seemingly saying the opposite that its a feature of the statement. the statement, not the proof, is what relativizes (is true or false with respect to certain oracles). | |
| May 24, 2020 at 23:59 | comment | added | Noah Schweber | @RingRing Let me add to this answer that we may indeed have the following situation: a non-relativizing proof of a result is found, and then later a relativizing proof is also found. A given result may have many very different proofs. | |
| May 24, 2020 at 19:46 | comment | added | Yuval Filmus | That's all you need to do. | |
| May 24, 2020 at 18:41 | comment | added | DeeDee | So, if my result is C != B. and someone else has a result that C^O = B^O relative to O, then this is all that is needed to say that the result C=!B does not relativize, all i need to do is cite the example that C^O = B^O and this proves my result C=! B does not relativize? Or are there more steps? Sorry this is what im confused about. | |
| May 24, 2020 at 18:29 | history | answered | Yuval Filmus | CC BY-SA 4.0 |