kokomocutie88r1

2022-07-15

Discrete math predicate problem
In this problem, we will be using binary predicates F(x, y), G(x, y), etc. to represent functions f, $g:U\to U$, etc., where U is the universe. Thus, F(x, y) holds iff $y=f\left(x\right)$, G(x, y) holds iff $y=g\left(x\right)$, 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$.”

tykoyz

Expert

Explanation:
I'll do the very first one ... see if that helps you get some of the others:
F represents a function:
$\mathrm{¬}\mathrm{\exists }x\mathrm{\exists }y\mathrm{\exists }z\left(F\left(x,y\right)\wedge F\left(x,z\right)\wedge \mathrm{¬}y=z\right)$
or, equivalently:
$\mathrm{\forall }x\mathrm{\forall }y\mathrm{\forall }z\left(\left(F\left(x,y\right)\wedge F\left(x,z\right)\right)\to y=z\right)$
or, equivalently:
$\mathrm{\forall }x\mathrm{\forall }y\left(F\left(x,y\right)\to \mathrm{¬}\mathrm{\exists }z\left(F\left(x,z\right)\wedge \mathrm{¬}y=z\right)\right)$
or, equivalently:
$\mathrm{\forall }x\mathrm{\forall }y\left(F\left(x,y\right)\to \mathrm{\forall }z\left(F\left(x,z\right)\to y=z\right)\right)$

Do you have a similar question?