Erro menor em computabilidade, complexidade e idiomas?

No livro Computability, complexidade e Línguas (2 ^nd edição), Martin Davis escreve no capítulo 1 (Preliminares), Seção 2 (Funções):

Uma função parcial de um conjunto é simplesmente uma função cujo domínio é um subconjunto de . Um exemplo de função parcial em é dado por , onde o domínio de é o conjunto de quadrados perfeitos. $S$ $S$ $\mathbb{N}$ $g(n) = \sqrt n$ $g$

Até agora, tão simples. Mas ele segue em frente e escreve algumas linhas mais tarde, no final da seção:

Às vezes, nos referiremos à idéia de fechamento . Se é um conjunto e é uma função parcial em , então é fechada sob se a gama de é um subconjunto de . Por exemplo, está fechado em , mas não está fechado em ( onde é uma função total em ). $S$ $f$ $S$ $S$ $f$ $f$ $S$ $\mathbb{N}$ $f(n) = n^2$ $h(n) = \sqrt n$ $h$ $\mathbb{N}$

Portanto, na primeira citação, em é um exemplo para uma função parcial , enquanto na segunda citação a mesma função é um exemplo para uma função total . $\sqrt n$ $\mathbb{N}$

Ambos os exemplos parecem se contradizer. Ou estou faltando alguma coisa em relação aos fechamentos aqui?

mathematical-foundations Orgulho Nerd de Boa Noite
fonte

Este é pedagogicamente um mau exemplo de uma função parcial, porque o domínio é restrito apenas por definição arbitrária . Um exemplo melhor de uma função parcial é f (x) = 1 / x , que é indefinido quando x = 0.

Curinga

@Wildcard: Como isso é arbitrário? não é uma escolha estranha para a gama de ..

N

$\mathbb{N}$

g (n)

$g(n)$

MSalters

@MSalters, nethertheless é uma escolha como arbitrária .

Good Night Nerd Pride

@GoodNightNerdPride: Se você usar essa lógica, não é um exemplo melhor, porque existem intervalos (por exemplo, linha real projetada estendida) nos quais isso também é definido.

1 / x

$1/x$

MSalters 9/09/16

@Wildcard Não é arbitrário. definida como uma função de a , que é um objeto completamente natural. A função é indefinida em certos lugares porque, por exemplo, não existe um número natural tal que . É exatamente igual ao seu exemplo: é muito natural ter uma função de a , e a função que você escolheu é indefinida em alguns lugares porque, por exemplo, não há um número real tal que .

g

$g$

N

$\mathbb{N}$

N

$\mathbb{N}$

y

$y$

y^{2} = 2

$y^2=2$

R

$\mathbb{R}$

R

$\mathbb{R}$

y

$y$

y \cdot 0 = 1

$y\cdot0=1$

David Richerby

Respostas:

Não há contradição aqui. O primeiro caso define a função parcial dada por Como o texto diz, "o domínio de é o conjunto de quadrados perfeitos". $g\colon \mathbb{N}\to\mathbb{N}$

g (n) = {\begin{cases} x & if x \in N and x^{2} = n \\ undefined & if no such x exists. \end{cases}

$g(n) = \begin{cases} x &\text{if $x\in\mathbb{N}$ and }x^2=n\\ \text{undefined} &\text{if no such $x$ exists.} \end{cases}$

g

$g$

O segundo caso define a função total dada por O domínio de é o conjunto de todos os números naturais. $h\colon\mathbb{N}\to\mathbb{R}$

h (n) = x if x \in R_{\geq 0} and x^{2} = n .

$h(n) = x \quad \text{if }x\in\mathbb{R}_{\geq 0} \text{ and } x^2=n\,.$

h

$h$

Você diz que essas são as mesmas funções, mas não são. é indefinido, mas é definido (e igual a ). associa uma raiz quadrada a todo número natural, mas associa raízes quadradas a números naturais que são quadrados perfeitos. $g(2)$ $h(2)$ $\sqrt{2}$ $h$ $g$

$\mathbb{N}$ é fechado em porque, sempre que é definido, . não está fechado em porque, por exemplo, mas . $g$ $g$ $g(n)\in\mathbb{N}$ $\mathbb{N}$ $h$ $2\in\mathbb{N}$ $h(2)\notin\mathbb{N}$

David Richerby
fonte

+1, embora eu ache que o livro está errado quando usa " é uma função parcial em " para significar " é uma função parcial de para algum conjunto".

f

$f$

S

$S$

f

$f$

S

$S$

ruakh 9/09/16

@ruakh O que há de errado nisso?

David Richerby

Na minha experiência, a menos que você adicione explicitamente um modificador como "valor real" (para que o codomain seja claro), uma função em um conjunto é uma função desse conjunto para si mesma (analogamente à maneira como uma relação em um conjunto é uma relação desse conjunto para si mesmo). Mas talvez isso não seja um erro, e é apenas uma tradição terminológica diferente?

ruakh 9/09/16

No segundo exemplo, é definido para todos os números naturais ; quando não é um quadrado, é uma quantidade irracional e, em particular, não é um número natural. $h(n)$ $n$ $n$ $h(n)$

Em outras palavras, o conjunto de números naturais não é fechado sob raízes quadradas: por exemplo, não é um número natural. $\sqrt{2}$

Yuval Filmus
fonte

Desculpe, acho que não estava suficientemente claro. Consulte o segundo ao último parágrafo que adicionei à minha pergunta.

Good Night Nerd Pride

@GoodNightNerdPride Acho que Yuval está exatamente certo. No primeiro exemplo, a função raiz quadrada é uma função parcial de a ; no segundo exemplo, é uma função total de a .

N

$\mathbb{N}$

N

$\mathbb{N}$

N

$\mathbb{N}$

R

$\mathbb{R}$

David Richerby