Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [partial-functions]

Questions on partial functions, history, usage, properties, significance for computability theory, connections to (inverse)-semi-groups and other algebraic theories.

1
vote
3answers
110 views

The use and meaning of the “tilde-equal-symbol” for partial (recursive) functions in Girards monograph 'proof theory and logical complexity, volume 1'

English is not my native language, so please forgive if I do not express myself properly. I am working with the book named above on proof theory, and I have a little problem with the authors use of ...
1
vote
1answer
66 views

Can I give undefined ($\perp$) as an argument to my function?

Hopcroft & Ullman (1979) say that a function $f(x)$ is undefined when $f$ is not defined for $x$ and they use (I think) the $\perp$ symbol to denote that. My question is: since I can use $\perp$ ...
1
vote
2answers
46 views

The logic behind adding this sentence to the second condition in this definition of isomorphism

Below is the definition of isomorphism quoted from the textbook Introduction to Set Theory by Karel Hrbacek and Thomas Jech. First, we introduce relevant definitions: An $n$-ary relation $R$ in $A$ ...
2
votes
1answer
46 views

What equivalence relation is being used to define the category of partial maps?

Here's what Awodey says in his Category Theory. For any category $\mathbf{C}$ with pullbacks, define the category $\mathbf{Par}(\mathbf{C})$ of partial maps in $\mathbf{C}$ as follows: the objects ...
0
votes
2answers
30 views

Directional Derivative with partial function

I have been trying to do this question but I'm completely lost. Be $f(x,y)$ a differentiable function, the maximum value of $Duf$(0,2) is equal to 2 and occurs when $u = (\frac{\sqrt 2}{2},\frac{\...
0
votes
0answers
19 views

Show that if $R(\vec{m},n)$ is a recursive relation, and $f$ is a recursive function, then $R(\vec{m},f(n))$ is a recursive function.

I am currently reading through the text $\underline{\text{Computability Theory}}$ by Barry Cooper, which contains the titular exercise. I'm struggling a bit as, though I am getting a more intuitive ...
4
votes
2answers
76 views

Definition of (lazy) conditional in partial recursive functions

I'm currently working on formalizing the theory of partial recursive functions, and something seems peculiar about the standard definition. The definition of the primitive recursion clause of $\mu$-...
1
vote
0answers
15 views

Anything special on the ratio of partial over total functions?

The number of functions that maps an element in $A$ to another one in $A$ is $|A|^{|A|}$ for finite size of $A$, and the number of partial functions that maps an element in $A$ to another one in $A$ ...
-1
votes
1answer
67 views

Prove that a language A is c.e. iff it is the range of a partially computable function

I am having trouble in formally proving this statement. I looked online and most proofs just mention that it is the part of the definition of c.e (computably enumerable) language.
0
votes
1answer
141 views

The average values of a harmonic function over the ball and surface of the ball are the same?

This is the proof I saw in my text. I can understand all the algebraic manipulations in the proof. But, what I am not sure about is the deriative of the function Φ(r). As far as I know, the average ...
0
votes
0answers
44 views

Function of a function always total

Am I correct into thinking that any function of a function is always total? $$f : A \to B$$ if the range of of function f is all the functions that take two natural numbers and return a natural. My ...
1
vote
1answer
29 views

In what way is a partial function different from a partial transformation when both can always express the other's associated total function?

Using the definition given by wikipedia https://en.wikipedia.org/wiki/Partial_function a partial function $f:X\nrightarrow Y$ is just a function $f:X'\to Y$ for some subset $X'\subseteq X$ analgous to ...
1
vote
1answer
30 views

How do I show that this relation is a partial function?

I don't quite get the definition yet. How do I show that a relation $R : A \mapsto B$ is a partial function iff $R \circ R^{-1} \subseteq id_B$? I'm getting multiple definitions of partial ...
2
votes
1answer
244 views

Example function which is partial, injective, and surjective

Can somebody give an example of a function $f : \mathbb{N} → \mathbb{N}$ which is partial, injective, and surjective. I was thinking about $f(x)=x-1$, but I am not sure if it is surjective.
1
vote
1answer
108 views

Hasse Diagram and Partial Orders

Consider a partial order on piles of 2 black stones and 2 white stones. Say that one configuration of pile of stones,A, is smaller than another,B, if you can join piles ...
1
vote
1answer
61 views

When is the $\mu$ operator a partial function vs. total?

In my computability theory course notes, I have written that, if $f:\mathbb{N}^{n+1} \to \mathbb{N}$ is a partial function, then the function obtained from $f$ by minimisation is the partial function $...
0
votes
0answers
145 views

Is this a total function, a partial function, or just a total, single-valued relation?

Is the following a total function, a partial function or total, single-valued relation? $h: \mathbb{N} \rightarrow \mathbb{N}$, where $h(n) = \Bigg\{0 $ if $n$ is divisible by $2$, $1$ if $n$ is ...
0
votes
1answer
42 views

Extension of definable functions in o-minimal structures

The proof of the following theorem Let $M$ be an o-minimal structure, and let $a,b\in M,A\subseteq dom(M)$. If $a\in acl(b,A)$ and $a\notin acl(A)$, then $b\in acl(A)$. starts like this: ...
1
vote
0answers
54 views

Partial sum of infinite series

In a probability excercise I concluded that the expected value is the following infinite series: $\sum_{i=1}^{\infty} \frac{2i}{2^i}$ I wrote down the first few terms and saw that it converges to 4, ...
2
votes
1answer
70 views

Showing $\mathscr{P}_n=\langle\zeta, \tau, \pi, \xi\rangle$.

This is Exercise 1.9.13 of Howie's "Fundamentals of Semigroup Theory". The Details: Definition: The partial transformation semigroup $\mathscr{P}_n$ is the set of all partial maps from $\{1, 2, \...
1
vote
1answer
55 views

Soft question on notation regarding partial bijections

I'm not sure if the following technicality should just be ignored, or if I should just learn more category theory (of which I know very little), but here it goes anyway. Let $\mathcal{C}$ be the ...
2
votes
1answer
74 views

Union of Partial Functional relations

A relation $R$ is said to be partial functional if for all $x$, if $y R x$ and $y' R x$, then $y=y'$. The union of two relations $R$ and $S$ is defined as follows: $$y (R \cup S) x \iff y R x \text{ ...
0
votes
0answers
304 views

Is this Hasse Diagram correct?

I have the following question Let, A = {{1}, {2}, {3}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {1, 2, 4}, {1, 3, 4}, {1, 2, 3, 4}} and (A, R) is a POSET where R is the partial order a ⊆ b. I have drawn this ...
1
vote
1answer
115 views

Number of Partial Surjective Functions from X to Y

The number of total surjective functions from $X$ to $Y$ is known to be $T = y!\left\{{x \atop y}\right\}$, with $|X|=x, |Y|=y$. However, I am interested in the number $P$ of partial surjective ...
1
vote
3answers
109 views

Which properties of total functions are absent for partial functions?

For a partial function $p:X\to Y$, we have $p^{-1}(A\cap B)=p^{-1}(A)\cap p^{-1}(B)$ $p^{-1}(A\cup B)=p^{-1}(A)\cup p^{-1}(B)$ $p^{-1}(A \setminus B)=p^{-1}(A) \setminus p^{-1}(B)$ $p^{-1}(A \...
4
votes
1answer
207 views

Eager vs. lazy interpretation of recursive functions

One of the ways of defining the set of recursive functions is to define first a language $L$ by induction in the following way: $\mathsf{Z}^1 \in L$; $\mathsf{S}^1 \in L$; $\mathsf{P}^n_k \in L$ for ...