Proving Mappings Are One-to-One and Surjective: A Rigorous Approach

  • Thread starter sponsoredwalk
  • Start date
In summary, the conversation discusses the difficulty in understanding the concept of surjectivity, injectivity, and bijectivity in the context of functions. The speaker also asks for help in finding a more rigorous definition and method for proving these properties. Examples of functions are provided to illustrate the challenges in understanding and proving these properties.
  • #1
sponsoredwalk
533
5
Honestly I'm just having such a hard time understanding how to get this into a rigorous
fashion. I'm talking about proofs of surjectivity, injectivity & bijectivity.
The standard courses go from sets to functions to real numbers in analysis &
it's taken me quite a while to get rigorous in my proofs regarding sets. First they were
hand wavey, then they became good but extremely long requiring many many steps
to show certain things but now with the power of logic & truth table equivalences I
have reduced set proofs to two lines with full healthy understanding. I just want you
to know where I'm coming from because with functions I'm trying to get the same
pattern.

Let me give my definitions:

A mapping f | X → Y defined by f | x ↦ f(x) is the specification of a triplet (X,Y,f).
As far as I understand it the triple is an ordered set as opposed to an unordered set
{X,Y}. What I'm just curious about is while {X,Y} is an unordered set & (X,Y) is an
ordered set my book doesn't explicitly say it but is (X,Y) just another notation for the
cartesian product? They mention both things in the book one after the other but don't
make it explicit that (X,Y) is just another notation for the cartesian product but I think it's
correct. Well, assuming this is the case, what's with the notation (X,Y,f)? It's just notation
to indicate a rule is defined on the set right? (pages 9-10 of this book if you
don't know what I'm talking about).

Well a mapping f | X → Y defined by f | x ↦ f(x) is the specification of a triplet (X,Y,f).
A mapping is surjective if f(X) = Y. A mapping is injective if [f(x₁) = f(x₂)] ⇒ (x₁ = x)₂ or
equivalently [f(x₁) ≠ f(x₂)] ⇒ (x₁ ≠ x)₂.
A mapping f | X → Y is bijective if (f(X) = Y) ⋀ [ [f(x₁) ≠ f(x₂)] ⇒ (x₁ ≠ x₂) ].

Is there a more rigorous definition that hints at a proper method to prove things?
Until I found the definitions of sets involving logical implications and such I found it
very difficult to prove things regarding sets & had to rely on some intuition but now
they just roll off in a chain of logical implications which is really satisfying, I don't
see how to get that out of functions.

For instance, while I know f | RR defining the mapping x ↦ x² is
neither injective nor surjective I know how to make it so,
f | R⁺R⁺ defining x ↦ x² is bijective. But if I follow the method
[f(x₁) = f(x₂)] ⇒ (x₁ = x₂) by rewriting it [f(x) = f(y)] ⇒ (x = y) like so many books
do when the mapping is f | RR I get:
[f(x) = f(y)]
x² = y²
x = y

I mean they do it in a function like this f(x) = 3x - 7
f(x) = f(y)
3x - 7 = 3y - 7
3x = 3y
x = y

This is in a discrete math book on googlebooks as the only example in a chapter &
I mean had I not known about the methods of understanding this like I illustrated above
I'd be stumped here, I just want to get this rigorous. All the schaums manuals skip
proofs & give no helpful examples, some advanced math books I've checked on google
give no help, I really really need help here. I found one book at the weekend
describing a function with an x⁵ + 5x⁴ ... something crazy & it took a whole page to
justify the argument - something I can't find described anywhere else & I can't
find the book in my firefox history as it will take forever & I've already tried.

Any help?
 
Physics news on Phys.org
  • #2
No, I don't think there are more "rigorous" definitions. As for ease of use, note that in the context of your post, f(X) = Y is not the clearest way to check surjectivity. For one, the direction f(X) contained in Y is clear. Usually the other direction, when spelled out, is commonly defined as surjectivity. To say that Y is contained in f(X) basically means that for any y in Y, there exists an x in X such that f(x) = y. In my experience, this is the easiest way to check surjectivity, but you really have to work with a couple of examples to really grasp surjectivity.

As for injectivity, that is about as intuitive as a definition as one could obtain, and it's the criterion most often used in basic real analysis. I'm not sure I understand your gripes about using this definition, as you illustrated two examples. Proving injectivity of functions doesn't really get much more complicated than in the two examples you illustrated, and I'm not discerning whether you understand them (in particular the first one) completely.
 
  • #3
Here is an example I found in an old PF post:

f | x ↦ x³ + x

x³ + x = y³ + y

x³ - y³ + x - y = 0

(x - y)(x² -xy + y²) + (x - y) = 0

(x - y)[(x² -xy + y²) + 1] = 0

For this to hold either x = y or x² -xy + y² + 1 = 0.
Supposedly x² -xy + y² + 1 = 0 is contradictory in R.
I can't see a method to show this, I can't see how to complete the square or understand
how a discriminant even matters here?

The point is that no book teaches you how to do this, & what if you get some crazy
function with powers of x⁵ + 5x⁴ etc... in the equations? I'm sure some basic calculus
techniques could be used but you're not supposed to be using that stuff in a discrete
math book or in an analysis book where you haven't even learned these technique's yet!

I'm just wondering how you deal with similar situations, hoping someone whose dealt
with these will direct me to a good link & hopefully explain just what's going on in general
:tongue2:.

Also, in regard to general functions not dealing with specific equations, I mean how
do you deal with them?

Example: if f | X → Y show that the mapping F | X → X x Y defined by F | x ↦ (x,f(x)) is
injective.

How do you deal with something like this?

A mapping is injective if [f(x₁) = f(x₂)] ⇒ (x₁ = x₂) or equivalently [f(x₁) ≠ f(x₂)] ⇒ (x₁ ≠ x)₂.
So in this situation I just write [F(x₁) ≠ F(x₂)] ⇒ (x₁ ≠ x₂) & magic, the proof is done?
I get the feeling that all the proofs of this abstraction are the same, just repeat the
definition & that's a proof when it doesn't feel convincing in the least.

Thanks a lot for taking the time out to help btw :wink:
 
  • #4
I found another example:

Show that f | RR defined by f | x ↦ x³ is injective.

[f(x₁) = f(x₂)] ⇒ (x₁³ = x₂³) ⇒ (x₁³ - x₂³ = 0) ⇒ [(x₁ - x₂)(x₁² - x₁x₂ + x₂²) = 0]

⇒ [(x₁ - x₂) = 0] ⋁ [x₁² - x₁x₂ + x₂² = 0]

Now the book says that we must show that

[x₁² - x₁x₂ + x₂² = 0] ⇒ (x₁ = x₂) which makes sense as [(x₁ - x₂) = 0] already implies x₁ = x₂.


(x₁² - x₁x₂ + x₂² = 0) ⇒ [ (x₁² - x₁x₂) + x₂² = 0 ] ⇒ [ (x₁² - x₁x₂) + x₂² = 0 ]

⇒ [ (x₁² - x₁x₂ + ¼x₂²) + (x₂² - ¼x₂²) = 0 ] ⇒ [ (x₁ - ½x₂)² + ¾x₂² = 0 ]

Now it says that because the squares on non-zero real numbers are positive we conclude
that x₂ = 0 and then that x₁ = 0.

I just don't see how the squares of negative numbers always being positive imply that
both x₁ & x₂ are zero... Also with the x² -xy + y² + 1 = 0 being a contradiction in R as
shown by the determinant :confused: I just don't see it.

If I get some weirder equation than x³ I haven't a hope of dealing with it, and even the
x³ situation is iffy as I've shown here. Nearly very book I look at ignores this question
while going off to prove injections and bijections on abstract systems without dealing
with the fundamentals, it's crazy!

Do you guys all know how to deal with this stuff, to recognise it when it comes up &
all the ins and outs here when it doesn't seem to be addressed in any book except the
odd obscure discrete math book in one example...?
 
  • #5
I have a better idea of your question now I think. The short answer is you learn to prove mappings are one-to-one or surjective more easily as you delve further into a particular subject.

Since we're dealing with real functions, it's pretty easy to show that as long as your function is increasing or decreasing, then it's injective. Of course, if you know the mean value theorem, then you know that a differentiable function from R to R is increasing if its first derivative is positive everywhere. From this, we can easily conclude that x^3 is injective.

But of course you'll find these examples when first encountering functions in naive set theory or in your discrete math book or whatever. These books most likely just want you to work with the definition. If you have a real function here, and you don't know calculus or analysis, then all you can do is use algebra. If you have a polynomial f, like in your examples, then you start by supposing f(a) = f(b) for a,b in R (or whatever subset of R you're restricting to). Then you rewrite as f(a) - f(b) = 0 because they're polynomials, so what else can you do besides move everything to one side and try to factor out an (a-b) term? That's all there is to it.

So yes, no one who has already done analysis would prove injectivity of real functions in the same way as in the above examples. But it's still important that you realize that these definitions for injectivity and surjectivity are rigorous and make sense intuitively. You'll encounter the same definitions everywhere in math, but real functions allow you to visualize the situation clearly. In abstract algebra, for instance, you often work with very general structure-preserving maps called homomorphisms and it will not always be intuitively clear that a particular homomorphism is injective or surjective. However, there is a particular criterion that will allow you to verify easily whether some homomorphism is injective. If you've seen linear algebra before, you've probably seen this criterion and know it has to do with the kernel of a linear map.
 

1. What is injectivity in mappings?

Injectivity in mappings refers to the property of a mapping or function where each element in the domain is paired with a unique element in the codomain. This means that no two elements in the domain can map to the same element in the codomain.

2. How is injectivity determined in a mapping?

Injectivity is determined by checking if each element in the domain has a unique image in the codomain. This can be done by comparing the outputs of the function for different inputs. If there are no repeated outputs, the mapping is injective.

3. What is the importance of injectivity in mappings?

Injectivity is important in mappings because it ensures that each element in the domain has a unique corresponding element in the codomain. This allows for a one-to-one correspondence between the elements of the two sets, making it easier to analyze and manipulate the mapping.

4. How is a mapping with injectivity represented?

A mapping with injectivity is represented using set notation, where the function is defined as f: A → B, where A is the domain and B is the codomain. Additionally, the mapping can be visually represented using graphs or tables.

5. Can a mapping be injective and surjective at the same time?

Yes, a mapping can be both injective and surjective at the same time. A mapping that is both injective and surjective is called a bijection and it has a one-to-one correspondence between the elements of the domain and the codomain.

Similar threads

  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
20
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
440
  • Calculus and Beyond Homework Help
Replies
17
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
451
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
743
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
Back
Top