2

Let $P \subset \mathbb{N}$ be a finite index set and suppose that there is a partial function $f:P \to P$, which is undefined for some strict subset of $P$.

Then, suppose I have a function $g: P \to \{ 0, 1 \}$ defined as $$ g(i) = \begin{cases} 0 & f(i) \text{ is undefined} \\ 1 & f(i) \text{ is defined.} \end{cases} $$

What is the formally correct way to denote these predicates? Could $\not \exists f(i)$ and $\exists f(i)$ work?

daw
  • 49,113
  • 2
  • 38
  • 76
cisprague
  • 159
  • 4
    In the context of recursion theory, I have seen $f(x)!\downarrow$ used to mean that $f(x)$ is defined and $f(x)!\uparrow$ to mean that $f(x)$ is undefined. – Clive Newstead Feb 10 '21 at 21:37
  • 2
    $\exists p(i)$ doesn't look right. If these are functions represented as sets of pairs in set theory, then "$p(i)$ is defined" just means $i \in \mbox{dom}(p)$ (and your function $g$ is just the characteristic function $\chi_{\mbox{dom}(p)}$). In other contexts, a modality (like $\uparrow$ and $\downarrow$ in Clive Newstead's comment) might be more appropriate (there are many logics for working with undefined terms). (PS. there is some mix-up between $f$ and $p$ in the question.) – Rob Arthan Feb 10 '21 at 22:31
  • 1
    PPS: I see that an answer proposing $i \in \mbox{dom}(p)$ was posted but later deleted. That answer was perfectly good in the context of the usual representation of functions in set theory. When one writes that $f$ is a partial function from $X$ to $Y$, it is not possible to recover $X$ or $Y$ from the representation of $P$. In making a category out of sets and partial functions, one has to represent the functions as triples $(X, f, Y)$. – Rob Arthan Feb 10 '21 at 22:39
  • Another way to represent partial functions $f : P \to P$ would be in terms of a "full" function $f_{full} : P \to P \sqcup { undef }$; in this representation, you would simply test whether $f_{full}(i) = undef$ or not. – Daniel Schepler Feb 10 '21 at 23:03
  • @RobArthan, the mix-up has been amended. Is there a reason $\exists f(i)$ would not work? Would $\text{dom}(f)$ automatically convey the domain of definition, rather than $P$? – cisprague Feb 11 '21 at 08:12
  • In addition to the cited duplicate question, see Is there any symbol for "undefined"? – Calum Gilhooley Feb 20 '21 at 18:34

0 Answers0