6
$\begingroup$

From wikipedia I obtain the following definition of an injective function :

Let $f$ be a function whose domain is a set $A$. The function $f$ is injective if for all $a$ and $b$ in $A$, if $f(a) = f(b)$, then $a = b$; that is, $f(a) = f(b)$ implies $a = b$.

From this I conclude that a function $f$ is injective if the below statement is true for all $a,b \in A$:

$$f(a)=f(b) \implies a=b$$

My question is: Can I re-formulate the above statement as $f(a)=f(b) \iff a=b$ ?

  • 4
    $a = b \implies f(a) = f(b)$ is already part of the definition of a function since a function assigns exactly one output to each input.2011-10-26
  • 0
    Thus: Yes, your reformulation will also work.2011-10-26
  • 1
    Sivaram: that's not really part of the definition of functions... If $a$ is equal to $b$, then how could possibly $f(a)$ be not equal to $f(b)$? That's waaaay below, in the rules of manipulation of equality. (notice that for all this to make sense one has to define what $f(a)$ is, but even with one-to-many 'functions' it is true that $a=b\implies f(a)=f(b)$!)2011-10-26
  • 0
    Part of the definition of a function is $(a,b) \in f$ and $(a,c) \in f$ then $b=c$. This is *exactly* the condition $a=b$ implies $f(a)=f(b)$.2011-10-26
  • 0
    @Mariano: Well, it's part of the definition that distinguishes functions from among all relations from $A$ to $B$ (the part that says you want for all $a\in A$ and all $b,b'\in B$, if $(a,b),(a,b')\in f$, then $b=b'$)...2011-10-26
  • 1
    @Arturo: but that is a different statement alltogether! :D The meaning of the notation $f(a)$ cannot depend on whether the relation $f$ is or not a function, if the implication $a=b\implies f(a)=f(b)$ is to have sense as part of the definition of what it means for a relation to be a function. I claim that for **any** definition of what the notation $f(a)$ means for a relation $f$ and an element $a$, the implication will hold for all relations.2011-10-26
  • 0
    @Mariano: How do you define a function? Even the simplest word definition sais that we assign to every $x$ ONE element we denote by $f(x)$..... About your claim: what if by $f(a)$ we mean a colection of elements in $B$? My definition is a relation between $A$ and $B$ but is NOT a function... It only becomes a function if I change the range to the parts of $B$.... We always include in the definition, one way or another, that $f(a)$ is ONE element..... What you mean is probably that without this condition, our notion of function would not be well defined,but this means that it has to be part of2011-10-26
  • 0
    I mean *exactly* what I wrote in the comment above yours, user9176. $${}$$I define a function $f$ from $A$ to $B$ as a relation $f\subseteq A\times B$ such that **(i)** $\forall a\in A, \exists b\in B, (a,b)\in f$; **(ii)** $(a,b),(a,b')\in f\implies b=b'$. Now, **if** $f$ is a relation which is a function from $A$ to $B$ and $a\in A$, I define $f(a)$ to be the unique element $b\in B$ such that $(a,b)\in f$. This is not circular at all.2011-10-26
  • 0
    Your second condition is exactly the statement you claim is not the part of the definition ;)2011-10-26
  • 0
    No it is not. Read it and compare it with the implication I object to.2011-10-26
  • 0
    Your (ii) above is exactly what I put in my answer below -- just in different notation. $(a,b),(a,b')\in f$ implies that $b=b'$ is the same as $a=a$ implies that $f(a)=b=b'=f(a)$. Just different notation.2011-10-26
  • 0
    Yes it is exactly the same... Oh well technically if you say that $x=4-2$ you are not saying that $x=2$... You are basically claiming that $(a,b),(a,b')\in f\implies b=b'$ is NOT the same statement as $(a,b),(a',b')\in f \& a=a' \implies b=b'$, but it is.2011-10-26
  • 0
    I will not pursue it, because I have explained the problem above, and I will only repeat myself; this is a very minor point, I only brought it up because it makes my teeth grind every time...2011-10-26
  • 0
    @MarianoSuárez-Alvarez we usually define functions in terms of particular representations of elements. Saying $x=y$ does not mean $x$ and $y$ are the same string of characters. It means they are equivalent under some understood equality. So it is possible to "define" a relation in a way that violates this equality and thus gives a relation which is "not well-defined". [See my example of the numerator "function".]2011-10-26
  • 0
    Last comment, really. @Bill: that is a completely different issue, which has absolutely nothing to do with the definition of what being a function is, which is the subject of this little debate! $${}$$ user9176: **please** be precise when attributing to me claims, I *never* said that «$(a,b),(a,b')\in f\implies b=b'$» is not the same as «$(a,b),(a',b')\in f \& a=a' \implies b=b'$»: I said that that first stament is not the same as «$a=b\implies f(a)=f(b)$».2011-10-26
  • 0
    Ok @MarianoSuárez-Alvarez we'll just have to agree to disagree.2011-10-26
  • 0
    @MarianoSuárez-Alvarez: I see your point. Is the following statement in any sense better than the one I wrote earlier though it is very close to the contra-positive of the previous one "$f$ is a function $\implies$ $\left( f(a) \neq f(b) \implies a \neq b \right)$?2011-10-26

4 Answers 4

4

Yes, but the implication $a=b\Rightarrow f(a)=f(b)$ holds because you have a function. So in a sense it is redundant.

That is, "$f$ is a function" implies "$a=b\Rightarrow f(a)=f(b)$". So $$\begin{align*} f\text{ is an injective function} &\text{is equivalent to } f\text{ is a function and f is injective}\\ &\text{is equivalent to } f\text{ is a function and } f(a)=f(b)\Rightarrow a=b\\ &\text{implies }\Bigl( (a=b\Rightarrow f(a)=f(b))\text{ and }(f(a)=f(b)\Rightarrow a=b)\Bigr)\\ &\text{is equivalent to } f(a)=f(b)\Leftrightarrow a=b. \end{align*}$$ Conversely, since "$f$ is a function and $a=b \Rightarrow f(a)=f(b)$" is equivalent to "$f$ is a function", you also have the implication going the other way provided you know that $f$ is a function.

2

Yes.

Let us see why:

$f$ is a function if:

  1. $f\subseteq A\times B$ for some sets $A, B$. That is the elements of $f$ are ordered pairs.
  2. For all $a\in A$ there exists $b\in B$ such that $(a,b)\in f$.
  3. For every $a\in A$ if $b,c\in B$ such that $(a,b)\in f$ and $(a,c)\in f$ then $b=c$. We then denote this unique $b$ as $f(a)$.

This means that if $x=y$ then $f(x)=f(y)$ by the definition of a function.

Therefore for injective functions, it is enough to require $f(x)=f(y)\Rightarrow x=y$, since by the definition of $f$ as a function we have the other direction.

1

Yes, you can. You can formally prove that if a=b, then f(a)=f(b), where f denotes any unary predicate, as follows:

1 |a=b hypothesis 2 |f(a)=f(a) equality (identity) introduction 3 |f(a)=f(b) equality elimination 1, 2, or replacing "a" on the right by "b" 4 If a=b, then f(a)=f(b) 1-3 conditional introduction 

So, if f also denotes a function, then a=b implies f(a)=f(b). Thus, f(a)=f(b)⟹a=b can get reformulated as f(a)=f(b)⟺a=b

0

Yes. $a=b$ $\Longrightarrow$ $f(a)=f(b)$ means the function $f$ is well-defined.

By definition every function is well-defined.

Example: $f:\mathbb{Q} \to \mathbb{Z}$ "defined" by $f(a/b)=a$ (the numerator "function") is not well-defined since $4/2=6/3$ but $f(4/2)=4$ and $f(6/3)=6$. The same input gave two different outputs. Thus $f$ is not well-defined. It's not a function!

  • 0
    The sentence "$f$ is well-defined" makes no sense: if something is not well-defined, it cannot even be the subject of a sentence. What one *really* means is that "the relation $f$ which we have defined is a function".2011-10-26
  • 1
    And notice that if $f\subseteq X\times Y$ is a any relation whatsoever from $X$ to $Y$ and you define, as usual, for each $x\in X$ that $f(x)=\{y\in I:(x,y)\in R\}$, then it is also true that $x=x'\implies f(x)=f(x')$... so that implication is not characteristic of functions, really.2011-10-26
  • 0
    I stand behind the term "well-defined" -- this is common usage. $f$ and the relation defining $f$ are commonly identified.2011-10-26
  • 0
    @MarianoSuárez-Alvarez I don't follow your second comment. Do you mean that the implication fails to make sure that $f$ is defined for all elements of the domain? I wasn't claiming that "well-defined" is synonymous with "$f$ is a function". It's just part of the definition.2011-10-26
  • 0
    I am saying that for the implication $x=y\implies f(x)=f(y)$ to be part of the definition of a relation being a function, then the symbol $f(x)$ has to be defined for all relations, not just functions (for otherwise the definition wouldbe circular) I claim that for any definition you give of what $f(x)$ means for a relation $f\subseteq X\times Y$ and an element $x\in X$, the implication will hold independently of whether the relation is or not a function.2011-10-26
  • 0
    The usage is $(x,y) \in f$ then we say $f(x)=y$. So if $f$ is not a function it is possible that $(x,y),(x,z) \in f$ with $y \not= z$ so that $f(x) \not= f(x)$. This is case where "$f(x)$" is not *well-defined*.2011-10-26
  • 0
    If you want to use that definition of $f(x)$, then the implication $x=y\implies f(x)=f(y)$ simply cannot be part of the definition of 'function'. That is my point :)2011-10-26
  • 0
    Can we all agree that $x=y\Longrightarrow f(x)=f(y)$ follows from the axiomatic definition of _equality_? In general we can conclude $E[x]=E[y]$ from $x=y$ for any symbolic context $E[\cdot]$. A notation $E[\cdot]$ that doesn't allow this is not only not a function; it is not a logically meaningful notation _at all_.2011-10-26