Talk:Bijection/Archive 1

Archive 1

Line 5

Check line 5, function succ??? I dont get it --'''Rohit''' 08:11, 20 January 2006 (UTC)

succ=successive. as in successive interger after n (n+1) — Preceding unsigned comment added by 69.234.48.36 (talk) 05:38, 28 February 2006 (UTC)

Self-contradiction in one-to-one correspondence (About the incomplete totality of the set of all prime natural numbers)

Essay moved to User:BenCawaling/Essay. Gandalf61 08:31, 14 April 2006 (UTC)

permutation

This page says that bijection is also called permutation, while the permutation page says that permutation has to be on finite domain. Mizar does not restrict permutations to finite domains (http://mmlquery.mizar.org/mml/4.66.942/funct_2.html#NM2), but I don't claim that the terminology is right there. JosefUrban 23:14, 24 November 2006 (UTC)

Bijection Composition

I have moved this content from the top of this page:

In this page it is said that When X and Y are both the real line R, then a bijective function f: R → R can be visualized as one whose graph is intersected exactly once by any horizontal line.

For intuitively sound functions this is probably true.

However, consider the function $f:R->R$ with

$f(x)=2x$ for every $x\in Q$ and

$f(x)=-2x$ for every $x\in R-Q$.

For this example it is ofcourse still true that for every $y\in R$ there is one unique x with the property that $f(x)=y$. But it is not any longer possible to give a clear visualisation of this, in the way described in this page.

Regards, Bob v. R.

The theorem still holds for this example. The plot of this will look like a "X" going through the origin, but each arm of the x is not a continuous line, it is a "dense" set of of points. For all horizontal lines corresponding to rationals, the intersecting point will be on the line f(x) = 2x, and horizontal line line will not intersect the line f(x) = -2x, and a similar scenario occurs for horizontal lines at heights corresponding to numbers not in Q.--Nappyrash 09:28, 26 November 2006 (UTC)

Rename?

I might sound like a pedant (or perhaps even a moron!). But what are peoples opinions on renaming this page Bijective function? I only suggest this as we have pages Injective function and Surjective function, why not Bijective function? I only ask here, as I'm not too sure how to go about changing pages and redirects/I don't want to piss anybody off (especially people much more knowledgeable than me). Help plz 17:46, 14 January 2007 (UTC)

The reason there is an injective function term is because the term injection has multiple meanings. The terms bijection and surjection only have one (well-known) meaning. At any rate, bijective function redirects to bijection, so all the terms and their variants are covered. — Loadmaster 22:26, 1 March 2007 (UTC)

It's true that bijection is unambiguous, so there's no real need to have the article at bijective function, but seeing as injective function has to be at that title, wouldn't it make sense to have all three matching? Surjection already redirects to surjective function; why not make this one match the other two? Is there a good reason to be inconsistent? -GTBacchus^(talk) 21:23, 9 April 2007 (UTC)

I have at least one argument against using "bijective function" as the main name: it's not at all common in actual mathematical writing! "Bijective map" is definitely more widespread (outside of pure nomenclature) and "bijection" wins over both of them. Similar usage patterns seem to hold for "surjective function"/"surjective map"/"surjection" and "injective function"/"injective map"/"injection". Arcfrk 03:57, 10 April 2007 (UTC)

Ok, that indicates moving the injection article to injective map, and our question is whether the others should accord with it, or use the more common bijection and surjection. I haven't got a strong opinion on that question; I guess I would lean towards consistency. -GTBacchus^(talk) 06:04, 10 April 2007 (UTC)

Word origin

Speaking of names, does anyone know the etymology of the term "bijection" (and "surjection" and "injection")? I can't find any mention at dictionary.reference.com or at Merriam-Webster.com. — Loadmaster 22:26, 1 March 2007 (UTC)

Well, the terminology is due to Bourbaki, if that helps. And 'sur' is a Latin/French/English prefix for 'onto', so that's clear enough. And I've always assumed the 'bi' prefix alludes to the function being two-way i.e. invertible. No idea where they got 'in' or 'jection' from though. Algebraist 14:47, 16 March 2007 (UTC)

We have English "onto", telling us every element of a codomain is covered by some element of the domain, which corresponds to "surjection", and to "epimorphism". You'll never guess what "epi-" means in Greek. Then we have 1-1 with the meaning that distinct elements in the domain map to distinct elements in the codomain, which corresponds to "injection", and to "monomorphism". Of course, "mono-" is Greek for one. The reasoning behind "injection" is that the map essentially creates an identical copy of the domain inside the codomain; it "injects" it, with the "-ject" part deriving from the Latin jacere, to throw. Finally, we have one-to-one (which I always thought was horrible, too easily confused with "1-1"), which corresponds to "bijection", and to "isomorphism". We can understand the "bi-", meaning two, as either "injection"+"surjection", or (better) as indicating that the mapping is invertible, so we can map in two directions. We can translate "iso-" as "same", so isomorphic objects have the "same form". (The Greek μορφή means form or shape.) Of course, a "morphism" is a structure-preserving mapping, which I think is shortened from "homomorphism" (and "homeomorphism").

A good place to find etymology for a word is the American Heritage Dictionary, available at Bartleby or through Dictionary.com as well as OneLook (and other sites, I'm sure). A standard lexicon for Ancient Greek is LSJ (where we find that Morpheus, the god of dreams, gets his name from the shapes he conjures up in our heads).

The "-jection" names tend to be used for mappings of sets, whereas the "-morphism" names are used more in abstract algebra and higher mathematics. My impression is that the other names become less common as we move into university and beyond. --KSmrq^T 08:15, 10 April 2007 (UTC)

vertical bar?

Excuse me, I am unable to understand the notation in:

• For a subset A of the domain and subset B of the codomain we have:

|f(A)| = |A| and |f⁻¹(B)| = |B|. —Preceding unsigned comment added by 83.54.90.204 (talk) 17:08, 2 April 2008 (UTC)

The vertical bar notation is a sort of informal indicator of "size" -- so |A| is the "size" or "cardinality" of A, and we say $|A|=|B|$ iff there is a bijection between A and B. It is possible to make this idea more formal (see cardinal number#formal definition), but it's a hassle and not really necessary here. Hope that helped! 69.181.216.178 (talk) 22:59, 8 May 2009 (UTC)

Terminology

Elaborating on the discussion above under Rename? and Word origin: wouldn't it be (at least historically) correct to speak of the property "bijective", in stead of the object "bijection"? In the case of bijective this doesn't make a huge difference, but in the case of e.g. injective it does, because "injection" could mean injective function or injective relation, which are two different things. (Not all injective relations are functions.) The same goes for surjective relations and functions. I think Bourbaki has introduced the adjectives "...jective", not the nouns. My guess is, this was done for this reason.

I'd say it would therefore be better to define ...jective and, directly following the definition, mention that "...jection" can refer to ...jective relation or ...jective function. That way the nouns are explained in a clear way (and thus the usage pattern is not ignored), without making the popular mistake of actually defining e.g. injection. The more technical analysis about why the adjective is defined rather than the noun, can for example be explicated further down the article or in a footnote. Any opinions?

145.88.209.33 (talk) 10:15, 10 July 2009 (UTC)

I suggest naming the articles "surjectivity", "injectivity" and "bijectivity". That way it's instantly clear we're talking about properties, in stead of (kinds of) objects. After defining the property we can mention that the the word "surjection" (or "injection" etc.) is usually used to mean surjective function. I agree the technical analysis should be in a footnote or further down the article. 131.211.215.202 (talk) 11:02, 13 July 2009 (UTC)

Anyone else?... I think this is an important point. 145.88.209.33 (talk) 11:19, 12 August 2009 (UTC)

Article names should be nouns, not adjectives, per Wikipedia:Naming conventions (adjectives). So "bijective" is out. I think that "bijection" is preferable to "bijectivity", as it is simpler and much more recognizable. The case of injective, non-functional relations is really a minor topic. The main focus of all three of these articles is functions. — Carl (CBM · talk) 11:55, 13 August 2009 (UTC)

But there are no articles "injection" and "surjection"; they are called "injective function" and "surjective function". As far as I know these names were chosen to avoid ambiguity. I think this is a strange inconsistency with the name of this article: "bijection". Then, thinking about a solution I concluded that, although in every-day use, the terms ...jection are sloppy, as I tried to show above. I'd say "...jectivity" would be best. 145.88.209.33 (talk) 07:30, 14 August 2009 (UTC)

I agree with Carl. For me, and probably 97% of all mathematicians, bijection means a bijective mapping. I would guess that people spoke about bijective mappings a long time before they spoke about bijective relations, and that the terminology for the latter was borrowed from the former. ~~ Dr Dec (Talk) ~~ 16:21, 20 August 2009 (UTC)

In fact Mathworld assumes bijection to mean a bijective mapping. ~~ Dr Dec (Talk) ~~ 16:26, 20 August 2009 (UTC)

Sure, I agree. Being a small portion of that 97%, I use bijection in exactly the same way. The problem lies with injection and surjection however. These words are ambiguous. In everyday use this doesn't pose a problem, and I use them on a regular base like most mathematicians. At the same time I think it would be wise to be more precise in an encyclopedia, by defining the properties injectivity and surjectivity in stead of the (kinds of) objects injection and surjection. This is already more or less the case for these lemmas, but at the moment there is this strange naming inconsistency with the lemma bijection.

By the way, the words injection etc. are derived from injective, not the other way around! The claim that people spoke about bijective maps long before they spoke about bijective relations is not true. In fact the property bijective got introduced first and was applicable to both maps and relations. 145.88.209.33 (talk) 07:47, 27 August 2009 (UTC)

So, the point is:

1. There is an inconsistency in the naming of lemmas: "Injective function" and "Surjective function" vs. "Bijection".
2. Historically the properties injectivity, surjectivity and bijectivity are defined and the terms "injection", "surjection" and "bijection" are derived.
3. Usage patterns suggest the latter terms. This creates ambiguity in the cases of injection and surjection.

Some (including myself) conclude that it would be best to use the terms "injectivity", "surjectivity" and "bijectivity" as "root" concepts and derive the other concepts from them. We should define injections to be injective maps (not injective relations) thus using the correct direction of derivation without ignoring the usage pattern. This way it should be clear to everyone where ambiguity could occur and what the "pure" terminology is, without being forced into some unnatural terminology where the words "injection" and "surjection" are taboo. 87.212.194.255 (talk) 12:53, 3 September 2009 (UTC)

I forgot to respond to Carl's reaction. I think "bijection" is indeed more recognizable, but only slightly so. The word "bijectivity" should be instantly intelligible to everyone. What's to be gained is not that attention is drawn to the indeed minor topic of in- and surjective non-functional relations, but that terminology is introduced in a clean way.

Lets say the first sentence of the article would read

In math injectivity is the property of maps and binary relations that...

and the second sentence would be something like

The word injection usually means injective map (as opposed to injective relation).

I think that this would be clear to everyone, that it doesn't obscure anything and that it acknowledges the usage pattern, while at the same time it is the cleanest way of defining the concepts. 87.212.194.255 (talk) 13:33, 3 September 2009 (UTC)

I don't really see what the issue is. All three of the articles are first and foremost about functions; the cases of injective non-functional relations and surjective non-functional relations are of much less interest and may not even need to be mentioned in the lede. (Indeed. injective relation and surjective relation simply redirect to the articles on functions.)

If it is vital that the three articles have parallel names, we could move bijection to bijective function. But it doesn't seem very important to me for the titles to all be parallel. My personal opinion is that we should redirect everything to Bijection,_injection_and_surjection. — Carl (CBM · talk) 15:40, 3 September 2009 (UTC)

I know the articles are presently first and foremost about functions, but that's the whole point under discussion. I think there are good reasons to choose a slightly different approach. The fact that the current articles take some other approach can hardly be an argument if the approach itself is the subject of discussion.

I have three questions:

Your opinion is that it's not necessary for the articles to have consistent names. But what do you think about the historical argument for choosing a slightly different approach?

Injective and surjective relations might not be as commonly used as injective and surjective maps, but they are certainly more than just footnotes. They are of interest in logic and theoretical computer science for example. Don't you agree that the articles should reflect this too?

I sketched two sentences that could be used as introduction. Do you agree that these phrases are instantly clear, don't seem unnatural, are technically cleaner and at the same time fully acknowledge the usage pattern? 87.212.194.255 (talk) 11:46, 4 September 2009 (UTC)

P.S. I don't have a strong opinion on using separate articles or bringing them together in one article. If pressed I think I'd lean towards one article. (That's a different discussion though.)

I'm sorry; I thought the discussion was about renaming the articles.

I am not convinced that, historically, injective relations truly predate injective functions. I would guess that either the terminology was applied to both simultaneously, or injective functions were studied first. Of course I would be glad to be proved wrong about that. It could be that Bourbaki defined injective in the context of relations, only to immediately specialize it to functions. That would be the normal sort of generality one would use when writing a mathematics reference, but it wouldn't convince me that injective non-functional relations are really of interest.

As a logician, I do occasionally study injective, non-functional relations. However, I do see them primarily as a footnote in this context, a topic that is worth mentioning in passing but not dwelling on. The real issue, as with partial functions, is that the domain and codomain of the relation must be taken into account at all times. But we don't need to hammer the reader over the head with this issue, especially not right at the start of an article.

I don't favor starting with "injectivity" and then defining "injection" from that. I think it adds an unnecessary layer of wrapping to the concepts. Maybe someone else has an opinion. — Carl (CBM · talk) 12:06, 4 September 2009 (UTC)

As far as I know the terminology was applied to both simultaneously. But the point is that (historically) the word "injection" is derived from "injectivity", not the other way around. The current articles seem to suggest the false direction by choosing injection as the "root concept". The reason that originally only the properties were defined must have been to avoid ambiguity I guess. Or maybe for flexibility, who knows. That's why I phrased my suggestion for the introduction in that way. I don't think it would confuse anyone. (Or am I thinking too much of the average reader?) In any case, I prefer being precise about it to the quick-and-dirty approach. In an encyclopedia that is, in day-to-day use it would of course be annoying to be that precise. 87.212.194.255 (talk) 01:05, 5 September 2009 (UTC)

I just looked up Bourbaki's "Theory of sets" in Google books (in English translation). The definition of an injective mapping is on page 84. The definition gives both "injective" and "injection" but not "injectivity", and only gives the definition for mappings, not relations. So I do not see evidence there that "injection" is derived from "injectivity", nor that the definition was given simultaneously for functions and relations. As always, I would be glad to be proved wrong about this via references to prior usage of the terminology. — Carl (CBM · talk) 02:18, 5 September 2009 (UTC)

I was clearly wrong on this point. Thanks for the effort of showing it. I guess, my argument boils down to a personal preference of approach. For aesthetic reasons I still strongly have this preference, but at least you have shown there's nothing wrong with the current approach. So, I'll leave it at this. Thanks again and see you around. 87.212.194.255 (talk) 22:42, 7 September 2009 (UTC)

merge

I think we should merge this page with injective function and surjection. They are already using the same pictures. Any objections? What should be the name of the new page? MarSch 16:36, 21 Apr 2005 (UTC)

That's a tough one. Maybe properties of functions? Deco 04:44, 22 Apr 2005 (UTC)

Yes, I was thinking maybe it could simply be jection or injection, surjection and bijection or in-, sur- and bijection or maybe injective, surjective and bijective or then again in-, sur- and bijective. Jection or maybe jective would make linking easy: injective, although it doesn't highlight as I expected/hoped. Maybe I should file that as a bug. -MarSch 12:42, 22 Apr 2005 (UTC)

Let's not make article titles that are meaningless on their own. The linking feature as it is now is useful for links like noncommutative, although I can't say I've seen such a link recently. Deco 16:42, 22 Apr 2005 (UTC)

By merging, interwiki linking has been made almost impossible, since most other wikipedias have separate articles. What is wrong with navigation boxes to link related articles? To prevent erroneous automated interwiki linking, I have changed the redirect to the Bijection-section of the page. This will have no effect on en:wikipedia, but will stop people on dozens of other wikipedias to correct automated interwiki links manually. -- Quistnix 07:25, 28 December 2005 (UTC)

They're only using the same pictures because they're interrelated concepts—just like government, politics and civil service are interrelated. A lot of interrelated articles share pictures; there's nothing wrong with that. Bijection, surjection, and injection are each separate and distinct concepts that are notable enough on their own. If at least one of them was a stub, then a merge suggestion might warrant consideration, but that's not the case. This is like merging triangle, regular polygon, and equilateral triangle just because they're related. Overzealous merging and deletion are really negatively impacting the usefulness of Wikipedia. Let's not get carried away with change for the sake of change and fixing things that aren't broken. A single article for all Ford motor vehicles is not going to be as useful to Wikipedia users as having separate articles for each model.--Subversive Sound (talk) 18:47, 13 March 2010 (UTC)

Unknown character

The 5th paragraph is displaying an unknown character in Firefox using Unicode (UTF-8). This is the line in question:

The set of all bijections from X to Y is denoted as X ↔ Y. (Sometimes this notation is reserved for binary relations, and bijections are denoted by X ⤖ Y instead.)

—is anyone else seeing that as an unrecognized character (for me it shows a box with "29" and "16" printed in it, arranged one above the other)?--Subversive Sound (talk) 18:54, 13 March 2010 (UTC)

You mean the character that would be in bold? I can see it, it's an arrow with two heads. The 2916 is actually a code that lets you look it up (not that this is very useful when you are reading an article); see [1].

The most common reason for seeing these boxes is that you don't have sufficiently comprehensive fonts installed. The unicode itself is not usually the issue, it's just a matter of having a font that includes this symbol installed for your browser to use. — Carl (CBM · talk) 19:31, 13 March 2010 (UTC)

Composition of function

Is this right? "A relation f from X to Y is a bijective function if and only if there exists another relation g from Y to X such that g o f is the identity function on X, and f o g is the identity function on Y." f:X to Y; g:Y to X. So, g o f is identity function on Y and f o g is identity function on X.Its written in the otherway round. Kindly verify.

Hello, g o f means "first do f, then do g". This is the usual convention in mathematics. So f takes you from X to Y, and g takes you from Y back to X. So g o f goes from X to X. Hope that clarifies things. Sam Staton (talk) 09:53, 5 March 2008 (UTC)

I'm wondering if the present wording is unclear only to me:

... a bijective function, is a function f from a set X to a set Y with the property that, for every y in Y, there is exactly one x in X such that f(x) = y. It follows from this definition that no unmapped element exists in either X or Y. Alternatively, f is bijective if it is a one-to-one correspondence between those sets; i.e., both one-to-one (injective) and onto (surjective).

It seems as though "it follows" is untrue: the first sentence speaks only of Y, leaving the impression that there could be other unmapped elements of X so long as elements of Y are fully satisfied. The paragraph that follows then counters this and covers both sets. It seems to me that it would be clearer if we moved the "it follows" sentence to the end of the following paragraph, while removing "alternatively". --216.231.3.226 (talk) 19:48, 27 December 2010 (UTC)

"sumdif" example doesn't make sense

Is this supposed to be a bijection from R2 to R2? That isn't clearly specified. Also, it is hard to see that the function is bijective... are there really an infinite amount of pairs such that the first element equals 4... are there really no conflicts between the pairs? A reference or a cleaner explanation would be nice. —Preceding unsigned comment added by 24.99.60.219 (talk) 17:27, 20 April 2011 (UTC)

an incorrect line

each SSN is assigned to a person...one SSN can be assigned to more than one person. — Preceding unsigned comment added by 12.177.242.131 (talk) 04:49, 13 November 2012 (UTC)

Not really incorrect, it does not imply that a SSN is assigned to a unique person, but I changed it anyway for clarification. Bill Cherowitzo (talk) 19:55, 13 November 2012 (UTC)

Subheading: Inverses

The last sentence in this section is: "Bijections are the invertible functions." Can this be clarified to state: "Every invertible function is a bijection and every bijection is an invertible function."? OKmisterWIKI (talk) 15:55, 24 March 2013 (UTC)

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)