2
$\begingroup$

Is it possible to prove that there can't be two different inputs produce same output for surjection between same finite set without firstly proving such surjection is also an injection.

I'm asking this because I'm trying to use this result to prove that such surjection is also an injection.

Here's the working proof of injection.

Goal: $∀n ∈ ℕ, ∀ f, f: n ⟹ n → injective f$
Here "f: n ⟹ n" denotes that f is an surjection from n to n.

Prove by induction, n = 0 is true vacuously.

For n = k, assume $∀ f, f: k ⟹ k → injective f$

so we need to prove $∀ f, f: k⁺ ⟹ k⁺ → injective f$

Use exclude middle to $∀p ∈ k, f(p) ∈ k$

Case I: $∀p ∈ k, f(p) ∈ k$

We have $f(k) = k$, or else $f(k) ∈ k$ contradict surjection since nothing maps to k.

So we have $f ↾ k : k ⟹ k$ where "↾" denotes restriction.

By induction hypothesis, $injective (f ↾ k)$

Therefore $f = f ↾ k ∪ \{<k, k>\}$ is injective.

Case II: $¬ ∀p ∈ k, f(p) ∈ k$ which means $∃p ∈ k,f(p) = k$

If we can prove $f(k) ∈ k$,then it can be reduced to Case I by swapping values on k and p.

To prove $f(k) ∈ k$, notice $f(k) ∈ k⁺$

we only need to prove $f(k) ≠ k$ which leads to what title asks.

$\endgroup$
4
  • $\begingroup$ Please use latex via MathJax. See math.meta.stackexchange.com/questions/5020/…. Also, statements of the form $A\rightarrow B\rightarrow C$ require parentheses. $\endgroup$
    – halrankard
    Aug 21, 2020 at 12:57
  • $\begingroup$ Sorry, fixed it $\endgroup$ Aug 22, 2020 at 7:32
  • $\begingroup$ The question is still not very clear. One should be able to fully understand what you are asking without reading the title. Also, the line after "formally" still has misplaced parentheses. It does not say "if a function from $n$ to $n$ is surjective then it is injective". It would be better to just write out what you want to say in words, rather than resorting to this level of formalism, which is hard to read and prone to errors. $\endgroup$
    – halrankard
    Aug 23, 2020 at 12:47
  • $\begingroup$ Many thanks for your replying. I edited the question again. I hope it is clearer then before. $\endgroup$ Aug 24, 2020 at 9:31

1 Answer 1

1
$\begingroup$

I am going to write a direct proof that a surjective function between two finite sets of the same cardinality is injective. After that, I will discuss how it compares to your question and proof attempt.

Following your setup, I treat $n\in\mathbb{N}$ as a finite ordinal; so $n=\{k\in\mathbb{N}:k<n\}$.

Lemma: If $g:n\to n$ is injective, then $g$ is surjective.
Proof: Let $X$ be the image of $g$. Then $g:n\to X$ is a bijection, so $|X|=n$. So $X=n$.

Now we prove the main result. Let $f: n\to n$ be a surjective function. We want show that $f$ is injective. Since $f$ is surjective, for any $k\in n$ there is some $x_k\in n$ such that $f(x_k)=k$. Since $f$ is a function, we know that if $k\neq l$ then $x_k\neq x_l$. So $g:n\to n$ such that $g(k)=x_k$ is an injective function, and therefore is surjective by the Lemma. Finally, suppose $x,y\in n$ and $f(x)=f(y)$. Since $g$ is surjective, we know $x=x_k$ and $y=x_l$ for some $k,l\in n$. So $f(x_k)=f(x_l)$, i.e., $k=l$. So $x=x_k=x_l=y$. Therefore $f$ is injective.

Discussion of your question and proof attempt:

You ask if we can show that two different inputs, say $a$ and $b$, for a function $f$ produce different outputs without first showing that $f$ is injective. Since the definition of injective is "any two distinct inputs produce different outputs", the only way this would be possible is if we had further specific information about $f$, $a$, and $b$. Indeed, if you have an argument that $f(a)\neq f(b)$, which does not use anything special about $f$, $a$, and $b$, then what you have is a proof that $f$ is injective.

I claim that that in your proof, we don't have specific enough information to conclude that the problem you've reduced to is any easier. In your case, we are comparing the following two problems.

  1. For any $k$ and $p\in k$, if $f:k^*\to k^*$ is surjective and $f(p)=k$ then $f(k)\neq k$.

  2. For any $k$ and distinct $a,b\in k^*$, if $f:k^*\to k^*$ is surjective then $f(a)\neq f(b)$.

So (1) is the specific situation you arrive at in your proof, while (2) says "any surjective function from $k^*$ to $k^*$ is injective", which is the general question.

You are asking if (1) is somehow easier to show without showing (2). But I claim that (1) and (2) are essentially equivalent. Indeed, suppose we assume (1). Then, given surjective $f:k^*\to k^*$ and distinct $a,b\in k^*$, choose a permutation $h$ of $k^*$ that sends $p$ to $a$ and $k$ to $b$. Choose another permutation $g$ of $k^*$ that sends $f(a)$ to $k$. Consider $f^*=g\circ f \circ h$. Then $f^*$ is still surjective, and $f^*(p)=k$. So $f^*(k)\neq k$ by (1). Unpacking the choices, this says $g(f(a))\neq g(f(b))$, so $f(a)\neq f(b)$ since $g$ is injective. So we have shown (2).

To summarize, although the question you ask has the cosmetic appearance of being more specific, it is really the same as the general question, after composing by appropriate permutations. Therefore the only recourse you have to continue your proof is a general-type argument for injectivity, like the one I gave above.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .