Onto and one-to-one

Loading...

From the course by University of Amsterdam

Logic for Economists

3 ratings

University of Amsterdam

Logic for Economists

3 ratings

This course provides a very brief introduction to basic mathematical concepts like propositional and predicate logic, set theory, the number system, and proof techniques. At the end of the course, students will be able to (1) detect the logical structure behind simple puzzles (2) be able to manipulate logical expressions (3) explain the connection between logic and set theory (4) explain the differences between natural, integer, rational, real and complex numbers (5) recognise different basic proof techniques

From the lesson

Predicate logic, set theory, and functions

Logical statements that depend on a variable.

Predicate logic7:08

Predicate logic and set notation11:33

Functions and their graphs18:18

Onto and one-to-one19:44

Meet the Instructors

Florian
Dr. Ir.
Quantitative Economics

One-two, one-two-one.

No, we shall not be starting dance lessons.

But we shall be solving equations.

So when we have a function,

we've got a domain,

a range and a rule f which specifies for every element in the domain,

an element in the range.

So if A is in the domain and B in the range,

such that, half of A is B,

then we call B the image of A and A an original of B.

And you see, here it is 'the' image because it's the only one and

here it's 'an' original because there can be several ones.

Now let's look at a function f from D to R is called injective.

If every B in R has at most one original,

or if you will, we can say this differently.

Or if the equation have A = B has

at most one solution A for given B.

So you see, injectivity of a function is

about the number of solutions the equation f(a) = b can have.

And if the function is injective we say that this equation can have at most one solution.

Now just to remind ourselves what this means.

A function is injective,

well, draw our arrows here and here.

Now if I look at the points in the range,

this point has one original and one only.

This point has one original and this point has no original.

So every point has at most one original.

So this function is injective.

On the other hand, function like

this, like so. If we look at the first point,

this point has three originals and this point has no original.

So while this point has the required number of originals, at most one.

This one has three of originals,

so this function is not injective.

Now we can just play this game again.

By saying that a function f from D to R is called surjective.

If every point B in the range has at least one original in D or again,

if the equation f(a) is b has for every b, at least one solution a in D.

Now this is something you often want to have if you want

to solve a certain equation that you know that

a solution or at least one solution exists.

So let's look at our the examples again.

If I've got a situation like this then I have to look at every point in the range.

This point has at least one original.

It actually has two,

those two points.

That's originals.

And this point has one original,

which is at least one,

so this function is indeed surjective.

On the other hand if I'm looking at

this function where the arrows

go as follows, then, yes.

This point in the range has at least one original.

It has three but this point has none so

this function is not surjective.

If we combine these two notions we get a new notion.

A function f from D to R is called bijective if for every b in R,

there is exactly one original a in D or if the equation f(a) is b has for every b

in R exactly one solution a in D or again, if f is both injective and surjective.

Three ways of saying the same thing.

Now let's have a look our examples again.

So this first example,

when I look at my range,

this element has exactly one original.

This element has exactly one original So clearly this function is bijective.

On the other hand, if I look at

this example then I see that this element has exactly one original.

This element has exactly one original,

but this element doesn't have an original at all.

So this function is not bijective.

Actually it is injective but not surjective.

Actually we have to look a little bit closer at injective functions,

sorry, at bijective functions.

So, let's give an example of a bijective function from the set one,two,

three to the set four,

five, six and we define it as follows.

One is mapped to five,

two is mapped to four,

and three is mapped to six.

So as we stated,

every element in the domain is associated to exactly one element in the range.

That's the definition, of well, of the function.

But on the other hand every element in the range has exactly one original in the domain.

What this means is that we can invert the arrows.

So we now can have arrows go in a different direction.

So while we had originally a function which mapped one to four, two.

Sorry, one was mapped to five.

Let's fix that.

One was mapped to five,

two was mapped to four and three was mapped to six.

We now have also the rule that four has mapped to two,

five is mapped to one and the six is mapped to

three and every element in the range is accounted for.

So for every element in the range we've got exactly one image.

So g is also a function.

And that is the theorem.

If f from D to R is bijective then

there is a function g which goes from R

to D such that if f(a) = b,

then g(b) = a.

Now the difficulty with this theorem is not that the proof is terribly deep,

but I have to see what it is that has to be proved.

We can, of course,

always write that as a function g from R to D but we have to define it.

Now the definition is,

we take an element B and we look up by this equation, what's its origin,

originally is, under f. That's a and a will then

be the image of g. Now the question is whether this is a good definition.

Well, it wouldn't be a good definition if we

wanted to associate a different element for c also to b.

But that cannot happen because if we have b,

we go to this equation and we know,

that's just since the function f is bijective,

that there's exactly one solution to it.

So for every b we've got exactly one a that fits.

And that a we've put in there has

the image of b on a g. And in this way we define a good function.

And this function is called --- g is called

the inverse of f because if f goes from left to right,

then g goes in the inverse direction,

from right to left.

There are, of course,

a lot of inverse functions.

For instance, if f is the function which adds two to number,

then the inverse of f is the function which subtracts two from a number.

If f is a function that multiplies the number by two,

then the inverse is the function which divides the number two.

If f is the function which squares a number,

then f inverse is the number which takes the square root.

But, wait a second. Here we have to pay

attention because we know

that with the square root there's a problem,

the number x is not allowed to be negative.

So here we have to take care of the definition of f. Now what is the problem?

If we are looking to the graph of f,

which we've just drawn, it looks like that.

We see that it is actually not,

if we define it from R to R,

it is not an injective function because if we take any y,

then f(x) is y has two solutions.

If y is bigger than zero and it has

no solution if y is smaller than zero.

So it's neither injective nor surjective.

You can see that graphically.

If y is bigger than zero,

then we get two solutions,

one there, one there.

If y is smaller than zero,

we've got no solutions at all.

So what should we do here?

Now the way to remedy is always change the domain and the range.

So what we do is, we said, well,

f will be from R+ to R+,

and R+ is here the set for real numbers such that x is larger than zero.

For, in that case,

my domain is only here.

That's now my new domain.

This is when you arrange.

And if I'm looking now at my graph I see that for every value of y,

I've got exactly one solution.

So this is this function up here, is not.

I'm sorry, this function is not bijective.

But the function f from R+ to R+ such that f(x)

is x square is bijective and has as inverse square root.

So the way, that the thing to remember about this example is,

if you are in a situation where you're not injective or not surjective,

you often can remedy the situation by restricting domain and range to

a part of the function which is then bijective and where you can define an inverse.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play