Timeline for "Strange" proofs of existence theorems
Current License: CC BY-SA 4.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 2, 2019 at 2:53 | comment | added | Timothy Chow | @KConrad : Provided one takes some care in formulating the pigeonhole principle, one can prove it (by induction) in Heyting arithmetic, and hence in a certain precise sense it does not rely on proof by contradiction. See for example "Ramsey's theorem and the pigeonhole principle in intuitionistic mathematics" by Veldman and Bezem. | |
| Oct 13, 2018 at 4:49 | comment | added | KConrad | One of the conditions set by the OP was that the argument does not use contradiction, and I think anything involving the pigeonhole principle is in some sense relying on a proof by contradiction: if $f : A \rightarrow B$ and $|A| > |B|$ then $f$ can't be injective, because if $f$ were injective then $|A| \leq |B|$ and we have a contradiction. I was considering posting an argument with the pigeonhole principle earlier but chose not to due to the OP's desire not to see proofs that somehow involve contradiction. | |
| Oct 13, 2018 at 2:23 | history | answered | Timothy Chow | CC BY-SA 4.0 |