Talk:Injective function/Archive 1

Archive 1

Inverses and intuitionism

Hello, User:Chinju has added a statement about absence of inverses for injectives in intuitionistic systems. By {0,1}, do you mean the open interval (0,1)? Also, do you have a handy reference for this? Thanks Sam Staton (talk) 07:47, 23 May 2008 (UTC)

I don't have a reference, but constructivist analysis might be a better link than intuitionistic logic. I think Chinju meant the two-point set {0,1}, though what's written applies equally well to (0,1). Algebraist 13:52, 26 May 2008 (UTC)

Thanks (I had misread the sentence). I understand this has to do with indecomposability, as now linked; correct me if I'm wrong. Sam Staton (talk) 15:52, 27 May 2008 (UTC)

I don't know that this is such an important point to include here; intuitionism is an extreme minority view within mathematics, and we don't want to discuss it in every mathematics article as if it is a common viewpoint. That is: the mathematics community has soundly rejected intuitionism over the last 50 years, so we don't want to give a biased picture of contemporary mathematics by discussion intuitionism at every possible point. It is difficult to find a mathematics text that mentions intuitionism at all, apart from texts specifically about it and texts in proof theory. I don't think any generic undergraduate analysis text that covers inverse functions even mentions intuitionism.

Finding the right balance (how often to mention these minority views) is somewhat difficult. I will try to pare down what is here without completely removing it; the article on intuitionism can discuss these things in more detail. I think this article is likely of interest to particularly young readers, so giving everything due weight is important. — Carl (CBM · talk) 16:49, 27 May 2008 (UTC)

Hi Carl, I agree that it is important to get the right balance, and that it's tricky. I think your footnote is appropriate. But I re-added the text "in conventional mathematics" as an aside, in brackets. I don't think this adds undue weight to constructivism.

It might be inappropriate to mention constructivism in every wikipedia article, but this article is a topic in discrete mathematics and set theory, and I think it is appropriate to mention at this stage that the foundations might be questioned. For instance, when teaching, I often find that students find non-constructive principles harder to understand, and it is sometimes nice to tell the keen ones that these principles are debatable. I don't think it's fair to say that "the mathematics community has soundly rejected intuitionism over the last 50 years", since various related topics are still active research areas. Note also that many computer scientists do accept constructivism, and that injective functions and discrete maths are also a part of every undergraduate computer science course (though explicit constructivism admittedly isn't). Sam Staton (talk) 10:14, 29 May 2008 (UTC)

My research is in proof theory and computability theory, so I have spent some time learning and working with intuitionistic systems. While it is true that there is active research in constructive mathematics within mathematical logic, that's not because the principles of ordinary mathematics are being debated. The main contemporary motivations for studying intuitionistic systems are (1) they are interesting on their own, and (2) properties of intuitionistic systems can be used to obtain results about classical systems.

Outside of mathematical logic, it appears to me that the community of constructive mathematicians is on the same scale as the community of ultrafinitists, and both are very small minorities within the broader mathematics community. This is reflected in the complete lack of coverage of either intuitionism or finitism in standard undergraduate mathematics texts. I don't know the CS community well enough to know how many of them might espouse some sort of constructivism or finitism, but I haven't seen those philosophies discussed in the few computer science texts I have seen.

We would do a disservice to readers (especially students) if we gave them the impression that there is some sort of active debate within the mathematics or mathematical logic community about the validity of classical mathematics. So I don't think the "in conventional mathematics" disclaimer should be included here. The entire article (apart from the footnote) is about conventional mathematics, as are virtually all other math articles on WP. I think the footnote is reasonable, though, as a pointer for those who want to learn more. — Carl (CBM · talk) 10:51, 29 May 2008 (UTC)

Hi Carl. I agree it would be wrong if readers got the idea that there was some kind of large guerrilla group trying to rise up against conventional mathematics. (Though there is some active debate about the validity of classical mathematics, I admit it is not within the general mathematics community.)

I'd like to add a third item to your list, though: (3) constructive proofs are often more informative than non-constructive ones. I've just been in our library here, and all the "discrete maths" textbooks I looked in discuss constructivism (Rosen, Ross & Wright, Huth & Ryan, not to mention Paulson, Forster, Taylor). So I think it is quite normal to let students know about this. All the books go further, suggesting that it is best to write constructive proofs where possible. I think that many students are thus aware that there is something better about constructive proofs, and I think those people will be interested to know when something as basic as inverting an injection is non-constructive.

I'm not sure whether the footnote alone is enough. My concern is that footnotes are usually used to clarify unclear sentences, whereas the sentence, without the "(in conventional mathematics)", is not unclear. Sam Staton (talk) 18:09, 29 May 2008 (UTC)

Are you convinced those textbooks are actually discussing mathematical constructivism (e.g. intuitionism) and not just a vague sense that some classical proofs are "constructive" and others aren't? — Carl (CBM · talk) 17:10, 9 June 2008 (UTC)

Sorry to show up so late to this discussion; in response to the first (already answered) question, yes, I had been talking about the two point set, and indecomposability is exactly the right thing to link to. As for the more ongoing debate, I agree with Carl's concern about the infeasibility of discussing constructive logic (or other well-known but "non-standard" systems of math/logic) differences in every mathematics article, but in this particular case, it struck me as a reasonable thing to point out, not because I want to (falsely) suggest that there is some very large controversy over the use of classical systems, but simply to present interesting and illustrative illumination of the concept under discussion (injective functions) as viewed from other, not necessarily competing, perspectives. I had actually been a bit uncomfortable myself with giving my own parenthetical injection of intuitionistic logic so much prominence but couldn't figure out how to present it better; however, I think the current solution, with the parenthetical qualifier of "conventional mathematics" and then the footnote explaining the constructive difference, is pretty good. -Chinju (talk) 20:20, 3 June 2008 (UTC)

Though I don't know if it's fair to say that "This principle may fail in constructive mathematics, where the concepts of function and set are treated differently than in mainstream mathematics." In a sense they are treated differently, sure, but not generally due to any direct difference of definition, but only because of the inevitable effects of differences elsewhere in the system. That is, in such systems as I have in mind, a set remains a collection of elements and a function remains a mapping between such sets (as given by a binary relation satisfying the appropriate properties of "totality" and "single-valuedness"). At this level, the concepts are treated no differently. The only problem is that some binary relations which could classically be proved to be "total", in the relevant sense, could no longer could be proved "total" constructively; but that's hardly a difference in the concepts of set and function, merely a difference in the strength of the logic (to prove certain things to actually be total functions). -Chinju (talk) 20:34, 3 June 2008 (UTC)

I agree, and I've simplified the footnote. Sam (talk) 15:39, 9 June 2008 (UTC)

I don't agree. The counterexample given in the footnote is extremely subtle, as it permits the inclusion "function" f from the "set" {0,1} into the real numbers, but denies the existence of the same "function" when {0,1} is viewed as a subset of the reals rather than as an independent set. From a classical viewpoint, this inclusion map f literally is its own inverse (f and f^-1 are the same set {{0,{0}},{1,{1}}}), so only a difference in the definitions of "set" and "function" could permit the "function" f to exist without the inverse of f existing simultaneously.

You may have intended to mean that the domain of f was the set of natural numbers {0,1}. In that case, the above argument doesn't hold, but a stronger one still does: a set, classically, is the collection of elements that satisfy a given property. The property "is either the image of 0 or the image of 1 under the map f" thus defines a set. In order to claim that the inverse of f doesn't exist, you would either have to claim its domain isn't a set (thus departing from the classical definition of sets) or that despite its domain existing, the function itself doesn't exist (departing from the classical definition of function, as even constructively it is possible to distinguish the real number 0 from the real number 1, as they are separated at nonzero distance). This is another facet of the subtlety of the issue.

My motivation in adding that explanatory text in the first place was to include some vague explanation, for a reader grounded only in classical math, telling why the classical principle in question may fail. I didn't want to get into so much detail in the footnote, though. Can you reword it to add some explanation? — Carl (CBM · talk) 17:10, 9 June 2008 (UTC)

Hi Carl, I'm having trouble with your comment. I don't think that the function f^-1 that you mention is total. (Sure, it is constructively true that every injection has a partial inverse.) Sam (talk) 17:24, 9 June 2008 (UTC)

I see. I am so used to thinking about functions without an explicitly given codomain that I missed the terminology here that the left inverse needs to be total on the original codomain. Of course that's impossible constructively, like the example shows. My last comment was under the impression that the footnote made a stronger claim.

I went back to see what was confusing me, and I'm going to change the wording slightly to prevent this happening to anyone else, by being more explicit that the left inverse is meant to be a retraction. — Carl (CBM · talk) 18:35, 9 June 2008 (UTC)

---

I've never heard the phrase "information-preserving function", and a Google search confirms that the phrase is extremely rare. The claim that injective functions are sometimes called information-preserving may be technically true, but it is very misleading. Listing the phrase before "one-to-one function" (a very common phrase) is simply absurd. 204.77.35.12 (talk) 16:58, 31 January 2009 (UTC)

I agree. I've removed the phrase from the intro now. 87.114.27.44 (talk) 21:52, 2 February 2009 (UTC)