Predicates about functions in 1st order logic

Question

Given the usual definition of function as a subset of $ D \times C $. What is the correct way to write "All functions $ f $ from $ D $ to $ C $ have property $P(f)$". This is both a question about notation but also can I make statements like this safely without my logic becoming second order?

Answer 1

Presumably you mean in the first order language of set theory, involving the single predicate "$\in$". You need to be able to talk about unordered pairs, ordered pairs using the definition $\{u,\{u,v\}\}$, notions derived from these, and more.

To express "all functions $f$ from $D$ to $C$ have property $P(f)$", first we need to be able to express "$f$ is a function from $D$ to $C$". This requires being able to talk about ordered pairs. It's helpful to define a couple of predicates. First, $$\begin{align} \operatorname{IsOrderedPair}(p) := \exists x\,\exists y\, (p = \{x, \{x,y\}\}. \end{align}$$ As a convenience, let's define a notation for the ordered pair of $x$ and $y$: $$ \langle x,y\rangle := \{x, \{x,y\}\}. $$ One more predicate definition: $$ \operatorname{IsSecond}(p,y) := \exists x \,(p = \langle x,y\rangle). $$ (It turns out that we don't need an $\operatorname{isFirst}$ predicate.)

Now we can define $$ IsFunction(f,D,C) := \forall p\,(p\in f\to \\ [\, \operatorname{IsOrderedPair}(p) \\ \land \forall x\,(x\in D \leftrightarrow \exists y\, \langle x,y\rangle\in f)\\ \land \forall y\,(\operatorname{IsSecond}(p,y)\to y\in C ) \\ \land \forall x,y,z\, (\langle x,y\rangle\in f\land \langle x,z\rangle\in f\to y=z) \, ]) $$

Finally, the phrase in your question can be symbolized as follows: $$ \forall f\,[\operatorname{IsFunction}(f,D , C) \to P(f)] $$