Timeline for Cardinal Arithmetic, foundations and constructive math
Current License: CC BY-SA 3.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 5, 2012 at 9:18 | vote | accept | Najdorf | ||
| Nov 5, 2012 at 9:17 | comment | added | Najdorf | Law of excluded middle is non-constructive. I have doubts about MP as well, if $A$ and $A \to B$ but it took a trillion years to get from $A$ to $B$ would that be constructive? I have realized that I use constructive in a much stronger form than anyone else here. For example, I have a class of graphs with $\chi = 5$ but the proof is classical, then I get a 5-coloring algorithm of order $O(|G|^{|G|})$. To my mind the algorithm is progress but still not constructive. In short being constructive without being computable in some sensible sense of the word does not make sense to me ... | |
| Nov 5, 2012 at 0:52 | comment | added | Noah Schweber | @Najdorf Especially in light of your rejection of some of Andrej's observations about constructive mathematics, I'm still confused: what is a "non-constructive consequence?" | |
| Nov 5, 2012 at 0:28 | comment | added | Guillaume Brunerie | @Najdorf Do you consider the law of excluded middle as being constructive? | |
| Nov 5, 2012 at 0:22 | comment | added | Joel David Hamkins | Najdorf, isn't any axiom non-constructive on that criterion? After all, the law of excluded middle is classically valid, and so any axiom has excluded middle as a consequence in classical logic. | |
| Nov 4, 2012 at 23:05 | comment | added | Najdorf | @all: I call an axiom AX non-constructive if it has non-constructive consequences in everyday classical mathematics we use. I thought that was the normal understanding of the term. | |
| Nov 4, 2012 at 23:03 | comment | added | Najdorf | @Blass I think you are right in your first comment. | |
| Nov 4, 2012 at 19:36 | comment | added | Noah Schweber | See, for instance, Section 7.2 of "On arbitrary sets and ZFC" by Jose Ferreiros (math.ucla.edu/~asl/bsl/1703/1703-002.ps), which points out that AC loses some of its nonconstructive flavor in the context of V=L. Also, I second Andreas' question about theory vs. model - in every sense I'm aware of, any model of ZFC+V=L must be at least as large as the theory. | |
| Nov 4, 2012 at 19:33 | comment | added | Noah Schweber | @Najdorf, the point of my comment is that things like GCH, AC, etc. are not "inherently" non-constructive (for a broad enough notion of "constructive"). To elaborate, the usual reason given for thinking of AC as non-constructive is roughly that it entails the existence of undefinable sets of reals. However, this isn't actually true: assuming V=L, every set of reals is definable (from an ordinal). What this means to me is that the idea that "AC is inherently nonconstructive" is flawed, or at least requires further explanation. Similar arguments apply to GCH, etc. (cont'd) | |
| Nov 4, 2012 at 14:42 | comment | added | Andreas Blass | @Najdorf: Your last comment adds some urgency to Noah's request that you explain your terminology. You have said that a certain countable set of sentences ("the theory itself") is "much bigger" than a certain proper class ("the model for $V=L$ done by Gödel"). You have also applied the word "constructive" to two things of very different types, a theory and a model, which leads me to think you have (at least) two meanings in mind for this word. | |
| Nov 4, 2012 at 11:07 | comment | added | Najdorf | @Noah, my understanding is that the model for V=L done by Godel is "constructive" but the theory itself (which is always much bigger than any single model ...) is not. | |
| Nov 4, 2012 at 11:02 | comment | added | Najdorf | @Ricky, well GCH implies AC ... | |
| Nov 4, 2012 at 11:01 | history | edited | Goldstern |
logic
|
|
| Nov 4, 2012 at 5:50 | comment | added | Noah Schweber | I'm not sure what you mean by "constructive," since that word can have many different meanings, but certainly this reason for GCH holding (in fact, all of V=L) seems fairly constructive, at least relative to what set theory tends to involve. | |
| Nov 4, 2012 at 5:47 | comment | added | Noah Schweber | Building off of Ricky's comment, I'd argue that in fact the presence of GCH is actually a reasonably constructive consequence of the axiom of constructibility (V=L). The reason that GCH holds assuming V=L is that from V=L we can actually define a precise well-ordering of the reals (in fact, of the entire universe, but that's a separate issue) and show that this well-ordering has order type $\omega_1$. This basically requires us to (1) determine the real number satisfying some first-order property, and (2) iterate that procedure through all the countable ordinals. (cont'd) | |
| Nov 4, 2012 at 4:15 | answer | added | Andrej Bauer | timeline score: 13 | |
| Nov 4, 2012 at 3:55 | comment | added | user5810 | How does the axiom of constructibility give us non-constructive math? $\:$ | |
| Nov 4, 2012 at 3:47 | comment | added | Andreas Blass |
$2^{\aleph_0}$ need not be smaller than $\aleph_\omega$. You may be thinking of the theorem that it cannot be equal to $\aleph_\omega$, but it might well be larger.
|
|
| Nov 4, 2012 at 1:55 | history | asked | Najdorf | CC BY-SA 3.0 |