Understanding Computer Code to Test for an Injective Function

Question

I'm learning about types of function in discrete maths. I like to learn by exploring concepts through computer code. I came across the following code purporting to determine whether a function is injective:

def is_injective(function):
    # Check if the function is injective (one-to-one)
    codomain_set = set(function.values())
    return len(codomain_set) == len(function)

# Example usage
domain = ["A","B","C"]  # Replace with your domain
codomain = [1,2,3,4]  # Replace with your codomain

function = {
    "A": 1,  # Replace with your function mapping
    "B": 2,  # Replace with your function mapping
    "C": 4,  # Replace with your function mapping
}

if is_injective(function):
    print("The function is injective (one-to-one).")

I'm having a bit of trouble understanding how this works or whether it is correct. In is_injective(), codomain_set seems to create a set from the function values (which I think represent the range?). I assume creating a set is to remove duplicates.

However, I'm not seeing how comparing a set comprising the range values to the number of values from the domain in the mapping is equivalent to the standard mathematical definition of an injective function.

Can anyone please provide some clarification?

Answer 1

The way I see this is function is an array of something like this.

function = ((1,A),(2,B),(3,C),(4,B)) [not injective as function.2 = function.4 = B]

Then function.values() is a list (A,B,C,B). A list can have multiple objects.

set() is a function that turns the list into a set that can not have multiple objects. So set(A,B,C,B) will return (A,B,C)

Now function has length 4. And function.values() has length 4. but codomain_set = (A,B,C) has length 3 so the they are inequal. The only way that can happen is if function.values() had repeated elements that got stripped. And that means the function was not injective.

On the other hand if the function = ((1,A),(2,B), (3,C), (4,D)) and was injective then function.values = (A,B,C,D) has no repeated values. So set(A,B,C,D) will return (A,B,C,D) and nothing is stripped and function, function.values(), and codomain_set=set(function.values()) will all be equal to 4.

So despite my initial critique of this being bad code and useless, I've changed my mind and now think it is valid.

...... but it does depend on the coding language (which must have a set() function that strips out repeated list terms.

======

Now this will ONLY work on functions with finite domains. Infinite domains we could easily have $f:\mathbb Z \to \mathbb Z$ $f(x) = x^2$ were the domain is $\mathbb Z$ and function.values() is $\{....,16,9,4,1, 0 , 1, 4, 9, 16,....\}$ and set(function.values) DOES strip it to $\{0,1,4,9,16,.....\}$ and but we the length of both even after stripping are both equal and infinite.

....

Then again... I can only program finite domains anyway, I think.

Answer 2

Since I am not able to add comments, I will post this as an answer.

As you probably know, the standard definition of injectivity is: $$x_1 \ne x_2 \implies f(x_1) \ne f(x_2)$$

The "codomain_set" in your code seems to be taking the values of each element that goes through the function (i.e len(function)). If those are equal then the function must yield different values for different elements.

If, for example $f(A)=4=f(B)$, then this $4$ element will be counted just once, while A and B are two different elements. This gives two different cardinals of those sets.

Answer 3

Making some (hopefully) reasonable assumptions about what function.values() and len(function) do, your understanding of the code seems correct. Correctness of the function itself then follows from the following observation that $f\colon X \to Y$ where $X$ is a finite set is injective iff $|X| = |f(X)|$: Clearly $|X| = |f(X)|$ if $f$ is injective since it matches elements of the domain uniquely to elements of its range, whereas if $|X| = |f(X)|$ and you assume that $f$ is somehow not injective, you can find some $y \in f(X)$ with $|f^{-1}(\{y\})| \geq 2$; but if you then consider $f|_{X \setminus \{x\}}\colon X \setminus \{x\} \to f(X)$ for some choice of $x \in f^{-1}(\{y\})$ you'll have a surjection from a set of cardinality $|f(X)| - 1$ onto one of strictly greater cardinality $|f(X)|$ which is absurd, which is to say that $f$ must have been injective in the first place.