EDB — 01P

Exercises

1. [01P] (Solved on 2022-11-15) Let \(D,C\) be non-empty sets. A partial function from \(D\) in \(C\) is a function \(𝜑:B→ C\) where \(B⊆ D\). (The definition of ”function” is in [1Y6]↺↻).

   It can be convenient to think of the partial function as a relation \(Φ⊆ D× C\) such that, if \((x,a),(x,b)∈ Φ\) then \(a=b\) (see [23X]↺↻). The two notions are equivalent in this sense: given \(Φ\) we build the domain of \(𝜑\), which we will call \(B\), with the projection of \(Φ\) on the first factor i.e. \(B=\{ x∈ D : ∃ c∈ C, (x,c)∈Φ\} \), and we define \(𝜑(x)=c\) as the only element \(c∈ C\) such that \((x,c)∈Φ\); vice versa \(Φ\) is the graph of \(𝜑\).

   Partial functions, seen as relations \(Φ\), are of course sorted by inclusion; equivalently \(𝜑≤ 𝜓\) if \(𝜑:B→ C\) and \(𝜓:E→ C\) and \(B⊆ E⊆ D\) and \(𝜑=𝜓_{|B}\).

   Let now \(U\) be a chain, i.e. family of partial functions that is totally ordered according to the order previously given; seeing each partial function as a relation, let \(Ψ\) be the union of all relations in \(U\); show that \(Ψ\) is the graph of a partial function \(𝜓:E→ C\), whose domain \(E\) is the union of all the domains of the functions in \(U\), and whose image \(I\) is the union of all images of functions in \(U\)

   If moreover all functions in \(U\) are injective, show that \(𝜓\) is injective.

   Solution 1

   [01Q]↺↻