Discrete math predicate problem

Question

In this problem, we will be using binary predicates F(x, y), G(x, y), etc. to represent functions f, g : U → U, etc., where U is the universe. Thus, F(x, y) holds iff y = f(x), G(x, y) holds iff y = g(x), etc.

1. Write predicate statements that expresses the following facts:
   • F represents a function.
   • F represents a one-to-one function.
   • F represents an onto function.
   • F and G represent inverse functions of one another.
   • H represents the composition function $f \circ g$.
2. Use binary predicates representing functions to give formal proofs (in the style of Sec 1.6 of the following statements:
   • “If f and g are one-to-one functions, then so is $f \circ g$.”
   • “If f and g are onto functions, then so is $f \circ g$.”

Answer 1

I'll do the very first one ... see if that helps you get some of the others:

$F$ represents a function:

$\neg \exists x \exists y \exists z (F(x,y) \land F(x,z) \land \neg y = z)$

or, equivalently:

$\forall x \forall y \forall z ((F(x,y) \land F(x,z)) \rightarrow y=z)$

or, equivalently:

$\forall x \forall y (F(x,y) \rightarrow \neg \exists z ( F(x,z) \land \neg y = z))$

or, equivalently:

$\forall x \forall y (F(x,y) \rightarrow \forall z ( F(x,z) \rightarrow y = z))$