Content deleted Content added
→top: there is no *particular* (Goedel number for) a recursive function such that no algo can decide if it's total -- rather, no algo can decide totality correctly for *all* such functions |
Undid revision 1127436695 by 2601:547:501:8F90:413B:B4AA:7440:58B0 (talk) disagree that this was unnecessary |
||
Line 44:
== Function spaces ==
The set of all partial functions <math>f : X \rightharpoonup Y</math> from a set <math>X</math> to a set <math>Y,</math> denoted by <math>[X \rightharpoonup Y],</math> is the union of all functions defined on subsets of <math>X</math> with same codomain <math>Y</math>:
: <math>[X \rightharpoonup Y] = \bigcup_{D \subseteq{X}}
the latter also written as <math display="inline">\bigcup_{D\subseteq{X}} Y^D.</math> In finite case, its cardinality is
: <math>|[X \rightharpoonup Y]| = (|Y| + 1)^{|X|},</math>
because any partial function can be extended to a function by any fixed value <math>c</math> not contained in <math>Y,</math> so that the codomain is <math>Y \cup \{ c \},</math> an operation which is injective (unique and invertible by restriction).
| |||