Predicate logic for statements about functions?

Question

Given the relation $R$ defined on the cartesian map $A\times A$ where $|A|=n$.

How to use the predicate logic to express the statements about functions?

Examples.

1. The relation R corresponds to a function from A to A.
2. The relation R corresponds to an injective function from A to A.
3. The relation R corresponds to and bijective function from A to A.

where for each part above respectively I think them as

1. $\forall a\in A$, there exist $c\in A,s.t.(a,b)\in R$.
2. $\forall a,b\in A$, there exist $c,d\in A,s.t. (a,c),(b,d)\in R\& (a\ne b\to c\ne d)$
3. i8t is surjective with the statement in ii).

Are the above interpretations right?

Answer 1

No, they aren't:

The first statement you wrote would be satisfied if the set $A$ were ${1,2}$ and $R$ were defined as ${(1,1),(1,2),(2,2)}$. That is, you need to require also that $b$ is unique.

For the second statement, I think you almost have it but I've usually seen it phrased the other way, that is you start by asserting that $R$ is a function, (using what you said for the first statement) and then say that $c=d \to a=b$. But if you fix your first statement, your way works too.

For the third statement, yes, I'd just say the second statement and surjective (which is just $\forall b \in A, \exists a \in A {\rm s.t.} (a,b) \in R$ )

Answer 2

Not exactly.

i) $\phi:=$"$\forall a\,\exists b:aRb\land \,\big(\forall c: (aRc\Rightarrow b=c)\big)$"
ii) $\psi:=\phi\land$ "$\forall a,b,c: (aRc\land bRc)\Rightarrow (a=b)$"
iii) $\vartheta:=\psi\land$ "$\forall b\,\exists a: aRb $"

Answer 3

Let $=$ be the equality predicate. Then the relation $R$ is a function if $$ \forall x \forall y \forall z: ((x, y) \in R \land (x, z) \in R) \to (y = z). $$ It is a total function if it is a function and $$ \forall x \exists y: x \in A \to (x, y) \in R. $$ Usually we omit "total" and assume that all "functions" are total. (Those that are not total are given the adjective "partial".) So I believe you need both statements in your problem.

In order for $R$ to be an injective function, it must be a (total) function and satisfy $$ \forall x \forall y \forall z: ((x, z) \in R \land (y, z) \in R) \to (x = y). $$

Finally, in order for $R$ to be a bijective function, it has to be injective and satisfy $$ \forall y \exists x: y \in A \to (x, y) \in R. $$

If your quantifiers are always over $A$, predicates for surjectivity and totality can be shortened a little bit. Here's the summary:

• Well-defined: $\forall x \forall y \forall z: ((x, y) \in R \land (x, z) \in R) \to (y = z)$
• Total: $\forall x \exists y: (x, y) \in R$
• Injective: $\forall x \forall y \forall z: ((x, z) \in R \land (y, z) \in R) \to (x = y)$
• Surjective: $\forall y \exists x: (x, y) \in R$
• Being a (total) function: Total and well-defined
• Being an injective (total) function: Total, well-defined and injective
• Being a bijection: Total, well-defined, injective and surjective