Questions tagged [partial-functions]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
24 views

Function vs Partial Function

Generally speaking, can we say that "any function is a partial function"? I know what is exactly a partial function, but is it correct to imply that arbitrary function can be seen as a ...
-1
votes
0answers
15 views

Partial Functions and Relations

Is it possible to infer that "Any function is a partial function" is true? If not, what are some counterexamples for that (for example, $f(x) = \frac{1}{x}$)? I know that any partial ...
0
votes
1answer
29 views

Confusion regarding Computability and Recursion

I'm reading about Computability and so far I have found it a bit difficult to understand, given that I have a narrow mathematical background, and that often times I would find different names for the ...
1
vote
1answer
31 views

Number of bijective partial functions between two finite sets?

Suppose we have two finite sets $A, B.$ If we are to create a partial function $A\to B,$ for each $a\in A$ we have $|B|+1$ choices for the image of $a.$ Hence there must be $(|B|+1)^{|A|}$ partial ...
0
votes
0answers
25 views

Family of unary partial computable functions having total computable extension is computable.

I have to prove: Family of unary partial computable functions having total computable extension is computable. But it is not so obvious for me. Here i provide some definitions: If the function $h$ ...
1
vote
1answer
34 views

How can I show that a computably enumerable set is the range of a partial computable function

In recursion theory, by definition, a computably enumerable set (c.e.) is the range of a total computable function. However, I came across a textbook which asks to show how a c.e. set can also be the ...
0
votes
1answer
27 views

How to represent sections in math notation? E.g. (_ + 3)

Functional programming languages have the concept of sections where they can partially apply a function that is represented by an operator. For instance, one can define a function that always adds ...
1
vote
2answers
39 views

Equivalence Relations and Partial Order - Symmetry and Anti-Symmetry

I am confused on how to check symmetry and anti symmetry I came to a conclusion that '==' is symmetric, but can it be anti-symmetric? '>=' function is reflexive and transitive. But I cannot determine ...
1
vote
1answer
271 views

Inverse Laplace with a irreducible quadratic in the denominator and a 1 in the numerator

Please help me find the Inverse Laplace transform of: $$F(s) = \frac{1}{s(s^2+8s+4)}$$ After completing the square, I obtained $$F(s) = \frac{1}{s((s+4)^2-12)}$$ Thank you.
1
vote
0answers
39 views

Equivalence of various notions of injectivity for partial functions

Let $A$ and $B$ denote sets. Definition. Given a partial map $f : A \rightarrow B$, let us define that a partial inverse of $f$ is any partial map $g : B \rightarrow A$ satisfying $$fg \leq \mathrm{...
1
vote
3answers
413 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
67 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
55 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
77 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
35 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{\...
4
votes
2answers
105 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
22 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
170 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
348 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 ...
1
vote
1answer
57 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
62 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 ...
3
votes
1answer
584 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
147 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
93 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
236 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
61 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
56 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
87 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
85 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
145 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
825 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
151 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
148 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
266 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 ...