Talk:Bijection

Huh?

I've heard that the set of rational numbers is supposed to be in one to one correspondence with the set of integers. How is this supposed to be? Isn't there an infinite number of rational numbers for each integer. (e.g. 1, ... 1.001, ... 1.1, ... 1.3145, ... etc. 2, ... 2.1, ... 2.2, ... 2.3, ... etc.)

The countable set page outlines a scheme for creating a 1-1 correspondence between ordered pairs of non-negative integers and the set of natural numbers, N. Essentially, this maps the ordered pair (m,n) as follows:

$(m,n)\rightarrow {\frac {m^{2}+2mn+n^{2}+3m+n+2}{2}}$

... which gives:

$(0,0)\rightarrow 1$

$(0,1)\rightarrow 2$

$(1,0)\rightarrow 3$

$(0,2)\rightarrow 4$

$(1,1)\rightarrow 5$

$(2,0)\rightarrow 6$

etc.

The scheme can be extended to map ordered pairs of integers (positive or negative) to N. You can also map the set of rational numbers Q to a subset of the set of ordered pairs of integers - the rational m/n maps to the ordered pair (m,n) where m and n are co-prime. Putting these two maps toghether gives you a 1-1 correspondence between Q and a sub-set of N. Gandalf61 09:00, 18 April 2006 (UTC)

Wow, it makes absolutely no sense, but it works. Weeeeird. Linguofreak 18:12, 20 April 2006 (UTC)

Right... the union of countably many countable sets is countable. For a decimal representation to be a rational number, it must either terminate or repeat, and it can be shown that for each integer, there are only countably many ways to write decimals after it that either terminate or repeat. So take the union of all those and it's countable. You may have to be careful about repeating 9's, but they don't really matter anyways. —Preceding unsigned comment added by 69.181.216.178 (talk) 23:05, 8 May 2009 (UTC)

Is this related to the diagonal proof? — Preceding unsigned comment added by 92.2.210.208 (talk) 20:01, 24 April 2013 (UTC)

total function

What about total functions? Either a bijective function is also a total function, or the page about total functions is wrong. I suppose it's the former. If so, that should be mentioned here at "Properties". I'd rather have someone write it who is not just supposing things like I am ;) —Preceding unsigned comment added by 80.238.227.222 (talk • contribs) 12:04, July 14, 2006

Unless one is discussion partial functions, every "function" is assumed to be total. Paul August ☎ 15:35, 14 July 2006 (UTC)

Still, for completeness, the difference between a partial and a total bijection should be explained. ClassA42 (talk) 22:21, 30 March 2008 (UTC)

I second ClassA42 - the article is not at all clear as to whether bijections are necessarily total. Wootery (talk) 15:10, 6 August 2014 (UTC)

Too technical

I've changed the lead so that it is no longer too technical for a novice reader (at least IMO), but I haven't really done anything with the rest of the article. Should I do more? Bill Cherowitzo (talk) 17:19, 26 October 2011 (UTC)

Wondering what other editors think about providing for the very novice reader a couple of examples that may be easily understood. What comes to mind is a planned classroom of 20 students and 20 student desks; the student arrive and each is to sit at a desk; there is one desk for each student. Joefaust (talk) 02:24, 30 October 2011 (UTC)

Ya some examples would be helpful for this page. As it stands it is still pretty technical.P0PP4B34R732 (talk) 03:01, 30 October 2011 (UTC)

Totally agree. It also should be made clear that the subject is more about function than something else. 109.206.156.72 (talk) 18:05, 13 October 2017 (UTC)

Baseball, anyone?

For the sake of readers who might not be familiar with baseball, perhaps another example should be given (instead or in addition). 188.169.229.30 (talk) 02:22, 24 November 2011 (UTC)

-Seconded :-) I agree, the baseball example was confusing for me as a "non-player" 88.104.128.57 (talk) 20:43, 4 February 2014 (UTC)

Adding an example using cricket (which, AFAIK, is a sport understood poorly in the few countries which even tolerate such nonsense) is probably the wrong direction... DrKC MD (talk) 03:54, 22 September 2023 (UTC)

Skirmish with diagram caption

There appears to be some disagreement about the caption on the composition diagram. Paul August is perfectly correct, the composition is a bijection. The anon editor may be thinking of this: if (g∘f) is a bijection, then (g∘f)^-1 is also a bijection and (g∘f)^-1 = f^-1∘g^-1, which would be a contradiction since g is not an injection, so its inverse is not even a function. The subtle fallacy here is that while (g∘f)^-1 = f^-1∘g^-1 holds for arbitrary relations, it only holds for functions if both f and g are bijections. The situation depicted in the diagram actually shows why this is so. Is this an important enough point to bring up in the article? If it is, I can use some help in finding a citation that discusses the failure of the formula when one or the other of the functions is not a bijection. (I have a number of sources for the proof of the formula, but none of them discusses the necessity of the conditions.) Bill Cherowitzo (talk) 04:24, 30 July 2013 (UTC)

Recent revert

This one.

• "exact pairing" is a concept from category theory, and should not be used unless you can provide a source establishing its general use for pedagogical purposes. Please do not invent terms.
• I have doubts that the article is too technical, especially giving that this is a technical topic. If you still think so, consider the following: Are there other resources that do the job, towards which the reader can be directed? We're not a textbook. Maybe something suitable is available at Wikibooks? Other sites that introduce the reader should exist, this is taught to kids, after all. Quote from the article: "This topic is a basic concept in set theory and can be found in any text which includes an introduction to set theory.". Finally, the possibility of writing an introductory article exists.
• For the benefit of other editors, please insert a statement at the beginning of the article to the effect that this article strives to be non-technical, as we've seen, that does not go without saying.

Paradoctor (talk) 14:06, 29 November 2013 (UTC)

Just a couple of comments. The fact that "exact pairing" is a technical concept from category theory is totally irrelevant to the inclusion of this phrase in this article. Anyone who knows this would not be looking at this page to start with. Your argument here is fallacious–you are saying that a mathematician can not use the word "onto", unless s/he is talking about a surjection, in normal discourse, because they are aware of the technical definition. You can place that argument onto the head of a pin, and sit on it! ;^) But seriously, this article was rewritten precisely because it was deemed too technical by a large number of readers (look at the reader's feedback when it was enabled). This is not a technical topic, it is, "taught to kids, after all", as you say. The question of what level to write an article at has been bouncing around the Math Wikiproject for some time. While I would hesitate to say that there is agreement on the issue, a good rule of thumb emerging from these discussions is to set the level, at least in the lead, at one level below where the topic would normally be taught in school. As the bijection concept is typically taught in a Precalculus course these days (if not before), I would say that the intro here should be geared toward high school sophomores. Your final point, about putting up "warning signs" about the article level (sometimes phrased as what are the prereqs for reading an article) has also been bandied about by project editors. I would say that there is even less agreement on this issue than on the appropriate level issue. One clear pitfall with this approach is that whatever is said about the article at the start will rarely be true by the end. Our articles should incorporate a graduated level of technicality, starting out in easily accessible language (appropriate to the topic) and building up to the more technical aspects later in the article. This of course is an ideal, the number of counterexamples to be found among the math articles is embarrassing huge, but we keep trying to improve them. Bill Cherowitzo (talk) 21:08, 29 November 2013 (UTC)

"category theory is totally irrelevant" Please note that my first reference to category theory was "used only in category theory". Instead of focusing on ancillary information, I'd prefer my concern about the non-use of the term in the relevant literature being adressed.

"you are saying that a mathematician can not use the word "onto"" ¿Que? Please quote and cite the edit where I say that, because my memory does not yield anything like that.

"taught to kids" That doesn't make it any less a technical topic, and I believe I mentioned that we're not a textbook. Whatever, not going to argue about this any further.

"warning signs" [...] "prereqs for reading" (my emphasis) If you back up a little, you'll note that I said "benefit of other editors". In case that should prove too much to ask, no problem. Sprinkle some HTML comments (e. g. <!-- No gobble-di-gook, or ELSE -->) across the sections, that would be entirely satisfactory. It would also have saved you the work of informing me about the larger history of this article. ;)

"we keep trying to improve them" Never doubted it, that's why we edit, after all. Paradoctor (talk) 00:16, 30 November 2013 (UTC)

image

When searching google for bijection the image accompanying the wiki text is "a bijection composed of an injection and a surjection" which may be misleading. An image of only a bijection would reduce confusion. If there is a way to enforce which image is grabbed by a google search this change would be good.

First of all, Wikipedia has no control over what Google does. Second, as this article clearly reads in the lead, a bijection is always both an injection and a surjection. What is so misleading?—Anita5192 (talk) 00:13, 22 July 2017 (UTC)

good job

this is one of the very very few math articles on wiki where the intro is at the right level almost all math articles, the intro is pitched way to high for a general encylopedia congrats to the authors/editors — Preceding unsigned comment added by 50.245.17.105 (talk) 19:14, 18 March 2021 (UTC)

Is the second sentence of this article correct?

I am not sure that the first sentence (correct one) and the second sentence are equivalent. Could someone correct either me or the page? 96.230.81.2 (talk) 15:56, 31 October 2023 (UTC)

 Fixed. You are correct; thanks. D.Lazard (talk) 16:17, 31 October 2023 (UTC)

Recent revisions

@Jacobolus: I appreciate your reworking the intro. I'm still unclear on exactly how the notation works that you added; that is, what it would express if spoken out loud. That's due in part to my unfamiliarity with the symbol $\mapsto$. (Well, now that I see the source, I understand "mapsto".) I assume these expressions are equivalent to something like, "the function X gives Y as a result". Not at all sure if that's correct, though, and I'm sure non-specialists like myself might not understand the precise meaning. This one, $2k-1\mapsto 2k,\,\ldots$, leaves me completely in the dark. I recognize, of course, that probably very few non-specialist people will seek out this article or subject. Nevertheless, I think improving its accessibility as we're doing is a good exercise in how to similarly improve other specialized articles that might cover more broadly recognized subject areas. So, I have a couple of more suggestions. I would replace the second sentence which contains the notations ("For example...") with the entire second paragraph ("Equivalently, a bijection is an invertible function...."), and move the notation examples lower. Whether using the mapsto symbol or another notation, it would sure help if at least one "spoken" example were given, along the lines of what I wrote above ("function X gives Y", or whatever expression is correct). In most of the article, the simple arrow is used, which I understand to have a different meaning than mapsto. So, maybe mapsto should not be used at all, or if it is used, needs to be defined/explained (briefly) in the text when it is first used. I still think the parenthetical linked "binary relation" could be removed from the first sentence, where I do not believe it is essential and serves primarily as an interruption, and placed lower in the intro, perhaps in a phrase like "also known as binary pairing". DonFB (talk) 06:52, 11 November 2023 (UTC)

Yeah, ordered pairs notation like $\{(1,2),(3,4),(5,6),\ldots \}$ is probably better, or maybe without the curly braces. Let's go back to that version. I moved and added some to the example but I'm not sure that's an improvement. The original idea was to have a very quick example near the top to give an impression of what is meant by "pairing", but if the example gets bigger it gets increasingly distracting. I don't think a "spoken example" would be helpful in the lead section. –jacobolus (t) 15:04, 11 November 2023 (UTC)

I tried putting "binary relation" as a wikilink on "pairing" but I'm not sure I like it; I think the parenthetical is better. It could be something like "pairing (formally a binary relation)", but making it longer makes this more distracting. The reason to include it is that "pairing" is not a well-defined technical term, and is plausibly ambiguous to people trying to figure out very precisely what a bijection is. Such people (e.g. undergraduates in a first pure mathematics course) are the primary audience of this page, even if it should also ideally be accessible to a broader audience and useful to a more advanced audience. –jacobolus (t) 15:28, 11 November 2023 (UTC)

I followed up by explicitly mentioning "binary relation" in the following "Definition" section. –jacobolus (t) 00:27, 12 November 2023 (UTC)

Add: As a matter of principle, I dislike parenthetical expressions in lede sections. If something is important enough to be in the lede—especially the first sentence—it should be expressed directly, rather than as an aside, or "stage whisper". Often, I believe, parentheticals are added by another (smarty pants) editor, not the editor who originally wrote the text. DonFB (talk) 13:41, 11 November 2023 (UTC)

I don't find your "often" to be reflective of my experience. Parentheticals are common in lead sections because there's a lot of information to cram in and it's hard to do so in a logically structured sentence. Throwing in a parenthetical makes it clear that the additional information is not part of the sentence proper, but is a kind of aside which doesn't break the remaining structure, without being hidden away as it would be in a footnote.

I think you should get over your impression about a stage whisper, which is rarely if ever reflective of Wikipedia authors' intent. –jacobolus (t) 15:31, 11 November 2023 (UTC)

Thanks for all your changes. The intro is far better and shows it's not necessary to cram a bunch of opaque textbook jargon--forcing readers to chase links deep into the weeds--into the very beginning of a such an article. DonFB (talk) 23:30, 11 November 2023 (UTC)

Glad I could help. If you see other articles that you find similarly opaque, please don't hesitate to ping me or start a conversation on the math wikiproject or the like. I think there might be still some folks who would prefer to list a function-based definition before a pairing-based definition (definitely more common in typical sources), but you are probably right that the pairing-based version is more accessible, and if we put the function-based versions slightly afterward I think undergraduate math students will still be able to figure out what they need. –jacobolus (t) 23:59, 11 November 2023 (UTC)

@D.Lazard does this version seem okay to you? –jacobolus (t) 00:56, 12 November 2023 (UTC)

Jacobolus, just to add a bit more about my thinking:

You wrote:

Parentheticals are common in lead sections because there's a lot of information to cram in and it's hard to do so in a logically structured sentence.

Focusing more on the second part of your comment, "there's a lot of information to cram in", I would say that approach is a significant cause of loading jargon into the first sentence or first paragraph of lede sections. Technically knowledgeable editors tend to want the very early text to be surgically precise, and therefore they use exacting terminology and jargon and add parentheticals if that seems necessary. As a result, they end up writing technically sophisticated ledes that can be all but incomprehensible to typical readers. I've noted that other editors and you have spoken of an intended audience for an article like this--generally, referring to high school or undergrad math students. Here, we may have a real philosophical difference, at least regarding the lede section. My idea of the audience for the lede section of any article is--everyone. I don't think in terms of pitching the lede to any particular segment of the population. I want a lede to start by expressing the fundamental concept in everyday language, without sacrificing basic accuracy, and then build up to more complex concepts. Attempting to immediately "cram in" in a lot of info, in absolutely precise technical language, is the road to opacity. Editors have the remainder of the lede section to begin introducing more complexity, and they have the entire body of the article to dive into the really technical aspects of the subject. Keeping the lede section mostly free of jargon and links from jargon can give the reader an uninterrupted reading experience. That is not a betrayal of an article's "duty" to inform the public. It is, rather, a service to the public. DonFB (talk) 08:57, 12 November 2023 (UTC)

While this is true, and in general I strongly agree with everything you wrote, in practice the most common group of people reading this article are students in introductory courses. You can see from the page view statistics that there is a strong weekday vs. weekend bias and a strong beginning-of-the-semester vs. typical school holiday bias.

So it's important to make sure that any accessible version of an explanation or definition doesn't promote misconceptions for these students who may be relying on it. –jacobolus (t) 14:06, 12 November 2023 (UTC)

I disagree with the current version:

• The first sentence uses the term "pairing", with a WP:SUBMARINE link to Binary relation, where the term does not appear. Moreover, a reader who needs a definition of this term may search for Pairing, which is unrelated and very technical. This is not only possibly confusing, but also enforce the rather common misconception that using common English words instead of the proper technical words may makes understanding easier.
• The example is presented in a much too technical way, since it does not contains anything more than: "adding one" defines a bijection from the even numbers to the odd numbers, and the inverse bijection is "subtracting one". Moreover this example may be confusing, since "adding one" defines also a bijection from the odd numbers to the even numbers, and a bijection from the integers to the integers. So, a much better example would be: For example, "multiplication by two" defines a bijection from the integers to the even numbers, and the inverse bijection is the "division by two".
• IMO, starting with the definition as a relation rather than with the definition as a function is not a good idea, since, in practice, bijections are always defined as functions. So readers who have already heard of bijections may be confused by a new point of view, and readers who learn bijections as relations will have, later, to learn another point of view.

D.Lazard (talk) 10:42, 15 November 2023 (UTC)

I have edited the lead in the line of the above comments. I have also expanded the paragraph on cardinalities. Probably a clean-up is still needed for a more colloquial use of "to", "for", "by", "from", etc. Also, with the new version, it is not needed to know what are the domain and the codomain of a function. D.Lazard (talk) 15:42, 15 November 2023 (UTC)

I think the lead is more accessible than before @DonFB asked their question (because we e.g. include inline definitions for injective/surjective), but I think this version is still going to be hard going for those who aren't math students.

I agree that the previous example got unhelpfully big and wasn't the clearest. I was trying to explicitly show a set of ordered pairs. Your example seems fine, or we can still find a better one.

You are probably right that a bijection should be described primarily as a function, as this is the main way people think about it. I wonder though how we can make that version as clear as possible to laypeople.

The part about counting is helpful, but a bit awkwardly worded I think.

misconception that using common English words instead of the proper technical words may makes understanding easier – it doesn't make detailed technical understanding easier, but it certainly makes it easier for a newcomer who doesn't have any clue what the jargon words mean to figure out the basic idea. The new version has enough jargon in the first few paragraphs to be noticeably less welcoming.

The new paragraph about invertible functions helpfully includes an inline definition of inverse, but unfortunately it is not at all accessible to anyone who isn't a math student. It assumes people know not only about this arrow notation, but also about function composition and identity functions. I wonder if this paragraph can be made less obscure. –jacobolus (t) 16:15, 15 November 2023 (UTC)

This phrase seems to have either an extraneous word, or is missing a word: "that for each element of the codomain is mapped to from at least one element of the domain". DonFB (talk) 20:41, 15 November 2023 (UTC)

 Fixed. D.Lazard (talk) 21:28, 15 November 2023 (UTC)