Start a new discussion

Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

Site Tag Cloud

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

• CommentRowNumber1.
• CommentAuthorTodd_Trimble
• CommentTimeMay 12th 2014

I added a proposition to this subsection which seems valid intuitionistically, but I wouldn’t mind a reality check from someone.

• CommentRowNumber2.
• CommentAuthorMike Shulman
• CommentTimeMay 12th 2014

Should the definition of $U$ involve $x\notin A$ rather than $x\notin U$? And should the $Y$ in the last line be a $U$?

• CommentRowNumber3.
• CommentAuthorTodd_Trimble
• CommentTimeMay 12th 2014

Thanks, Mike! Good catches; I corrected both.

• CommentRowNumber4.
• CommentAuthorMike Shulman
• CommentTimeMay 12th 2014

Ok, now it looks good to me. Nice!

• CommentRowNumber5.
• CommentAuthorTodd_Trimble
• CommentTimeMay 13th 2014

Thanks again, Mike. I confess that I’m having some trouble seeing the assertion that “constructively” (I guess this means intuitionistically?) a set is well-founded if it is classically well-founded. My guess is that Toby wrote that sentence, so maybe he can help me out.

Suppose $\prec$ is a classically well-ordered relation on a set $X$. (I think I’m back to my old conundrum of “what does the nLab really mean by ’set’?”. I think it would be better to ask: what does the nLab think is meant by a category of sets? Basically I was hoping that the assertion would generalize so as to be valid for classically well-ordered relations in a topos.) Let $U$ be an inductive subset of $X$. I can prove intuitionistically that its complement $\neg U$ is not inhabited, which I am told is exactly synonymous with $\neg U$ being empty. (I actually have to think about that one as well.) But I don’t see how to conclude that $U$ is the entirety of $X$, intuitionistically.

• CommentRowNumber6.
• CommentAuthorTodd_Trimble
• CommentTimeMay 13th 2014

Re #5: oh, I think I see. Merely by assuming classical well-foundedness, classical logic is forced upon us. That must be the point (and in fact that point is made in the article).

• CommentRowNumber7.
• CommentAuthorMike Shulman
• CommentTimeMay 13th 2014

There seems to be a little something missing though; the article says that as soon as an inhabited relation is classically well-founded we have LEM, but how do we know that $\prec$ is inhabited?

• CommentRowNumber8.
• CommentAuthorTodd_Trimble
• CommentTimeMay 14th 2014
• (edited May 14th 2014)

There might be more information on this in the Elephant, D4.5.13 according to choice object (I don’t have access to this currently). It’s noted at that article that excluded middle is equivalent to the assertion that the 2-element set is classically well-orderable.

• CommentRowNumber9.
• CommentAuthorZhen Lin
• CommentTimeMay 14th 2014

The proof is straightforward enough – one forms a subset whose minimal member depends on the proposition you want to decide, and then one uses decidability of equality to decide everything. See here.

• CommentRowNumber10.
• CommentAuthorDavidRoberts
• CommentTimeMay 14th 2014

Nice of you to provide a Coq proof.

• CommentRowNumber11.
• CommentAuthorTodd_Trimble
• CommentTimeMay 14th 2014

Re #7: yes, it looks to me there’s a little bit missing. If we assume excluded middle in the meta-background, so that externally speaking every relation on a type is either inhabited or empty, then any classically well-ordered relation on an inhabited type $X$ is either inhabited or empty. If it is empty, then we argue it is well-founded (in the inductive sense) by vacuity, or if it is inhabited, then we can follow Zhen’s line of argument (thanks, Zhen!). But do we feel that meta-assumption is kosher? Or maybe there’s another way to argue?

• CommentRowNumber12.
• CommentAuthorMike Shulman
• CommentTimeMay 15th 2014

I don’t understand where meta-ness comes in, can you explain again?

• CommentRowNumber13.
• CommentAuthorTodd_Trimble
• CommentTimeMay 15th 2014

If the background logic is classical, then for any property $P$ we might assert of an object $x$ of a topos (say), we have $P(x) \vee \neg P(x)$. Here I was taking $P$ to be the property of being inhabited.

• CommentRowNumber14.
• CommentAuthorMike Shulman
• CommentTimeMay 15th 2014

But if the question is whether “any classically well-ordered relation is well-ordered” is true constructively, it seems that the quantifier “any classically well-ordered relation…”, being part of that statement, should be interpreted in the same (constructive) logic in question, not the meta-logic (classical or not).

• CommentRowNumber15.
• CommentAuthorTodd_Trimble
• CommentTimeMay 15th 2014

Thanks for your reaction, Mike. But we might be talking past one another here.

Let me try a different tack. You raised the question in #7, what if the (classically well-ordered) relation were not inhabited? Can we still prove it is well-ordered, constructively? That’s the question I’d like to focus on right now (and I thought that’s what you were driving at as well). My comment in #11 was an attempt to patch together some type of response to that, but I’m happy to put it aside so long as we can satisfactorily answer the question I’m putting out there now.

• CommentRowNumber16.
• CommentAuthorMike Shulman
• CommentTimeMay 15th 2014

Well, if it’s not inhabited, then that means that we never have $x\prec y$ for any $x,y$. (I presume that the meaning of “the relation is inhabited” is that the relation itself is inhabited, not that its carrier set is inhabited.) Therefore, any inductive subset must contain every $x$, since it contains all the $y$ such that $y\prec x$ (of which there are none). So the relation is well-founded. Maybe this is what you meant by “by vacuity”. But the point I was making in #7 is that constructively, we can’t say that every relation is either inhabited or not inhabited. (That’s why I didn’t phrase the question as “what if the relation were not inhabited?”)

• CommentRowNumber17.
• CommentAuthorTodd_Trimble
• CommentTimeMay 15th 2014

Yes, you’re absolutely right that I phrased #15 inaccurately, and yes, you just recalled the argument I had in mind, i.e., what I meant by “vacuity”. I think we agree on what the issue is, and presently I don’t have a good answer for it.

The statement “every relation is inhabited or not” can be interpreted internally (e.g., for a fixed object $X$ we can write down “every relation on $X$ is inhabited or not” as a proposition in the internal language). Or, there is an external statement “every object in a topos is inhabited or not”, and I was proposing in #11 that if one accepts LEM in the meta-logic, then of course that statement is true, and we’d be set. (And usually, I personally do accept LEM when reasoning at the meta-level.) But I gather you feel that would be a less than satisfactory response, and I can understand that.

• CommentRowNumber18.
• CommentAuthorMike Shulman
• CommentTimeMay 15th 2014

I’ve gathered that you always think of intuitionistic mathematics as the internal language of some topos. I think it’s good to try to get away from that and think of it as a kind of mathematics in its own right, which happens to be interpretable into any topos. And the universally quantified statement “every relation is inhabited or not” makes perfect sense in this intuitionistic mathematics, without needing to either pass to the meta-language or restrict to relations on a particular set. (It can also be interpreted into a topos, if you use stack semantics, but that’s not the point.)

• CommentRowNumber19.
• CommentAuthorTodd_Trimble
• CommentTimeMay 15th 2014

I’ve gathered that you always think of intuitionistic mathematics as the internal language of some topos.

No, that’s not an accurate description of what I think. Not at all.

I think it’s good to try to get away from that and think of it as a kind of mathematics in its own right, which happens to be interpretable into any topos.

In fact I do, and yes certainly. I’m quite happy working in intuitionistic mathematics or in classical mathematics, depending on the context. I actually don’t take a dogmatic stand, but when reasoning around other mathematicians, I’m usually happy to adopt classical first-order logic as a default for reasoning at the meta-level if that is an agreed-upon standard for discussion.

But somehow this discussion seems to be taking a philosophic turn? Right now I’m more concerned with finding a proof of something, or getting straight on the contents of the article.

(That said, I don’t see any philosophic problem in saying something like “every well-pointed topos is Boolean” (Mac Lane and Moerdijk, proposition VI.7) – provided we allow excluded middle in the metalogic. If we don’t allow that, well then, that’s no longer a theorem.)

And the universally quantified statement “every relation is inhabited or not” makes perfect sense in this intuitionistic mathematics…

It makes sense, but it’s not accepted as true in intuitionistic mathematics. (And hey, if that’s the mathematics we agree to have a conversation in, I have no problem with that, but I do want to be clear on the matter.)

• CommentRowNumber20.
• CommentAuthorMike Shulman
• CommentTimeMay 16th 2014

I’m very sorry; we really do seem to be talking past each other. I must have misinterpreted what you meant in #11 and #18. You’re right, we should focus on just being clear about what we have a proof of. It sounds like we can prove the following constructively:

• If any inhabited relation is classically-well-founded, then LEM.
• Any inhabited, classically-well-founded relation is well-founded (by way of first proving LEM).
• Any empty relation is well-founded.

Now what exactly is it that we can prove with a classical metatheory? I’m not actually sure I believe that “externally speaking every relation on a type is either inhabited or empty”. The internal meaning of “inhabited” in a topos (for instance) is that the map to 1 is epi, while the internal meaning of “empty” is that it’s isomorphic to 0 — but even in a classical metatheory it’s not true that every object of a topos has one of these properties. On the other hand, the external meaning of “inhabited” is that it admits a map from 1, while the external meaning of “empty” is that it doesn’t admit such a map — but while it’s certainly true in a classical metatheory that every object of a topos has one of these properties, I don’t see how that kind of “emptiness” suffices for the argument by vacuity.

• CommentRowNumber21.
• CommentAuthorTodd_Trimble
• CommentTimeMay 16th 2014

(This is after having drunk some single malt scotch a little while ago; hopefully some of it will be sensible.)

I’m very sorry; we really do seem to be talking past each other. I must have misinterpreted what you meant in #11 and #18.

No worries whatsoever. I was aware that I wasn’t expressing myself as articulately as I should have.

Now what exactly is it that we can prove with a classical metatheory? I’m not actually sure I believe that “externally speaking every relation on a type is either inhabited or empty”. The internal meaning of “inhabited” in a topos (for instance) is that the map to 1 is epi, while the internal meaning of “empty” is that it’s isomorphic to $0$

I actually completely agree with this. First, I agree with these meanings of ’inhabited’ and of ’empty’ (and therefore I think some stuff should be added to inhabited set). This “not inhabited = empty” assertion which was stated in inhabited set obviously holds not in the general topos setting but in some more specific setting; when I was muttering incoherently in #5 about the conundrum of what the nLab means by ’set’, it was really against the backdrop of understanding the exact context of this specific assertion. I.e., there must be some underlying assumptions about what is meant by $Set$ which I’m not fully clear on, possibly including a well-pointedness assumption, projectivity of $1$, and maybe a few others. (By the way, when I said ’type’ earlier, I meant 0-type, but maybe you understood that.)

The same issues might also play into what we’re discussing now, so for me it’s worthwhile to have this discussion.

Your analysis of what we can prove constructively so far seems spot on.

FWIW: for my own benefit I’m writing up (or have already written up at home) a proof that given an inhabited classically well-founded relation in a topos, the topos must be Boolean. (Perhaps Johnstone covers this?) This might be very easy to see using stack semantics, but for now I’m using just good old-fashioned topos-theoretic reasoning. Not that you need it, but I might make it more public soon.

• CommentRowNumber22.
• CommentAuthorMike Shulman
• CommentTimeMay 16th 2014

I had a discussion with Toby a while ago about the meaning of “inhabited” in a topos. It appears to still be present at the bottom of inhabited object. I think I still agree with the conclusions there, that in a general topos one should talk about “internally inhabited” or “externally inhabited”, whereas for a well-pointed topos the two agree, and when talking about sets one should by definition be in the context of a well-pointed topos (such as, for instance, the internal language of an arbitrary topos). But in any case, inhabited set could probably use some clarification.

• CommentRowNumber23.
• CommentAuthorMike Shulman
• CommentTimeMay 16th 2014

Re FWIW: I just glanced through the section in the Elephant about AC, and I didn’t see anything about this. I think it will be worthwhile to have such a proof recorded.

• CommentRowNumber24.
• CommentAuthorMike Shulman
• CommentTimeMay 16th 2014

Hmm, how about this for a sneaky trick? Suppose $(A,\prec)$ is classically well-founded; we want to show it is well-founded. So let $U\subseteq A$ be inductive, and let $a\in A$; we want to show $a\in U$. Since $U$ is inductive, it suffices to show that every $b\prec a$ is in $U$, i.e. we may assume given a $b$ such that $b\prec a$ and show $b\in U$. But now $\prec$ is inhabited, so LEM holds; therefore $(A,\prec)$ is well-founded by the previous argument, and so $U=A$ and thus $b\in U$.

• CommentRowNumber25.
• CommentAuthorTodd_Trimble
• CommentTimeMay 16th 2014

Well, I’m not seeing anything wrong with it, but it is indeed tricky! I can’t recall seeing this trick before. It reminds me vaguely (but only vaguely) of the inductive proof that all pigs are yellow. :-)

• CommentRowNumber26.
• CommentAuthorMike Shulman
• CommentTimeMay 16th 2014

To me it has a sort of call/cc feel, kind of like the constructive proof that $\neg\neg(P\vee\neg P)$.

• CommentRowNumber27.
• CommentAuthorTodd_Trimble
• CommentTimeMay 16th 2014

Re #23: I wrote up a proof of the topos-theoretic statement alluded to at the end of #21, which can be found here. It’s just a slightly more elaborate form of what Zhen wrote up at math.SE (see #9).

• CommentRowNumber28.
• CommentAuthorTodd_Trimble
• CommentTimeMay 16th 2014

And now I’ve expanded well-founded relation to take into account the fruits of this discussion. (Thanks again, Mike.)

• CommentRowNumber29.
• CommentAuthorMike Shulman
• CommentTimeMay 16th 2014

very nice; thanks!

• CommentRowNumber30.
• CommentAuthorTodd_Trimble
• CommentTimeMay 16th 2014

Finally, I added a little to inhabited set.

Thinking a little about some of the relevant issues, I feel as if maybe there should be some declared default assumptions about the category $Set$ for nLab purposes, that should be considered as in effect unless one specifies otherwise. (Well, this would probably help me anyway, as I’ve frequently been confused what it is we’re assuming or not assuming whenever we speak of $Set$ or sets in some random nLab article. The article set I haven’t found particularly helpful in this regard, although I might be missing something.)

Some core assumptions might include those stated at well-pointed topos, including projectivity and indecomposability of $1$. Possibly also up for consideration are relatively mild choice principles such as the presentation axiom (is that considered a choice principle? I sort of want to consider it one). Any thoughts on this?

• CommentRowNumber31.
• CommentAuthorDavidRoberts
• CommentTimeMay 17th 2014

I for one think of presentation axiom as a choice principle.

• CommentRowNumber32.
• CommentAuthorMike Shulman
• CommentTimeMay 19th 2014

Presentation is definitely a choice principle. I don’t think it should be included in any “default” core of axioms that’s intended to be constructive. It might not be a bad idea to state a default collection of assumptions about sets somewhere. Or perhaps several default collections, depending on whether the context is “classical”, “constructive”, “predicative”, etc.? E.g. something like “classical” means ETCS+R, “constructive” means a (constructively) well-pointed topos, “predicative” means a well-pointed $\Pi W$-pretopos. I do think we should emphasize that this doesn’t mean proofs need to be phrased in “arrow-theoretic” language; the whole point of well-pointedness is that you can treat sets as “things with elements” in the usual way.

• CommentRowNumber33.
• CommentAuthorMike Shulman
• CommentTimeMay 19th 2014

You’re right that set is not very helpful, since it mostly discusses “definitional set theories” according to which sets are defined in terms of some other objects. Maybe it could have two sections, one explaining the default axioms/properties that we assume of sets on the nLab, and another explaining how such notions of “set” arise in foundational theories that don’t assert them axiomatically?

• CommentRowNumber34.
• CommentAuthorTobyBartels
• CommentTimeMay 21st 2014

Default assumptions about $Set$ should probably be at Set rather than at set. (Or at foundations or some place like that.)

FWIW, my default assumptions about $Set$ are that it's a well-pointed Grothendieck topos, that is a well-pointed category satisfying Giraud's axioms. Of course, this is circular, since Giraud's axioms discuss ‘small’ coproducts, but really the point is the other axioms. And you have to be careful how you state those; sometimes people list the existence of small colimits among these axioms, but I wouldn't (and so the list in the nLab doesn't). You also have to be careful how you define well-pointedness, which is something that Mike and I worked out before (and is also in the Lab in the constructivist section); many famous consequences of this condition require excluded middle, and only the right ones (projectivity of $1$, for example, but not booleanness, for example) go into this definition.

As for Giraud's axioms, some important properties of $Set$ follow directly from these, principally the existence of quotient sets. (Thus notions of ‘set’ or ‘type’ that lack these, such as the types in straight Martin-Löf type theory, are not good enough.) Other properties, such as the existence of arbitrary small (or even finite) colimits, $W$-types (or even a natural numbers object), exponentials, and a subobject classifier, only follow (via the circular axiom about small coproducts) if you already believe in these things in your meta-logic. (The same goes for booleanness, as discussed above about well-pointedness.) So it's up to you whether or not you believe in them; my default assumptions allow for strict finitism and strict predicativism (as well as constructivism, of course).

• CommentRowNumber35.
• CommentAuthorTodd_Trimble
• CommentTimeMay 26th 2014

I forgot to thank you, Toby, for your last comment. These look like eminently reasonable assumptions to me: they are both flexible and principled. I think it might be a good idea to work those into the article Set more formally, as declared default assumptions for our use around the nLab (as many of the relevant articles bear your authorship, this could be helpful).

• CommentRowNumber36.
• CommentAuthorMike Shulman
• CommentTimeMay 29th 2014

I’m confused. How are such circular assumptions helpful? And what does it mean to believe in (say) a subobject classifier “in the meta-logic”?

• CommentRowNumber37.
• CommentAuthorTobyBartels
• CommentTimeMay 30th 2014

In a higher-order logic, we might have a type (a $0$-type) of truth values. It's a category error to call that a subobject classifier in the metalogic; but a coproduct indexed by it of the terminal object in $Set$ is a subobject classifier in $Set$.

There is only one well-pointed Grothendieck topos (up to a geometric isomorphism which is unique up to a unique natural isomorphism), which I denote $Set$. Accordingly, every property of $Set$ follows from its characterization as a well-pointed Grothendieck topos. Most of this is circular and therefore uninteresting. It is simply noted.

But some of this is not circular. I think that this amounts to saying that $Set$ is a Heyting pretopos, but you can probably pick this apart.

• CommentRowNumber38.
• CommentAuthorMike Shulman
• CommentTimeMay 30th 2014

I feel like there is a size problem. If the metalogic is a HOL like the internal language of a topos, then formulating an object theory such as that of a Heyting pretopos in that logic will be like describing an internal category in that topos. But an internal category can’t reasonably be expected to have coproducts indexed by all objects of the ambient category — it happens occasionally, such as in the effective topos, but that’s a very special situation and you have to be very careful there to even make sense of it.

There is only one well-pointed Grothendieck topos

I don’t think that’s true constructively, even with the constructive definition of “well-pointed”.

• CommentRowNumber39.
• CommentAuthorTobyBartels
• CommentTimeMay 31st 2014

an internal category can’t reasonably be expected to have coproducts indexed by all objects of the ambient category

But the ambient category thinks that it does.

Let's try to make this precise. We're working in a Lawvere–Tierney topos (so it has a subobject classifier), we define a well-pointed Grothendieck topos internal to that. This is defined to satisfy Girard's axioms, which say nothing about a subobject classifier, so it may not be (internally) a Lawvere–Tierney topos. But we should be able to prove that it is, using the subobject classifier in the ambient category.

But I realize now that I never did finish learning how to properly describe a large category internal to a topos, which is what we want here. Aren't we supposed to do treat it as an indexed category?

There is only one well-pointed Grothendieck topos

I don’t think that’s true constructively, even with the constructive definition of “well-pointed”.

Do you remember what goes wrong?

• CommentRowNumber40.
• CommentAuthorMike Shulman
• CommentTimeJun 1st 2014

Yes, large categories “relative to” a topos are categories indexed over that topos. But I don’t think they should be called “internal” because “internal category” has a standard meaning that’s different. The latter is the sort of internal category that I meant in 38, and I still believe that that’s what you would have to mean if you mean “metalogic” in the usual sense: if a theory $T$ is formulated in some metatheory $T'$, then a model of $T$ is an object of $T'$ (with structure), but categories indexed over a topos $E$ are not objects in the theory of $E$. If a theory $T$ has a model that’s an $E$-indexed category, then the metalogic isn’t $E$ but rather some “2-categorical logic” of $E$-indexed categories — and we can’t expect an $E$-indexed category to have all coproducts indexed by objects of that theory (even to the eyes of that theory). In the 2-categorical logic of $E$-indexed categories, $E$ itself is a sort of “universe of small sets” like in algebraic set theory.

Do you remember what goes wrong?

It’s been a while since I thought about this, but I think the point is that constructively, $Set$ can have nontrivial proper subtoposes, such as $Set/U$ for a truth value $U$, and if $U$ is chosen appropriately such a subtopos can be well-pointed.

• CommentRowNumber41.
• CommentAuthorTobyBartels
• CommentTimeJun 2nd 2014

If a theory $T$ has a model that’s an $E$-indexed category, then the metalogic isn’t $E$ but rather some “2-categorical logic” of $E$-indexed categories — and we can’t expect an $E$-indexed category to have all coproducts indexed by objects of that theory (even to the eyes of that theory). In the 2-categorical logic of $E$-indexed categories, $E$ itself is a sort of “universe of small sets” like in algebraic set theory.

Well, I want the model to be have all small coproducts, that is all coproducts indexed by $E$.

and if $U$ is chosen appropriately such a subtopos can be well-pointed.

H'm, this is striking a bell somewhere in my brain.

• CommentRowNumber42.
• CommentAuthorMike Shulman
• CommentTimeJun 3rd 2014

Okay, this is making a little more sense to me now. We’re assuming a metatheory that has some notion of “small”, such as the “categories of classes” used in algebraic set theory, or a “2-category of large categories” with a discrete opfibration classifier. Then the statement is that $Set$ is a (large) category in this metatheory which is well-pointed, has “small” coproducts, and satisfies the rest of Giraud’s axioms. Then I’ll believe that if the metatheory has a small subobject classifer in an appropriate sense, it follows that $Set$ has a subobject classifier, etc.

However, the constructive non-uniqueness of well-pointed Grothendieck topoi makes me somewhat wary of taking this as our “default assumptions” about $Set$. I found a note that I wrote to myself a while ago claiming that if $E$ is the Sierpinski topos and $U$ the interesting subterminal therein, that “$E/U$ is well-pointed” is true in the stack semantics of $E$. I haven’t tried to re-verify that right now.

• CommentRowNumber43.
• CommentAuthorTobyBartels
• CommentTimeJun 4th 2014

I suppose that we could talk about the terminal Grothendieck topos.

• CommentRowNumber44.
• CommentAuthorMike Shulman
• CommentTimeJun 4th 2014

Yeah, I think that would work. But it brings in a large quantification.

• CommentRowNumber45.
• CommentAuthorTobyBartels
• CommentTimeJun 4th 2014

Sometimes those can be avoided, but I don't see how in this case, not immediately.

• CommentRowNumber46.
• CommentAuthorMike Shulman
• CommentTimeJun 5th 2014

We might be able to show constructively that any well-pointed Grothendieck topos must be a subtopos of $Set$. If so, then at least if we have subobject classifiers, it must be classified by a LT operator on $Set$, of which there are only a small number.

• CommentRowNumber47.
• CommentAuthorDaniil
• CommentTimeApr 5th 2017

I didn’t fully understand all the details the Todd Trimble’s proof that classical well-foundedness implies LEM, but I figured there is a purely logical proof which is basically Zhen Lin’s proof. Assume that R is inhabited: R(y,x) holds; and R is classically well-founded, then consider the set P = { x } ∪ { a | R(a, x) & Q }. It is inhabited and thus have a minimal element x_0. If x_0 = x then Q does not hold: for if it does, then y<x and hence x is not a minimal element. If x_0 =/= x, then Q must hold.

I have formalised this proof and some of the others in Coq, if it is of interest to someone: https://gist.github.com/co-dan/887fb4dbe4cc2f51be868e4a27721b97

• CommentRowNumber48.
• CommentAuthorTobyBartels
• CommentTimeApr 5th 2017

I'd avoid the phrasing ‘if $x_0 \ne x$’; it should be ‘if $R(x_0,x) \:\&\: Q$’. Your phrasing makes it appear that you’re using LEM, assuming that $x_0 = x$ or $x_0 \ne x$. What we actually have is that $x_0 \in \{x\}$ or $x_0 \in \{a \;|\; R(a,x) \:\&\: Q\}$, or equivalently that $x_0 = x$ or $R(x_0,x) \:\&\: Q$. (OK, $x_0 \ne x$ does follow from $R(a,x) \:\&\: Q$, but what matters is that $Q$ follows, so it's misleading to bring in that $x_0 \ne x$.)

Anyway, I agree with the proof. Combined with Mike's trick from #24, this proves that any classically well-founded relation is (constructively) well-founded.

• CommentRowNumber49.
• CommentAuthorMike Shulman
• CommentTimeApr 6th 2017

Yes, this seems to work and is simpler than Todd’s proof. Thanks! Would you like to record this on the page well-founded relation?

• CommentRowNumber50.
• CommentAuthorDaniil
• CommentTimeApr 7th 2017

I have updated the page with the proof.

• CommentRowNumber51.
• CommentAuthorMike Shulman
• CommentTimeApr 7th 2017

Great, thanks!

• CommentRowNumber52.
• CommentAuthorTodd_Trimble
• CommentTimeAug 10th 2018

Added the proof of uniqueness of simulations from a well-founded coalgebra to a weakly extensional coalgebra.

• CommentRowNumber53.
• CommentAuthorAli Caglayan
• CommentTimeDec 2nd 2018

Any good references for well-founded relations?

• CommentRowNumber54.
• CommentAuthorMike Shulman
• CommentTimeDec 3rd 2018

Classically or constructively? Classically, there is probably an embarrassment of riches; probably most books on set theory will discuss them to some extent. Constructively, some references that pop into my (totally biased) mind are Paul Taylor’s book PFM and his paper Intuitionistic sets and ordinals, the HoTT Book chapter 10, and section 8 of this paper of mine.

• CommentRowNumber55.
• CommentAuthorAli Caglayan
• CommentTimeDec 3rd 2018
• (edited Dec 3rd 2018)

Can you prove well-founded induction from your definition of well-foundedness, without LEM? Every proof I’ve found has used LEM.

• CommentRowNumber56.
• CommentAuthorMike Shulman
• CommentTimeDec 3rd 2018

Which definition are you talking about? The ones in the constructive references I cited are essentially the same as the one at well-founded relation, which basically asserts well-founded induction by definition.

• CommentRowNumber57.
• CommentAuthorAli Caglayan
• CommentTimeDec 4th 2018
• (edited Dec 4th 2018)

If we have some property $P$ of all $x \in X$ how can we show the following:

$\forall x \in X, P(x) \iff \forall x \in X, ((\forall y \prec x, P(y)) \Rightarrow P(x))$

Which is the statement for well-founded induction in classical logic. I am not following how this follows from the definitions.

Clearly showing one way is trivial, but the the converse… all proofs I have seen do this by contradiction. Suppose some $x$ such that $\neg P(X)$, then constructing the set $\{ x \in X \mid \neg P(x)\}$ which is well founded, hence has a $\prec$-minimal element eventually leading to a contradiction.

• CommentRowNumber58.
• CommentAuthorUlrik
• CommentTimeDec 4th 2018

See Prop. 1.4 in Paul Taylor’s Intuitionistic Sets and Ordinals, also mentioned in #54, and the UniMath formalization by Peter Lumsdaine.

• CommentRowNumber59.
• CommentAuthormbid
• CommentTimeDec 4th 2018

@57 Alizter: Doesn’t it follow from the right-hand side of your equivalence that $\{x \in X \mid P(x) \}$ is (in the terminology of the nlab article) ≺-inductive? If $X$ is well-founded, then this set has to be equal to $X$ (by definition of well-foundedness on the nlab), hence your left-hand side.

I think you might currently be using the “every inhabited subset has a minimal element” definition of well-foundedness. This is constructively not equivalent to the definition on the nlab. For example, consider the set $\{n \in \mathbb{N} \mid n = 1 \, \text{ or } \, n = 0 \, \text{ and the continuum hypothesis is true} \}$. Then constructively finding a minimal element of this set (wrt. to the usual order on $\mathbb{N}$) is equivalent to proving or disproving the continuum hypothesis and hence impossible. However, $\mathbb{N}$ is well-founded as defined on the nlab (“every <-inductive subset of $\mathbb{N}$ is equal to $\mathbb{N}$”).

• CommentRowNumber60.
• CommentAuthorAli Caglayan
• CommentTimeDec 4th 2018
• (edited Dec 4th 2018)

Re 59. I should have probably made it clearer that I was giving the classical proof of well-founded induction using the classical definitions.

The classical definition of well-founded relation on a set is exactly what one needs in order to prove well-founded induction. The proof for this requires LEM and not to mention the non-constructivity when talking about minimal elements.

I see this intuitionistic definition and it avoids talking about minimal elements, so I wonder how can it be used to prove well-founded induction?

• CommentRowNumber61.
• CommentAuthorMike Shulman
• CommentTimeDec 4th 2018

As I said, the intuitionistic definition is exactly written so as to imply well-founded induction. As mbid said, given $P$ such that $\forall x \in X, ((\forall y \prec x, P(y)) \Rightarrow P(x))$, let $A = \{x\in X \mid P(x)\}$. Then $A$ is $\prec$-inductive; that’s precisely what the assumption about $P$ says. Therefore, by the definition of well-foundedness, $A=X$, which is to say $\forall x\in X, P(x)$.

• CommentRowNumber62.
• CommentAuthorAli Caglayan
• CommentTimeDec 6th 2018

OK my confusion was coming from the definitons I was using. I originally had Mike’s paper’s definitions in mind, not the nlab article. But now reading the nlab article it makes more sense.

• CommentRowNumber63.
• CommentAuthorMike Shulman
• CommentTimeDec 6th 2018

The definition in my paper is the same as the one on the nLab.