Mathematics Stack Exchange
Mathematics 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.

A partial function generalizes the concept of a function by not requiring that every element of the nominal domain is mapped to an element of the codomain. They became prominent in computability theory, but also have connections to (inverse)-semi-groups and other algebraic theories.

47 questions
5
votes
1 answer

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 all $n, k$ with $n \ge 1$, $1 \le k \le n$; if…
Luca Bressan
  • 6,755
  • 2
  • 19
  • 46
4
votes
1 answer

Can you define functions which are not primitive recursive, yet total, in Type Theory?

Ackermann's function is total but not primitive recursive. Can one define Ackermann's function in Type Theory, ie: Can you define functions which are not primitive recursive, yet total, in Type Theory? [this post was closed] due to being "not…
RFV
  • 140
  • 6
4
votes
2 answers

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$-recursive functions reads as follows (according to…
Mario Carneiro
  • 26,791
  • 4
  • 65
  • 134
3
votes
1 answer

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.
Waseem Anwar
  • 133
  • 4
2
votes
1 answer

Find P if Integrating factor of $x(1-x^2)dy+(2x^2y-y-ax^3)dx=0$ is $e^{\int Pdx}$.

I have seen one method which correctly evaluates $P=\frac{2x^2-1}{x(1-x^2)}$. But I have seen a method that says if $\frac{\frac{\partial M}{\partial y}-\frac{\partial N}{\partial x}}{N}$ is a function of just x ,i.e, it is equal to f(x) then…
Nivedita Chowdhury
  • 79
  • 7
2
votes
0 answers

Analytic Continuation of Fractions

Excuse my lack of expertise, I study natural sciences (physics) and not mathematics so I will be off with my terminology and mathematical vocabulary. Please feel free to poke and build at this idea but I do request at least playing around with it…
Captain HD
  • 49
  • 6
2
votes
3 answers

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 the $\simeq$ symbol. He does not introduce it…
Ettore
  • 487
  • 2
  • 11
2
votes
2 answers

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$ is a subset of $A^n$. Then we write…
Akira
  • 14,801
  • 6
  • 13
  • 43
2
votes
1 answer

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 are the same as those of $\mathbf{C}$, but an arrow…
D. Brogan
  • 3,142
  • 9
  • 18
2
votes
1 answer

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, \dots , n\}$ to itself, together with composition of…
Shaun
  • 42,617
  • 18
  • 62
  • 167
2
votes
1 answer

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{ or } y S x.$$ My question is what conditions must…
IAlreadyHaveAKey
  • 1,205
  • 7
  • 15
2
votes
1 answer

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 functions, that is, elements of $X$ do not necessarily…
doc
  • 1,287
  • 2
  • 9
  • 12
1
vote
1 answer

A pathological partial function with pathological singularities

Motivation I was thinking about how computers should deal with partial functions. An example of such situation: I'm doing arbitrary real number computation and a division by zero must not fall into an infinite loop. This can be accomplished by…
Dannyu NDos
  • 1,619
  • 8
  • 22
1
vote
0 answers

Semilattice of the Left Inverse Hull

This is a follow-up on this post, which is based upon this paper. First, let me set up some definitions, etc. A Semigroup $S$ is said to be an inverse semigroup provided that for every $x \in X$, there exists a unique element $x^{-1}$ such that…
user193319
  • 7,432
  • 4
  • 35
  • 83
1
vote
1 answer

Inverse Semigroups, Partial Bijections, and Semilattice of Idempotents

I have a question about a passage from this paper. First, some definitions A Semigroup $S$ is said to be an inverse semigroup provided that for every $x \in X$, there exists a unique element $x^{-1}$ such that $x^{-1}xx^{-1} = x^{-1}$ and…
user193319
  • 7,432
  • 4
  • 35
  • 83
1
2 3 4