Was ist der Logarithmus oder die Root-Operation im Typraum?

Ich habe kürzlich Die zwei Dualitäten der Berechnung gelesen: Negative und fraktionale Typen . Das Papier erweitert die Summen- und Produkttypen und gibt den Typen a - bund eine Semantik a/b.

Im Gegensatz zu Addition und Multiplikation gibt es nicht nur eine, sondern zwei Umkehrungen von Potenzierung, Logarithmus und Wurzelbildung. Wenn Funktionstypen (a → b) typtheoretische Exponentiation sind, was bedeutet es angesichts des Typs a → b(oder b^a), den Typ logb(c)oder den Typ zu haben a√c?

Ist es überhaupt sinnvoll, Logarithmen und Wurzeln auf Typen auszudehnen?

Wenn ja, wurden in diesem Bereich Arbeiten durchgeführt, und wie lassen sich die Auswirkungen nachvollziehen?

Ich habe versucht, Informationen dazu über Logik nachzuschlagen, in der Hoffnung, dass die Curry-Howard-Korrespondenz mir helfen könnte, aber ohne Erfolg.

lo.logic pl.programming-languages type-theory algebra efrey
quelle

Antworten:

Ein Typ hat einen Logarithmus zur Basis von von genau dann, wenn . Das heißt, kann als ein Container von Elementen in Positionen gesehen werden, die durch . In der Tat geht es darum zu fragen, zu welcher Potenz wir erhöhen müssen, um zu erhalten . $C$ $X$ $P$ $C \cong P\to X$ $C$ $X$ $P$ $P$ $X$ $C$

Es ist sinnvoll, mit wobei ein Funktor ist, wenn der Logarithmus existiert, was . Beachten Sie, dass, wenn , wir mit Sicherheit , der Container uns also nichts Interessantes sagt als seine Elemente: Container mit einer Auswahl von Formen tun dies keine Logarithmen haben. $\mathop{log}F$ $F$ $\mathop{log}\!_X(F\:X)$ $F\:X\cong \mathop{log}F\to X$ $F\:1\cong 1$

Bekannte Gesetze der Logarithmen sind sinnvoll, wenn Sie in Positionssätzen denken

\begin{array}{rcll} l O G (K 1) & = & 0 & keine positionen im leeren behälter \\ l O G ich & = & 1 & Behälter für eine, eine Position \\ l O G (F \times G) & = & l O G F + l O G G & paar container, wahl der positionen \\ l O G (F \cdot G) & = & l O G F \times l O G G & Container von Containern, Paar von Positionen \end{array}

$\begin{array}{rcl@{\qquad}l} \mathop{log} (\mathop{K}1) &=& 0 & \mbox{no positions in empty container}\\ \mathop{log} I &=& 1 & \mbox{container for one, one position}\\ \mathop{log} (F\times G) &=& \mathop{log}F+\mathop{log}G & \mbox{pair of containers, choice of positions} \\ \mathop{log} (F\cdot G) &=& \mathop{log}F\times\mathop{log}G & \mbox{container of containers, pair of positions} \end{array}$

Wir erhalten auch wobei unter dem . Das heißt, der Pfad zu jedem Element in einigen Codaten wird induktiv durch Iteration des Logarithmus definiert. Z.B, $\mathop{log}\!_X(\nu Y. T) = \mu Z. \mathop{log}\!_X T$ $Z=\mathop{log}\!_XY$

l o g S t r e ein m = l O G_{X} (ν Y. . X \times Y.) = μ Z . 1 + Z = N ein t

$\mathop{log}\mathop{Stream} = \mathop{log}\!_X(\nu Y. X\times Y) = \mu Z. 1 + Z = \mathop{Nat}$

Da die Ableitung den Typ in Ein-Loch-Kontexten und der Logarithmus die Positionen angibt, sollten wir einen Zusammenhang erwarten, und zwar

F 1 ≅ 1 \Rightarrow l O G F ≅ \partial F 1

$F\:1\cong 1 \;\Rightarrow\; \mathop{log}F\cong \partial F\:1$

Wo es keine Formwahl gibt, ist eine Position genau das gleiche wie ein Kontext mit einem Loch, in dem die Elemente ausgerieben sind. Im Allgemeinen steht immer für die Auswahl einer Form zusammen mit einer Elementposition innerhalb dieser Form. $\partial F\:1$ $F$

Ich fürchte, ich habe weniger zu Wurzeln zu sagen, aber man könnte von einer ähnlichen Definition ausgehen und der Nase folgen. Weitere Verwendungen von Logarithmen von Typen finden Sie in Ralf Hinzes "Memofunktionen, polytypisch!". Muss rennen ...

Schweinearbeiter
quelle

Die Antwort von Da Man selbst. Willkommen Conor!

Andrej Bauer

Hmm, ich bin gespannt, was Wurzeltypen sind, da sie Typen mit einer imaginären Einwohnerzahl erfordern würden. Es sei denn, ich liege falsch. Ich werde Ihre Antwort annehmen, aber wenn Sie die Zeit haben, Wurzeln zu erarbeiten, wären Sie sehr dankbar.

Jeffrey

Kann das irgendwie mit der Taylor-Reihe von ln (1 + x) zusammenhängen?

Yatima2975

Mit Logarithmen und Exponentialen frage ich mich ... was brauchen wir, um ein Napier-Objekt zu konstruieren ? (zB das vermeintlich einzigartige Objekt, eso dass ∂e = e)

Rhymoid

Ich kenne keine Arbeit, die diese Linie verfolgt, aber ein paar Momente, in denen ich darüber nachdachte, führten mich zu dieser Hypothese: Wäre die "Wurzel" des Exponentialtyps nicht nur die Codomäne und der "Logarithmus" des Exponentials? Nur die Domain?

Marc Hamann
quelle

Richtig, ich denke deine Intuition ist gut, aber deine Schlussfolgerung ist falsch. Die Root-Operation und die Logarithmus-Operation erhalten Sie, wenn Sie die Codomäne bzw. die Domäne "invertieren", nicht die (Co-) Domäne selbst. Die Frage ist, was wir mit invertieren meinen und was die binäre Typoperation ist, die sie erzeugt.

Jeffrey

Ich bin mir nicht sicher, ob das stimmt. Wenn ich , ist die te Wurzel und der Basis- Logarithmus ist . Die Umkehrung ist von der Operation, nicht von den Komponenten.

x^{y}

$x^y$

y

$y$

x

$x$

x

$x$

y

$y$

Marc Hamann

Entschuldigung, ich war mir in meiner Terminologie nicht ganz sicher. Ich möchte nicht fragen, "was ist die Wurzel, was ist das Ergebnis der Anwendung der Logarithmusfunktion". Ich frage mich, wie das Verwurzeln funktioniert. Wie lautet die Operation zum Finden des Logarithmus? Wenn →es sich um eine Expenentiation handelt, gibt es zwei Typen für die Root-Operation. Was ist zwei Arten unter dem Logarithmus. Was ich mit "das Argument umkehren" meine, ist etwas, für das es hier keine Zeit gibt zu erklären. Ich werde meine Frage klären, danke.

Jeffrey

Das von mir verlinkte Papier enthält eine Semantik für den Typ a - bund den Typ a / b. Es geht mir nicht um das Ergebnis der Reduzierung des Operationslogarithmus und der Wurzel, sondern darum, ihre Semantik als Operatoren vom Typ Binär zu verstehen.

Jeffrey