Namespaces
Variants
Actions

Difference between revisions of "Gödelization"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Created page with "{{MSC|68P05}} {{TEX|done}} A <i>Gödelization</i> or <i>Gödel numbering</i> of a $\Sigma$-algebra $A$ is a pair $(C,\beta)$ with $C$ a...")
 
m (→‎References: + ZBL link)
Line 14: Line 14:
 
==References==
 
==References==
  
{|
+
* {{Ref|W90}}| M. Wirsing, "Algebraic Specification", in J. van Leeuwen, "Handbook of Theoretical Computer Science", Elsevier 1990 {{ZBL|0900.68309}}
|-
 
|valign="top"|{{Ref|W90}}||valign="top"| M. Wirsing: "Algebraic Specification", in J. van Leeuwen: "Handbook of Theoretical Computer Science", Elsevier 1990
 
|-
 
|}
 

Revision as of 07:50, 21 March 2023

2020 Mathematics Subject Classification: Primary: 68P05 [MSN][ZBL]

A Gödelization or Gödel numbering of a $\Sigma$-algebra $A$ is a pair $(C,\beta)$ with $C$ as a recursive $\Sigma$-number-algebra and $\beta\colon A \longrightarrow C$ as a $\Sigma$-algebra-morphism from $A$ onto $C$. As usual, $\Sigma$ designates a signature. A Gödelization could be understood as encoding of the elements of $A$ by natural numbers [W90].


Gödelizations with bijective mapping $\beta$ are of special interest. They are the counterpart of a certain bijective coordinatisation mapping $\nu\colon C \longrightarrow A$. More precisely, $\beta=\nu^{-1}$ is the inverse of $\nu$ in this case. For a sensible signature $\Sigma$ and a term-generated $\Sigma$-algebra $A$, such a coordinatization with bijective mapping $\nu$ always exists. Taking together, every Gödelization induces canonically a corresponding coordinatization and vice versa.

The correspondence between Gödelization and coordinatization can be extended to congruences defined on $A$ and $C$. A congruence $\sim^\beta \subseteq A \times A$ induces a congruence $\sim^\nu \subseteq C \times C$ and vice versa via $\beta$ resp. $\nu$ [W90].

As one can easily see, a Gödelization with bijective mapping $\beta$ does not always exist. As a simple counterexample take a $\Sigma$-algebra $A$ with an uncountable number of elements.

References

  • [W90]| M. Wirsing, "Algebraic Specification", in J. van Leeuwen, "Handbook of Theoretical Computer Science", Elsevier 1990 Zbl 0900.68309
How to Cite This Entry:
Gödelization. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=G%C3%B6delization&oldid=53054