What are One-to-One, Onto and Bijective functions?
Posted on 21.02.2010 11:43 pm
Last fall I started learning Discrete Mathematics and I've wanted to go over a few of the more fun things that it teaches.
A lot of what Discrete Math teaches does not require a high understanding of mathematics so hopefully I'll be able to shed some light on some of these subjects.
In both math and programming, functions have a lot of properties that are fun to go over. Just a quick note about functions, for those who don't know what they are. You can think of a function as a thing that performs some action. Functions usually have some input and some output, but that is not a requirement.
A quick example of a function. You can think of the plus (+) operator in arithmetic as a function. It takes in two numbers as an input and outputs their added value, how it does that is not important for us in this entry, and how other functions work is not something we care about, they just perform magic. It's their properties that we are interested in.
A One-to-One function (or an Injective function) is when one input has a unique output. This means that if a function f has the input 3 and the output 5, usually denoted like this f(3) -> 5 then the output of that function is unique for that input. So no matter what other numbers we would put into that function, we would only get 5 with 3 as the input.
This f() of ours could be implemented like this. (Though this is not One-to-one due to overflow, but shown as an example)
int f(int x)
{
return x + 2;
}
One slight note about One-to-One functions, that it is ok not to be able to get a certain value from a One-to-One function. But in a Onto function, that is not ok.
An Onto function (or a Surjective function) is when you can create every possible output value with the input values. In this case it's ok for duplicate input values to return the same output value, but it's not ok for a function to not be able to return a value in it's domain.
An example of a surjective function is floor and ceiling functions. Their input domains could be rational numbers but the output domain could be integers.
A Bijective function is when a function is both Onto and One-to-One.
So here we have a One-to-One correspondence, where one input value correspondence to one output value, and the Onto property of being able to express every value in the domain through that function. So here a floor or ceiling function would not work, since two or more input values can express the same output value. This is often called a Perfect One-to-One correspondence.
So when you are creating your function, think about it's property, since these properties pop up in all sorts of fun places later on.
0 5 Like it or hate it? - Comment (0)
Process time: 0.009365 seconds
