Hide

Problem E
Functional Fun

A mathematical function is something that takes each object (like a number) from a set of possible values (called the domain), and produces a single object (again, perhaps a number) from another set of possible values (called the codomain). Functions can be defined over any domain and any codomain.

In this problem we will be looking at partial functions, which map some subset of the elements of the domain to the co-domain. For instance, $f(x) = \sqrt {x}$ is a partial function but not a function on the domain of real numbers, since it only defined for the non-negative numbers.

There are two key properties a partial function may have.

  • A partial function can be injective (or one-to-one), which means that any value in the codomain can be produced by at most one value from the domain. The function $f(x) = x^2$ is not injective if we define its domain and codomain both as the real numbers (since $3^2 = 9$, but also $(-3)^2 = 9$). However, if we define its domain as the non-negative real numbers, then it is injective.

  • A partial function can be surjective (or onto), which means that every value in the codomain can be produced by the function. If we define both the domain and the codomain of the example $f(x) = x^2$ to be all real numbers, then $f(x)$ is not surjective, because it cannot produce negative numbers with the given domain.

If a function is both injective and surjective, then it is called bijective. In this problem, we will analogously define a partial function to be bijective if it is both injective and surjective (but note that this is not standard terminology – a more common definition is to drop the surjectivity requirement and say that a partial function is bijective if it is injective).

Here are visual examples of different types of partial functions:

An injective (but not surjective) partial function that is not a function:
\includegraphics[width=2.5in]{injection}
A bijective partial function that is also a function:
\includegraphics[width=2.5in]{bijection}
A surjective (but not injective) function:
\includegraphics[width=2.5in]{surjection}
Neither injective nor surjective:
\includegraphics[width=2.5in]{neither}

For this problem, write a program which determines if some descriptions are partial functions or not. A description is a partial function if each object in the domain is associated with at most one object in the codomain. For each function, determine if it is injective, surjective, bijective, or neither injective nor surjective.

Input

Input contains a sequence of at most $200$ descriptions. Each description starts with two lines that describe the domain and codomain, given as space-separated alphanumeric tokens. The words “domain” and “codomain” are always the first words on these lines and are not part of the sets, they are for readability. The next line contains the number of mappings $0 \leq n \leq 40$. The next $n$ lines each contain one mapping in the form x -> y which indicates that x from the domain maps to y in the codomain (x and y are drawn from the domain and codomain for the description). Input ends at end of file.

Output

For each description that is a partial function, print bijective, surjective, injective, or neither injective nor surjective depending on what type of partial function it is. For each description that is not a partial function, print not a function.

Sample Input 1 Sample Output 1
domain 1 2 3 4 5
codomain 1 4 16
3
1 -> 1
2 -> 4
4 -> 16
domain 1
codomain 0 1
2
1 -> 1
1 -> 0
domain apple banana pear kiwi
codomain house cat car
4
kiwi -> cat
apple -> house
banana -> cat
pear -> car
domain john mary fred
codomain 1 2 3 4
2
john -> 4
mary -> 2
domain i like to program
codomain what about you
2
like -> you
program -> you
bijective
not a function
surjective
injective
neither injective nor surjective

Please log in to submit a solution to this problem

Log in