User ed dean - MathOverflow

Answer by Ed Dean for A question about Quine's set theory NF.

2012-09-30T21:54:25Z

One can give stratified definitions for individual Frege-Russell natural numbers, and then so too for the set $\mathbb{N}$ of all Frege-Russell naturals, so that exists in NF. One can then check that the set $$\mathcal{T} = \{X\subseteq\mathbb{N} : \exists n\in\mathbb{N} (X = \mathbb{N}\setminus\{0,\dots,n\})\}$$ has a stratified definition, and so it too provably exists in NF. This $\mathcal{T}$ is the obvious candidate for witnessing that $\mathbb{N}$ is Tarski-infinite; we just need to know that NF proves it has the desired property.

The only sticking point for that would be showing that $$\mathbb{N}\setminus\{0,\dots,n+1\} \subsetneq \mathbb{N}\setminus\{0,\dots,n\}$$ for all $n$, and specifically that the inclusion really is proper, i.e. that none of our Frege-Russell naturals is empty. But this is where Specker's 1953 heavy lifting comes into play; namely, his proof that the universe $V$ cannot be well-ordered also implies that it is "Frege-infinite," i.e. $\forall n\in\mathbb{N} (V\notin n)$, because NF can prove that all Frege-finite sets are well-ordered. In turn, the fact that $V\notin n$ forall $n$ can be used to show that $n\ne\emptyset$ for all $n$, as required.

Answer by Ed Dean for Is there a general theory of models that has as instances classical FOL, classical propositional logic, etc.?

2012-06-20T20:17:47Z

What you are after is institution-independent model theory, for which Diaconsecu has a recent textbook account. Here the bare concept of an institution is basically that of a logical system absent particular distinguishing features; things such as classical first-order logic, higher-order logic and intuitionistic logic are then instances of institutions.

Answer by Ed Dean for Axiomatic Set Theory

2012-05-05T21:14:55Z

Foundations of Set Theory by Fraenkel, Bar-Hillel and Levy is a classic that provides what it sounds like you're after. It surveys ZF and its milieu, type-theoretic approaches (including Quine's New Foundations, for instance), intuitionism, and more.

Though I don't know your exact goal, or how specifically your interest is tied to set theory as opposed to, say, somewhat broader foundations of math concerns, you might find Steve Awodey's "From Sets to Types to Categories to Sets" to be useful. It is a short, focused and enlightening look at these prominent approaches to foundations in relation to one another, and it offers a nicely ecumenical account. E.g. this passage from the concluding section:

the objects of type theory and set theory are structured by the operations of their respective systems in certain ways that are not mathematically salient. That additional information is essentially what is lost by our comparisons ... Categorical structure is closer to the mathematical content, and it is not lost in translation. ... The structural approach implemented by category theory is thus more stable, more robust, more invariant than type or set theoretic constructions. On the other hand, type and set theory have certain distinctive advantages as well. ...

Answer by Ed Dean for Set-Theoretic Issues/Categories

2012-04-22T09:02:47Z

Regarding (1), the definition of category already doesn't rule out instances in which the collection of morphisms between two objects might be class-sized; these are known as categories which fail to be locally small. Regarding (2), the main issue is that there will come points when size considerations play crucially into the possibility of certain constructions. I recommend Mike Shulman's very nice article "Set theory for category theory," which uses Freyd's special adjoint functor theorem to illustrate that point (in his section 2. Size Does Matter), and then goes on to explore many of the foundational approaches that can be taken to address considerations of size in category theory, e.g. Grothendieck universes, NBG set theory, Morse-Kelley set theory, and so on.

Answer by Ed Dean for Essential reads in the philosophy of mathematics and set theory

2012-04-18T05:31:32Z

Benacerraf and Putnam's Philosophy of Mathematics: Selected Readings is a pretty standard (as these things go) collection of seminal papers in the philosophy of mathematics generally, and in the philosophy of set theory in particular (Part IV). Looking farther afield, you could use Maddy as a guide to the literature and go through some of this syllabus, which largely builds around that volume.

You don't say exactly what papers of Maddy's you've read, so maybe this next isn't useful, but I remember getting a lot out of her Naturalism in Mathematics many moons ago, and maybe you'd prefer a single, focused work to a bevy of papers. Rather than a survey, this book takes a particular philosophical stance, and uses it to give a sustained argument against the idea of adopting $V=L$ as a foundational axiom. Along the way, Maddy situates her position among the traditional philosophy of math literature (e.g. Quine), while also dealing substantially with the set-theoretic issues/technicalities that necessarily intertwine with any attempts to do something serious.

Beyond the works already mentioned, if you seek current philosophical work that draws directly on the set-theoretic state-of-the-art, my humble suggestion is to look to folks like Peter Koellner (disclaimer: former advisor) and MO-superstar Joel David Hamkins.

Answer by Ed Dean for effective/constructive/algorithmic probability theory

2012-04-03T05:10:01Z

A recent paper that gives the sort of effective result you're after is Freer and Roy's Computable exchangeable sequences have computable de Finetti measures. From their introduction:

The classical result states that an exchangeable sequence of real random variables is a mixture of independent and identically distributed (i.i.d.) sequences of random variables. Moreover, there is an (almost surely unique) measure-valued random variable, called the directing random measure, conditioned on which the random sequence is i.i.d. The distribution of the directing random measure is called the de Finetti measure.

We show that computable exchangeable sequences of real random variables have computable de Finetti measures. In the process, we show that a distribution on $[0,1]^\omega$ is computable if and only if its moments are uniformly computable.

Like the work of Hoyrup and Rojas that you point to in your question, this paper operates under the type-2 theory of effectivity (TTE) framework for computable analysis (for more on which see e.g. Weihrauch's text Computable Analysis), though unlike Hoyrup and Rojas' work, notions from algorithmic randomness are not employed here.

I know you said you're after a theory for ruling out the "cheating" you describe. Really, there's nothing special about probability theory here, and I think computability theory itself (coming in this setting in the guise of TTE) is already what you want in order to determine when "cheating" is generally necessary. It just boils down to proving, for a given theorem, either (1) you can always compute the conclusion data from the hypothesis data, or (2) there are instances where it cannot be computed.

The Freer and Roy paper is an instance of the former; an instance of the latter can actually be found in a more recent paper of theirs, with Nate Ackerman, on conditional probability. From the abstract: "We ... show that there are computable joint distributions with noncomputable conditional distributions, ruling out the prospect of general inference algorithms, even inefficient ones. Specifically, we construct a pair of computable random variables in the unit interval such that the conditional distribution of the first variable given the second encodes the halting problem."

Answer by Ed Dean for Reference Request: Non-Standard Models of PA

2012-03-02T13:04:46Z

Richard Kaye's book Models of Peano Arithmetic is good and accessible. And I know that what Frank said in his comment, about its availability as a pdf online, is indeed true; though like Frank, I shan't give a link here.

Answer by Ed Dean for Higher categories in logic

2012-02-23T18:18:58Z

You would probably enjoy checking out homotopy type theory and Vladimir Voevodsky's corresponding program of univalent foundations for mathematics. Steve Awodey's survey article (linked to from that site) is a good starting point, and includes a spelling-out of a homotopical interpretation of Martin-Lof type theory.

Answer by Ed Dean for An undergraduate's guide to the foundational theorems of logic

2012-01-18T03:27:43Z

Edit: This answer was given to the original formulation of the question, which asked for five-minute explanations for laypersons met on the street, rather than handwavy introductions for undergraduates. Maybe it still works though.

Since I have only 5 minutes to tell a layperson, I'd channel the late George Boolos and explain the second incompleteness theorem using only one-syllable words (Mind 103, pp. 1-3).

First of all, when I say "proved", what I will mean is "proved with the aid of the whole of math". Now then: two plus two is four, as you well know. And, of course, it can be proved that two plus two is four (proved, that is, with the aid of the whole of math, as I said, though in the case of two plus two, of course we do not need the whole of math to prove that it is four). And, as may not be quite so clear, it can be proved that it can be proved that two plus two is four, as well. And it can be proved that it can be proved that it can be proved that two plus two is four. And so on. In fact, if a claim can be proved, then it can be proved that the claim can be proved. And that too can be proved.

Now, two plus two is not five. And it can be proved that two plus two is not five. And it can be proved that it can be proved that two plus two is not five, and so on.

Thus: it can be proved that two plus two is not five. Can it be proved as well that two plus two is five? It would be a real blow to math, to say the least, if it could. If it could be proved that two plus two is five, then it could be proved that five is not five, and then there would be no claim that could not be proved, and math would be a lot of bunk.

So, we now want to ask, can it be proved that it can't be proved that two plus two is five? Here's the shock: no, it can't. Or, to hedge a bit: if it can be proved that it can't be proved that two plus two is five, then it can be proved as well that two plus two is five, and math is a lot of bunk. In fact, if math is not a lot of bunk, then no claim of the form "claim X can't be proved" can be proved.

So, if math is not a lot of bunk, then, though it can't be proved that two plus two is five, it can't be proved that it can't be proved that two plus two is five. By the way, in case you'd like to know: yes, it can be proved that if it can be proved that it can't be proved that two plus two is five, then it can be proved that two plus two is five.

But if you were to start saying this to someone unsolicited, you might raise some eyebrows and be asked to leave the store or exit the bus. Proceed with care.

Answer by Ed Dean for History of Logic Development

2012-01-18T07:51:14Z

The scope of the figures you mention (Tarski, Frege, Peano, Wittgenstein, Russell) makes it a little unclear exactly what you're after. For instance, From Frege to Goedel (as mentioned by Mahmud) is an excellent compilation of early texts in mathematical logic -- you get e.g. Frege, Peano, Hilbert, Zermelo, Skolem, Herbrand, Goedel -- with helpful introductions included, but the focus is on the primary texts, rather than giving a single, unified account of the development of logic. And its relative lack of a philosophical focus means there's nothing like Russell or Wittgenstein to be found. [N.B. Along similar lines to this work, the two volumes of From Kant to Hilbert offer a more wide-ranging (in terms of subject and chronology) cross-section of works in the foundations of mathematics; note, though, that mathematical logic per se is not the focus there.]

Not knowing your background, or your exact goal, I would tentatively recommend Benacerraf and Putnam's Philosophy of Mathematics: Selected Readings. It has a great selection of works by the likes of Frege, Russell, Hilbert, Brouwer, Goedel, Von Neumann, Quine, and so on (and Wittgenstein is mentioned aplenty). In total, you get a lot about the interplay between technical matters in mathematical logic, foundations of math, and also related issues of a more straight-up philosophical nature (if you're into that sort of thing). It too doesn't give a single chronological narrative, but just skipping around the articles in that collection will give you a lot to chew on, and ultimately give you a better account of the development of modern logic than will primary sources (IMHO).

Answer by Ed Dean for Is there any literature about inner-replacement rule?

2011-12-30T00:51:59Z

I don't know a name for the particular inference you indicate, but its feature that it operates "deeply" within the formulas at hand rather than at the root of their parse trees brings to mind current proof-theoretic work in deep inference. Perhaps check out Alessio Guglielmi's Deep Inference in One Minute; you might find that this blurb jibes with some of your motivation. Guglielmi's site in general is pretty comprehensive about this area, of which I know very little.

Answer by Ed Dean for Does model-complete in a language with a constant symbol imply EQ?

2011-12-29T03:00:08Z

Per JDH's suggestion, I'll turn my earlier comment into an answer.

Assuming $T$ to be model-complete, then whenever $M$, $N$ and $A$ are all models of $T$, it would certainly follow from $A \subseteq M$ and $A \subseteq N$ that $M \models \phi(a)$ iff $N \models \phi(a)$ for any $a$ from $A$ (as whenever one model of $T$ is a substructure of another, it is in fact an elementary substructure). But in Marker's condition, $A$ can be any $L$-structure and is not required to be a model of $T$.

Any theory that has elimination of quantifiers is model-complete, but the converse is not true. Note that while Marker's Theorem 3.1.4 is stated for a theory in a language with at least one constant symbol, he notes afterward that the proof can be adapted to cover the case in which $L$ has no constant symbols; so if model-completeness were to have sufficed here, it would've implied that the false converse were true.

Incidentally, one very interesting theory which is model-complete yet does not admit elimination of quantifiers is the theory of the real field with exponentiation. This theory isn't known to be decidable, but MacIntyre and Wilkie showed that its decidability is implied by the real version of Schanuel's conjecture. (This nicely succinct postscript file of Kuhlmann's contains handy references.)

Answer by Ed Dean for Irreversible chess

2011-10-22T15:33:25Z

According to the rules you have set up, I believe that the following positions A and B give what you are after (even once Hauke's good point that pawn checks shouldn't be allowed is taken into account). In position A, it is black to move, and position B can be reached via 1. ... Bd8+ 2. Ne7++ Kc7. But from there, according to the rules you laid out, white's only moves are to shuffle the bishop between c6-d5-e4 (EDIT: and d7 and e8 too of course, thanks Noam), and black can only play around with the rook on h8.

Position A

Position B

Answer by Ed Dean for Elementary+Short+Useful

2011-04-03T21:29:13Z

Strong law of large numbers

Answer by Ed Dean for Elementary+Short+Useful

2011-04-03T20:09:12Z

Stone's representation theorem.

Answer by Ed Dean for Mathematical "urban legends"

2011-01-25T04:31:16Z

Professor A at Harvard told the following story, supposedly a first hand account of his student days at Chicago, though it never struck me as remotely plausible. (I think he just told it so that he would seem like a teddy bear in comparison.) But I wonder if anyone else has heard variants of this.

At the beginning of a course, Professor X would start asking some reasonable questions, the answers to which students taking the course could be expected to already know. Finally, he would ask one unfortunate student a question which no one taking the course would be able to answer. Upon the student's failure to answer correctly, Professor X wouldn't explain that the student's ignorance was justified, instead letting this event undermine the student's confidence about taking the course. Professor X would continue to single out this poor target for humiliation until he or she finally dropped the course. Professor A claimed to believe that Professor X's motivation was to have lit a fire under the remaining students and make them band together.

Again, it's a rather unlikely tale of abuse. Though perhaps with a plant "student" playing along as the victim it could be an effective ploy ...

Answer by Ed Dean for Independence of P = NP?

2010-12-21T10:10:10Z

This answer started life as a nascent comment intended for the back-and-forth above, but it ballooned into what follows.

ZW, as I pointed out above, your current question does parallel your earlier question about CH, as do the (very good) answers in each case. From your further comments, though, I think I now have some idea why the answers haven't satisfied you; I'll take a stab at answering what I think's bothering you. (If I'm right, then it's a fairly simple matter, but just one that wouldn't be the initial guess as the issue on MO. And if I'm wrong about what you don't like, oh well; but I've genuinely tried to figure out why you're unhappy with the answers so far given.)

The answers given try to clarify a (very common and understandable) mathematical confusion that people can have about independence results, but your further comment:

My confusion is, people take V as the standard model. But why so?

suggests something else is at the heart of what's bothering you personally. And now looking at your original question about $CH$, it seems clear there as well:

OK, Cohen has constructed a model in which both ZFC and ~CH are true. Isn't this model an answer to the continuum problem? Hasn't he showed that it is indeed possible to construct a set with cardinality between that of the integers and that of the reals? Why is it still not considered sufficient to settle CH? Why is one model not enough? Why for all models? In other words, why do we have to answer whether "ZFC |- CH" instead of just "CH" itself?

So it seems that part of what you're not happy with is simply the (extra-mathematical, somewhat conventional) privileged position of $ZFC$ as a foundational theory for mathematics. (Again, if I'm wrong in ascribing such thoughts to you, my apologies.) And that's perfectly fair; plenty of people have taken issue with that status for myriad reasons.

So maybe you're really thinking: "Hey, Cohen constructed this model $\mathcal{M}\models ZFC + \neg CH$, and I think this $\mathcal{M}$ can be (or should be, or is) the mathematical universe we all work in." Well that's a perfectly acceptable way to think, but now you no longer have a purely mathematical pursuit on your hands (one reason, by the way, why myself and others generally would be expecting to answer the question the way they did), thanks to the privileged position $ZFC$ enjoys. Now you've also got a sociological (and dare I say philosophical) endeavor, namely that of convincing fellow mathematicians of the truth/efficacy/beauty/... of your favored universe.

Those who answered you were working under the accepted convention that "settling" a problem means either proving it in $ZFC$, or refuting it there, or establishing its independence from $ZFC$, and answered your initial queries accordingly (and accurately). If I'm right about what you're finding unsatisfactory here, then you now get to immerse yourself in the delights of the philosophy of mathematics. Enjoy! (And if I'm wrong, at least I've only wasted my own time.)

Answer by Ed Dean for Why does the Kleene Hierarchy not collapse?

2010-12-19T08:48:25Z

You're right that the statement $\varphi(a,q,v,w)$ defined by $\forall x<a+q \,\, \exists y<a+v \,\, \forall z<a+w [P(x,y,z)]$ can be checked by a Turing machine. If I read you correctly, you're wondering whether (1) $\forall x \exists y \forall z P(x,y,z)$ is generally equivalent to (2) $\forall a \exists q,v,w \varphi(a,q,v,w)$, because an affirmative answer would conflict with the fact that the Kleene hierarchy doesn't collapse.

Happily, (1) and (2) aren't generally equivalent. Let $P(x,y,z)$ be the statement $x+z<y$ for instance. Then (2) is true: for any $a$, set $q=w=0$ and $v=a+1$, and the $y<a+v=2a+1$ that you need can always be witnessed by $2a$. But (1) is certainly false for this $P(x,y,z)$.

Answer by Ed Dean for A Game of Knights and Queens

2010-12-03T19:25:48Z

Here's how White (my new name for Player 1) wins in the $u=v=1$ case. The idea is of course for White to force the knight to an edge, where it can then be summarily captured. WLOG let's force the knight to the lower edge (in my coordinate system, that'll be the edge given by $n=1$). It's enough to show that whenever the knight stands at a point $(a,b)$, we can force a situation where its next move will either allow it to be captured, or will place it on a square whose $n$ coordinate is $<b$ ; that $n$ coordinate can't decrease forever, so White wins.

So suppose the knight starts at $(a,b)$, and the queen starts at $(c,d)$. Here's a painfully explicit strategy which works uniformly.

In case $c\ne a\pm 1$, White plays the queen to $(c,b+2)$ (the fact that $c\ne a\pm 1$ guarantees Black can't capture here). Now four of Black's moves head towards the bottom, so those are no problem. The moves to $(a-1,b+2)$ and $(a+1,b+2)$ are open to capture, so those are out. Thus Black must move to $(a\pm 2,b+1)$. But now White plays to $(a\pm 2,b+2)$, and Black's only safe moves are to squares with an $n$ coordinate of $b-1$, and the knight has been pushed down, establishing all that we need.

In case $c=a\pm 1$, White moves to $(c,b+4)$. Black's only safe non-retreat is then to $(a\pm 2,b+1)$. White plays to $(a\pm 2,b+4)$. Black has four safe moves; two place it on the $b-1$ row, and we are done. The other two place it back on the $b$ row, but such that we are now back in the previous case, so done.

I'm actually not sure how to be fully explicit in the $u=1,v=2$ case, so I'll just explain it conceptually. Roughly, if the two knights are far enough apart, it's like they aren't even part of the same game, leaving us with successive instances of the winning $u=v=1$ case. (I know very little about combinatorial game theory, but this idea of breaking up games into component sub-games is common. You can see the idea, for example, in this paper by Noam Elkies on pawn endgames, and I feel like this is a big part of thinking in Go, where various regions are their own little battles.) The second knight is irrelevant, the queen picks off one, then the other. On the other hand, if the knights are close enough, the queen will be able to attack both at once, and moreover can arrange that with either side to move, leading to a capture of one knight and reduction to the $u=v=1$ case.

Finally, if $u=1,v=3$, here's an initial position of the knights which White can't win. Place them at $(a,b)$, $(a+2,b+1)$ and $(a+4,b+2)$. They all protect each other here, and no matter where White places the queen, one of the "outer" knights has a safe square to move to, and can then just move back on the next move.

Generally, if $v=u+1$, White will usually be able to at least force repeated even trades of a single queen for a single knight, reducing to the winning $u=1,v=2$ case; but with huge numbers of pieces I don't know how to solidly argue this. For arbitrary $u,v$, the space of possibilities is such that I have absolutely no idea what can be said in general.

Answer by Ed Dean for Is it correct to state that basic primitive recursive functions are in fact combinators?

2010-12-02T07:35:38Z

Yes, if I'm right in assuming you mean to ask whether these can be construed without free variables in the lambda calculus. (If my assumption is wrong, I apologize; your question is rather terse.) You can see here, for instance, how the "Church numerals" (Zero among them, of course) can be introduced, along with Successor and various other primitive recursive functions.

Answer by Ed Dean for How much of ZFC does Quine's New Foundations prove?

2010-11-26T15:40:15Z

NF does prove Cantor's theorem in the sense you indicate, $|\mathscr{P}_1(X)|<|\mathscr{P}(X)|$ for any set $X$. The usual ZF proof goes through, because definitions in that proof which need to be stratified for it to work in NF, in fact are. But if you try to prove $|X|<|\mathscr{P}(X)|$, you no longer have the right stratification, so Cantor's theorem fails in NF in this sense (which is good, as the universal set $V$ can't have a lesser cardinality than any other set).

Generally speaking, in NF one cannot prove $|X|=|\mathscr{P}_1(X)|$ because the obvious bijection $x\mapsto \{x\}$ does not have a stratified definition. One way of increasing strength of NF-style theories is to assert that more and more sets are "Cantorian" in the sense that $|X|=|\mathscr{P}_1(X)|$ (or "strongly Cantorian" in the sense that the particular bijection $x\mapsto \{x\}$ exists). This idea goes back at least to some papers of Orey (if I recall correctly), and Holmes has had a lot to say about that. Solovay proved some interesting results that link up the consistency strength of such additional axioms (on top of NFU) with large cardinal axioms for ZF. See, e.g., the paper on NFUB here.

Answer by Ed Dean for FTA in first order setting

2010-11-22T18:02:05Z

As Ricky indicates above, talk of tuples of natural numbers can be coded as talk of natural numbers in the language of arithmetic (see e.g. Gödel's original incompleteness paper for a full, clear account; while he works there in a system of type theory rather than the first-order language of arithmetic, the idea of this coding is made plain), which gets around your issue of needing different numbers of quantifiers for different arguments. So there's no problem expressing FTA in the language of arithmetic.

As for proving FTA, it certainly can be done in Peano arithmetic (so FTA holds in all of its models, standard and nonstandard), but also in the much weaker $S^1_2$ if I'm not mistaken. Look up Sam Buss and bounded arithmetic if you're curious about that.

Answer by Ed Dean for Completion of ZFC

2010-11-22T05:39:28Z

Alex, you ask a lot of questions, and I'm in no position to say much about Ultimate L. I'll just address this initial matter:

And how do we know that there are (infinitely) many different completions of ZFC in the first place? Could it be that there is no way to consistently assign truth-values to all first-order sentences, i.e. that no completion exists?

The existence of these completions of ZFC follows from Lindenbaum's lemma, a standard ingredient of proofs of the completeness theorem for first-order logic, at least assuming ZFC to be consistent. This also speaks to your second question there: it could be that no completion of ZFC exists, but only if ZFC itself is already inconsistent.

Answer by Ed Dean for Is the space of continuous functions from a compact metric space into a Polish space Polish?

2010-11-14T04:17:51Z

Yes, it appears e.g. as Theorem 4.19 in Chapter I of Kechris' Classical Descriptive Set Theory. (The relevant page is visible in Google Books if it's not in your library.)

Answer by Ed Dean for Limiting set theory using symmetry

2010-11-14T04:00:54Z

If you're sure the paper in mind was on the arxiv, then this paper of Harvey Friedman's isn't it. But since you're after "corroboration for a line of thought [you are] pursuing at the moment," maybe it and its treatment of a principle of symmetric arguments could be of use to you nonetheless.

Answer by Ed Dean for Modal logic - satisfiability

2010-11-13T20:10:23Z

Your question as originally written (which Henry correctly diagnosed as problematic in two ways) does not match the more reasonable aim reflected in your comments to Henry's answer. Specifically, your comments make it sound like you want to show that the satisfiability of both $\diamond X$ and $\diamond Y$ implies the satisfiability of $\diamond X \wedge \diamond Y$, not the satisfiability of $X\wedge Y$ as your original phrasing states.

If your notion of satisfiability of a formula $Z$ is simply that there is some Kripke model $\mathcal{M}$ (with no restrictions on its accessibility relation) and some world $w$ in it such that $\mathcal{M},w\models Z$, then this weaker form of the question isn't too difficult to answer.

Let $\mathcal{M},w\models\diamond X$ and $\mathcal{N},v\models\diamond Y$. In particular, there is a world $u$ in $\mathcal{N}$ which is accessible from $v$ and satisfies $Y$. Now just form a new model $\mathcal{P}$ whose set of worlds is the union of those of $\mathcal{M},\mathcal{N}$, and whose accessibility relation is the union of those of $\mathcal{M},\mathcal{N}$, plus we set $u$ to be accessible from $w$. Then $\mathcal{P},w\models\diamond X \wedge \diamond Y$.

Henry's point about underspecification is still pertinent. I'm not sure I've gotten at what you want, and if you were to be limited to special kinds of Kripke frames, for instance, then the argument would need to say a bit more (ensuring we end up with an appropriate $\mathcal{P}$). I hope this is helpful.

Comment by Ed Dean

2012-10-02T03:43:22Z

Yes, Specker carries out his proof within NF. His short paper on the matter is available online for free: pnas.org/content/39/9/972 It's fairly self-contained, but it does appeal to some basic results established in Rosser's NF-based textbook Logic for Mathematicians.

Comment by Ed Dean

2012-09-29T08:20:42Z

Jakob, you might find the closely related Theorem 2.2 of the following paper to be of interest: dx.doi.org/10.4115/jla.2012.4.3

Comment by Ed Dean

2012-08-29T21:29:29Z

Just to be clear, I wasn't suggesting that ZFC is in any way lacking for motivation, or that it doesn't originate from a weakening of naive comprehension, and I agree wholeheartedly that the lines you quote from the OP are mistaken as written. I meant no more and no less in my comment than that part of ZFC (Choice and Foundation, please excuse the mention of Infinity) isn't axiomatized as it seems the OP intends, and so I thought ZF-Foundation (rather than ZFC) would speak more directly to what concerns the OP.

Comment by Ed Dean

2012-08-29T20:11:29Z

That was my initial reaction upon reading the question as well, but I think the point that kimtown is only after theories all of whose axioms (besides extensionality) are instances of comprehension. So ZFC in its entirety doesn't make the cut, and one would have to do without foundation, infinity and choice. (Though I suppose infinity could be recovered as part of the theory while respecting kimtown's criterion by adding as axioms the finitely many instances of stratified comprehension which Specker used in his proof that NF refutes choice.)

Comment by Ed Dean

2012-05-14T05:49:39Z

I second Yu's recommendation, which is very clear and accessible. Sacks' Higher Recursion Theory is also a good source for effective DST.

Comment by Ed Dean

2012-05-08T16:04:39Z

While it may not seem so, your question is off-topic for this particular site, but the FAQ can point you to better places to ask it. Here's a hint though: you want a one-to-one correspondence between maps $\{a,b\} \rightarrow \mathbb{R}$ and pairs of reals. Given a particular such map, what pair of real numbers might uniquely determine it among all other such maps?

Comment by Ed Dean

2012-05-05T08:07:48Z

Say, who gave this talk?

Comment by Ed Dean

2012-05-02T22:20:41Z

You're in the wrong forum, as your question isn't research-level. But the FAQ will point you to other good places to post this.

Comment by Ed Dean

2012-05-02T12:51:29Z

@James: I took the liberty of adding the lo.logic tag as Jason suggested, since that might get you some feedback beyond my somewhat deflationary answer.

Comment by Ed Dean

2012-04-30T21:22:58Z

You should probably get your screenshot of this one ready.

Comment by Ed Dean

2012-04-18T08:32:08Z

Colin McLarty's "Exploring Categorical Structuralism" (cwru.edu/artsci/phil/PMExploring.pdf) is another follow-up in the Awodey/Hellman series. Also, one can find in the FOM archives many instances through the years of Harvey Friedman and Vaughan Pratt debating the merits of category-theoretic foundations.

Comment by Ed Dean

2012-04-12T08:01:41Z

You want stackoverflow.com

Comment by Ed Dean

2012-04-04T04:19:14Z

mathoverflow.net/questions/83298/…

Comment by Ed Dean

2012-04-03T16:42:48Z

Unless I'm missing something, it follows immediately from the setup/definitions that $T\leq m$ if and only if $L\ge l$. Indeed, the text of your question seems to take it for granted that each of these just gives a different description for the event "we win."

Comment by Ed Dean

2012-03-28T13:57:50Z

Perhaps the question's assertion that projective sets are all universally measurable and have the PSP means that Detelin wants to assume projective determinacy.