|
|
| Line 1: |
Line 1: |
| {{Distinguish|Gamma function}}{{refimprove|date=September 2012}} | | {{For|numberings of the set of computable functions|Numbering (computability theory)}} |
|
| |
|
| {{Infobox probability distribution 2
| | In [[mathematical logic]], a '''Gödel numbering''' is a [[function (mathematics)|function]] that assigns to each symbol and [[well-formed formula]] of some [[formal language]] a unique [[natural number]], called its '''Gödel number'''. The concept was used by [[Kurt Gödel]] for the proof of his [[Gödel's incompleteness theorems|incompleteness theorems]]. ({{harvnb|Gödel|1931}}) |
| | name =Gamma
| |
| | type =density
| |
| | pdf_image =[[Image:Gamma distribution pdf.svg|325px|Probability density plots of gamma distributions]]
| |
| | cdf_image =[[Image:Gamma distribution cdf.svg|325px|Cumulative distribution plots of gamma distributions]]
| |
| | parameters =
| |
| * ''k'' > 0 [[shape parameter|shape]]
| |
| * θ > 0 [[scale parameter|scale]]
| |
| | support =<math>\scriptstyle x \;\in\; (0,\, \infty)</math>
| |
| | pdf =<math>\frac{1}{\Gamma(k) \theta^k} x^{k \,-\, 1} e^{-\frac{x}{\theta}}</math> | |
| | cdf =<math>\frac{1}{\Gamma(k)} \gamma\left(k,\, \frac{x}{\theta}\right)</math>
| |
| | mean =<math>\scriptstyle \mathbf{E}[ X] = k \theta </math><br /><math>\scriptstyle \mathbf{E}[\ln X] = \psi(k) +\ln(\theta)</math><br />(see [[digamma function]])
| |
| | median =No simple closed form
| |
| | mode =<math>\scriptstyle (k \,-\, 1)\theta \text{ for } k \;{\geq}\; 1</math>
| |
| | variance =<math>\scriptstyle\operatorname{Var}[ X] = k \theta^2 </math><br/><math>\scriptstyle\operatorname{Var}[\ln X] = \psi_1(k)</math><br />(see [[trigamma function]])
| |
| | skewness =<math>\scriptstyle \frac{2}{\sqrt{k}}</math>
| |
| | kurtosis =<math>\scriptstyle \frac{6}{k}</math>
| |
| | entropy =<math>\scriptstyle \begin{align}
| |
| \scriptstyle k &\scriptstyle \,+\, \ln\theta \,+\, \ln[\Gamma(k)]\\
| |
| \scriptstyle &\scriptstyle \,+\, (1 \,-\, k)\psi(k)
| |
| \end{align}</math>
| |
| | mgf =<math>\scriptstyle (1 \,-\, \theta t)^{-k} \text{ for } t \;<\; \frac{1}{\theta}</math>
| |
| | char =<math>\scriptstyle (1 \,-\, \theta i\,t)^{-k}</math>
| |
| | parameters2 =
| |
| * α > 0 [[shape parameter|shape]]
| |
| * β > 0 [[rate parameter|rate]]
| |
| | support2 =<math>\scriptstyle x \;\in\; (0,\, \infty)</math>
| |
| | pdf2 =<math>\frac{\beta^\alpha}{\Gamma(\alpha)} x^{\alpha \,-\, 1} e^{- \beta x }</math>
| |
| | cdf2 =<math>\frac{1}{\Gamma(\alpha)} \gamma(\alpha,\, \beta x)</math>
| |
| | mean2 =<math>\scriptstyle\mathbf{E}[ X] = \frac{\alpha}{\beta}</math><br /><math>\scriptstyle \mathbf{E}[\ln X] = \psi(\alpha) -\ln(\beta)</math><br />(see [[digamma function]])
| |
| | median2 =No simple closed form
| |
| | mode2 =<math>\scriptstyle \frac{\alpha \,-\, 1}{\beta} \text{ for } \alpha \;{\geq}\; 1</math>
| |
| | variance2 =<math>\scriptstyle \operatorname{Var}[ X] = \frac{\alpha}{\beta^2}</math><br/><math>\scriptstyle\operatorname{Var}[\ln X] = \psi_1(\alpha)</math><br />(see [[trigamma function]]) | |
| | skewness2 =<math>\scriptstyle \frac{2}{\sqrt{\alpha}}</math>
| |
| | kurtosis2 =<math>\scriptstyle \frac{6}{\alpha}</math>
| |
| | entropy2 =<math>\scriptstyle \begin{align}
| |
| \scriptstyle \alpha &\scriptstyle \,-\, \ln \beta \,+\, \ln[\Gamma(\alpha)]\\
| |
| \scriptstyle &\scriptstyle \,+\, (1 \,-\, \alpha)\psi(\alpha)
| |
| \end{align}</math>
| |
| | mgf2 =<math>\scriptstyle \left(1 \,-\, \frac{t}{\beta}\right)^{-\alpha} \text{ for } t \;<\; \beta</math> | |
| | char2 =<math>\scriptstyle \left(1 \,-\, \frac{i\,t}{\beta}\right)^{-\alpha}</math> | |
| }}
| |
|
| |
|
| In [[probability theory]] and [[statistics]], the '''gamma distribution''' is a two-parameter family of continuous [[probability distribution]]s. The common [[exponential distribution]] and [[chi-squared distribution]] are special cases of the gamma distribution. There are three different [[parametrization]]s in common use:
| | A Gödel numbering can be interpreted as an [[Semantics encoding|encoding]] in which a number is assigned to each [[symbol]] of a [[mathematical notation]], after which a sequence of [[natural number]]s can then represent a sequence of symbols. These sequences of natural numbers can again be represented by single natural numbers, facilitating their manipulation in formal theories of arithmetic. |
| #With a [[shape parameter]] ''k'' and a [[scale parameter]] θ.
| |
| #With a shape parameter ''α'' = ''k'' and an inverse scale parameter β = 1/θ, called a [[rate parameter]].
| |
| #With a shape parameter ''k'' and a mean parameter μ = ''k''/β.
| |
| In each of these three forms, both parameters are positive real numbers.
| |
|
| |
|
| The parameterization with ''k'' and θ appears to be more common in [[econometrics]] and certain other applied fields, where e.g. the gamma distribution is frequently used to model waiting times. For instance, in [[Accelerated life testing|life testing]], the waiting time until death is a [[random variable]] that is frequently modeled with a gamma distribution.<ref>See Hogg and Craig (1978, Remark 3.3.1) for an explicit motivation</ref>
| | Since the publishing of Gödel's paper in 1931, the term "Gödel numbering" or "Gödel code" has been used to refer to more general assignments of natural numbers to mathematical objects. |
|
| |
|
| The parameterization with α and β is more common in [[Bayesian statistics]], where the gamma distribution is used as a [[conjugate prior]] distribution for various types of inverse scale (aka rate) parameters, such as the λ of an [[exponential distribution]] or a [[Poisson distribution]]<ref>[http://arxiv.org/pdf/1311.1704v3.pdf ''Scalable Recommendation with Poisson Factorization''], Prem Gopalan, Jake M. Hofman, [[David Blei]], arXiv.org 2014</ref> – or for that matter, the β of the gamma distribution itself. (The closely related [[inverse gamma distribution]] is used as a conjugate prior for scale parameters, such as the [[variance]] of a [[normal distribution]].) | | == Simplified overview == |
| | Gödel noted that statements within a system can be represented by natural numbers. The significance of this was that properties of statements - such as their truth and falsehood - would be equivalent to determining whether their Gödel numbers had certain properties. The numbers involved might be very long indeed (in terms of number of digits), but this is not a barrier; all that matters is that we can show such numbers can be constructed. |
|
| |
|
| If ''k'' is an [[integer]], then the distribution represents an [[Erlang distribution]]; i.e., the sum of ''k'' independent [[exponential distribution|exponentially distributed]] [[random variable]]s, each of which has a mean of θ (which is equivalent to a rate parameter of 1/θ).
| | In simple terms, we devise a method by which every formula or statement that can be formulated in our system gets a unique number, in such a way that we can mechanically convert back and forth between formulas and Gödel numbers. Clearly there are many ways this can be done. Given any statement, the number it is converted to is known as its Gödel number. A simple example is the way in which English is stored as a sequence of numbers in computers using [[ASCII]] or [[Unicode]]: |
| | :* The word '''<tt>HELLO</tt>''' is represented by 72-69-76-76-79 using decimal [[ASCII]]. |
| | :* The logical statement '''<tt>x=y => y=x</tt>''' is represented by 120-061-121-032-061-062-032-121-061-120 using decimal ASCII. |
|
| |
|
| The gamma distribution is the [[maximum entropy probability distribution]] for a random variable ''X'' for which '''E'''[''X''] = ''k''θ = α/β is fixed and greater than zero, and '''E'''[ln(''X'')] = ψ(''k'') + ln(θ) = ψ(α) − ln(β) is fixed (ψ is the [[digamma function]]).<ref>{{cite journal |last1=Park |first1=Sung Y. |last2=Bera |first2=Anil K. |year=2009 |title=Maximum entropy autoregressive conditional heteroskedasticity model |journal=Journal of Econometrics |volume= |issue= |pages=219–230 |publisher=Elsevier |doi= |url=http://www.wise.xmu.edu.cn/Master/Download/..%5C..%5CUploadFiles%5Cpaper-masterdownload%5C2009519932327055475115776.pdf |accessdate=2011-06-02|doi=10.1016/j.jeconom.2008.12.014 }}</ref>
| | == Gödel's encoding == |
| | Gödel used a system based on [[prime factorization]]. He first assigned a unique natural number to each basic symbol in the formal language of arithmetic with which he was dealing. |
|
| |
|
| ==Characterization using shape ''k'' and scale θ==
| | To encode an entire formula, which is a sequence of symbols, Gödel used the following system. Given a sequence <math>(x_1,x_2,x_3,...,x_n)</math> of positive integers, the Gödel encoding of the sequence is the product of the first ''n'' primes raised to their corresponding values in the sequence: |
| A random variable ''X'' that is gamma-distributed with shape ''k'' and scale θ is denoted by
| |
|
| |
|
| :<math>X \sim \Gamma(k, \theta) \equiv \textrm{Gamma}(k, \theta)</math> | | :<math>\mathrm{enc}(x_1,x_2,x_3,\dots,x_n) = 2^{x_1}\cdot 3^{x_2}\cdot 5^{x_3}\cdots p_n^{x_n}.\,</math> |
|
| |
|
| ===Probability density function===
| | According to the [[fundamental theorem of arithmetic]], any number obtained in this way can be uniquely factored into [[prime factor]]s, so it is possible to recover the original sequence from its Gödel number (for any given number n of symbols to be encoded). |
| [[Image:Gamma-PDF-3D.png|thumb|right|320px|Illustration of the gamma PDF for parameter values over ''k'' and ''x'' with θ set to 1, 2, 3, 4, 5 and 6. One can see each θ layer by itself here [http://commons.wikimedia.org/wiki/File:Gamma-PDF-3D-by-k.png] as well as by ''k'' [http://commons.wikimedia.org/wiki/File:Gamma-PDF-3D-by-Theta.png] and ''x''. [http://commons.wikimedia.org/wiki/File:Gamma-PDF-3D-by-x.png].]] | |
|
| |
|
| The [[probability density function]] using the shape-scale parametrization is
| | Gödel specifically used this scheme at two levels: first, to encode sequences of symbols representing formulas, and second, to encode sequences of formulas representing proofs. This allowed him to show a correspondence between statements about natural numbers and statements about the provability of theorems about natural numbers, the key observation of the proof. |
|
| |
|
| :<math>f(x;k,\theta) = \frac{x^{k-1}e^{-\frac{x}{\theta}}}{\theta^k\Gamma(k)} \quad \text{ for } x > 0 \text{ and } k, \theta > 0.</math>
| | There are more sophisticated (and more concise) ways to construct a [[Gödel numbering for sequences]]. |
|
| |
|
| Here Γ(''k'') is the [[gamma function]] evaluated at ''k''.
| | == Example == |
|
| |
|
| ===Cumulative distribution function=== | | In the specific Gödel numbering used by Nagel and Newman, the Gödel number for the symbol "0" is 6 and the Gödel number for the symbol "=" is 5. Thus, in their system, the Gödel number of the formula "0 = 0" is 2<sup>6</sup> × 3<sup>5</sup> × 5<sup>6</sup> = 243,000,000. |
| The [[cumulative distribution function]] is the regularized gamma function:
| |
|
| |
|
| :<math> F(x;k,\theta) = \int_0^x f(u;k,\theta)\,du = \frac{\gamma\left(k, \frac{x}{\theta}\right)}{\Gamma(k)}</math>
| | == Lack of uniqueness == |
|
| |
|
| where γ(''k'', ''x''/θ) is the lower [[incomplete gamma function]].
| | A Gödel numbering is not unique, in that for any proof using Gödel numbers, there are infinitely many ways in which these numbers could be defined. |
|
| |
|
| It can also be expressed as follows, if ''k'' is a positive [[integer]] (i.e., the distribution is an [[Erlang distribution]]):<ref name="Papoulis">Papoulis, Pillai, ''Probability, Random Variables, and Stochastic Processes'', Fourth Edition</ref>
| | For example, supposing there are ''K'' basic symbols, an alternative Gödel numbering could be constructed by invertibly mapping this set of symbols (through, say, an [[invertible function]] ''h'') to the set of digits of a [[Bijective numeration|bijective base-''K'' numeral system]]. A formula consisting of a string of ''n'' symbols <math> s_1 s_2 s_3 \dots s_n</math> would then be mapped to the number |
|
| |
|
| :<math>F(x;k,\theta) = 1-\sum_{i=0}^{k-1} \frac{1}{i!} \left(\frac{x}{\theta}\right)^i e^{-\frac{x}{\theta}} = e^{-\frac{x}{\theta}} \sum_{i=k}^{\infty} \frac{1}{i!} \left(\frac{x}{\theta}\right)^i</math> | | :<math> h(s_1) \times K^{(n-1)} + h(s_2) \times K^{(n-2)} + \cdots + h(s_{n-1}) \times K^1 + h(s_n) \times K^0 .</math> |
| <!-- The parameter θ used here is equivalent to the β defined above! -->
| |
|
| |
|
| ==Characterization using shape α and rate β==
| | In other words, by placing the set of ''K'' basic symbols in some fixed order, such that the ''i''<sup>''th''</sup> symbol corresponds uniquely to the ''i''<sup>''th''</sup> digit of a bijective base-''K'' numeral system, ''each formula may serve just as the very numeral of its own Gödel number.'' |
| Alternatively, the gamma distribution can be parameterized in terms of a [[shape parameter]] α = ''k'' and an inverse scale parameter β = 1/θ, called a [[rate parameter]]. A random variable ''X'' that is gamma-distributed with shape ''α'' and rate ''β'' is denoted
| |
|
| |
|
| :<math>X \sim \Gamma(\alpha, \beta) \equiv \textrm{Gamma}(\alpha,\beta)</math>
| | == Application to formal arithmetic == |
|
| |
|
| ===Probability density function===
| | Once a Gödel numbering for a formal theory is established, each [[rule of inference|inference rule]] of the theory can be expressed as a function on the natural numbers. If ''f'' is the Gödel mapping and if formula ''C'' can be derived from formulas ''A'' and ''B'' through an inference rule ''r''; i.e. |
| The corresponding density function in the shape-rate parametrization is
| | :<math> A, B \vdash_r C, \ </math> |
| | then there should be some [[arithmetical function]] ''g<sub>r</sub>'' of natural numbers such that |
| | :<math> g_r(f(A),f(B)) = f(C). \ </math> |
| | This is true for the numbering Gödel used, and for any other numbering where the encoded formula can be arithmetically recovered from its Gödel number. |
|
| |
|
| :<math>g(x;\alpha,\beta) = \frac{\beta^{\alpha} x^{\alpha-1} e^{-x\beta}}{\Gamma(\alpha)} \quad \text{ for } x \geq 0 \text{ and } \alpha, \beta > 0</math>
| | Thus, in a formal theory such as [[Peano arithmetic]] in which one can make statements about numbers and their arithmetical relationships to each other, one can use a Gödel numbering to indirectly make statements about the theory itself. This technique allowed Gödel to prove results about the consistency and completeness properties of [[formal system]]s. |
|
| |
|
| Both parametrizations are common because either can be more convenient depending on the situation.
| | == Generalizations == |
|
| |
|
| ===Cumulative distribution function===
| | In [[computability theory]], the term "Gödel numbering" is used in settings more general than the one described above. It can refer to: |
| The [[cumulative distribution function]] is the regularized gamma function:
| | #Any assignment of the elements of a [[formal language]] to natural numbers in such a way that the numbers can be manipulated by an [[algorithm]] to simulate manipulation of elements of the formal language. |
| | #More generally, an assignment of elements from a countable mathematical object, such as a countable [[group (mathematics)|group]], to natural numbers to allow algorithmic manipulation of the mathematical object. |
|
| |
|
| :<math> F(x;\alpha,\beta) = \int_0^x f(u;\alpha,\beta)\,du= \frac{\gamma(\alpha, \beta x)}{\Gamma(\alpha)}</math>
| | Also, the term Gödel numbering is sometimes used when the assigned "numbers" are actually strings, which is necessary when considering models of computation such as [[Turing machine]]s that manipulate strings rather than numbers. |
| | |
| where γ(α, β''x'') is the lower [[incomplete gamma function]].
| |
| | |
| If α is a positive [[integer]] (i.e., the distribution is an [[Erlang distribution]]), the cumulative distribution function has the following series expansion:<ref name="Papoulis"/>
| |
| | |
| :<math>F(x;\alpha,\beta) = 1-\sum_{i=0}^{\alpha-1} \frac{(\beta x)^i}{i!} e^{-\beta x} = e^{-\beta x} \sum_{i=\alpha}^{\infty} \frac{(\beta x)^i}{i!}</math>
| |
| | |
| ==Properties==
| |
| | |
| ===Skewness===
| |
| The skewness is equal to <math> 2/\sqrt{k} </math>, it depends only on the shape parameter (k) and approaches a normal distribution when k is large (approximately when k > 10).
| |
| | |
| ===Median calculation===
| |
| Unlike the mode and the mean which have readily calculable formulas based on the parameters, the median does not have an easy closed form equation. The median for this distribution is defined as the value ν such that
| |
| | |
| : <math>\frac{1}{\Gamma(k) \theta^k} \int_0^\nu x^{ k - 1 } e^{ - \frac{ x }{ \theta } } dx = \tfrac{1}{2}.</math>
| |
| | |
| A formula for approximating the median for any gamma distribution, when the mean is known, has been derived based on the fact that the ratio μ/(μ − ν) is approximately a linear function of ''k'' when ''k'' ≥ 1.<ref name=Banneheka2009>Banneheka BMSG, Ekanayake GEMUPD (2009) "A new point estimator for the median of gamma distribution". ''Viyodaya J Science'', 14:95–103</ref> The approximation formula is
| |
| | |
| : <math> \nu \approx \mu \frac{3 k - 0.8}{3 k + 0.2} ,</math>
| |
| | |
| where <math>\mu (=k\theta)</math> is the mean.
| |
| | |
| ===Summation===
| |
| If ''X''<sub>''i''</sub> has a Gamma(''k''<sub>''i''</sub>, θ) distribution for ''i'' = 1, 2, ..., ''N'' (i.e., all distributions have the same scale parameter θ), then
| |
| | |
| :<math> \sum_{i=1}^N X_i \sim\mathrm{Gamma} \left( \sum_{i=1}^N k_i, \theta \right)</math>
| |
| | |
| provided all ''X''<sub>''i''</sub> are [[statistical independence|independent]].
| |
| | |
| For the cases where the ''X''<sub>''i''</sub> are [[statistical independence|independent]] but have different scale parameters see Mathai (1982) and Moschopoulos (1984).
| |
| | |
| The gamma distribution exhibits [[Infinite divisibility (probability)|infinite divisibility]].
| |
| | |
| ===Scaling===
| |
| If
| |
| | |
| : <math>X \sim \mathrm{Gamma}(k, \theta),</math>
| |
| | |
| then for any ''c'' > 0,
| |
| | |
| : <math>cX \sim \mathrm{Gamma}( k, c\theta).</math>
| |
| | |
| Hence the use of the term "[[scale parameter]]" to describe θ.
| |
| | |
| Equivalently, if
| |
| | |
| : <math>X \sim \mathrm{Gamma}(\alpha, \beta),</math>
| |
| | |
| then for any ''c'' > 0,
| |
| | |
| : <math>cX \sim \mathrm{Gamma}( \alpha, \beta/c).</math>
| |
| | |
| Hence the use of the term "inverse scale parameter" to describe β.
| |
| | |
| ===Exponential family===
| |
| The gamma distribution is a two-parameter [[exponential family]] with [[natural parameters]] ''k'' − 1 and −1/θ (equivalently, α − 1 and −β), and [[natural statistics]] ''X'' and ln(''X'').
| |
| | |
| If the shape parameter k is held fixed, the resulting one-parameter family of distributions is a [[natural exponential family]].
| |
| | |
| ===Logarithmic expectation===
| |
| One can show that
| |
| | |
| : <math>\mathbf{E}[\ln(X)] = \psi(\alpha) - \ln(\beta)</math>
| |
| | |
| or equivalently,
| |
| | |
| : <math>\mathbf{E}[\ln(X)] = \psi(k) + \ln(\theta)</math>
| |
| | |
| where ψ is the [[digamma function]].
| |
| | |
| This can be derived using the [[exponential family]] formula for the [[exponential family#Moment generating function of the sufficient statistic|moment generating function of the sufficient statistic]], because one of the sufficient statistics of the gamma distribution is ln(''x'').
| |
| | |
| ===Information entropy===
| |
| The [[information entropy]] is
| |
| :<math>\operatorname{H}(X) = \mathbf{E}[-\ln(p(X))] = \mathbf{E}[-\alpha\ln(\beta) + \ln(\Gamma(\alpha)) - (\alpha-1)\ln(X) + \beta X] = \alpha - \ln(\beta) + \ln(\Gamma(\alpha)) + (1-\alpha)\psi(\alpha).</math>
| |
| | |
| In the ''k'', θ parameterization, the [[information entropy]] is given by
| |
| | |
| :<math>\operatorname{H}(X) =k + \ln(\theta) + \ln(\Gamma(k)) + (1-k)\psi(k).</math>
| |
| | |
| ===Kullback–Leibler divergence===
| |
| [[Image:Gamma-KL-3D.png|thumb|right|320px|Illustration of the Kullback–Leibler (KL) divergence for two gamma PDFs. Here β = β<sub>0</sub> + 1 which are set to 1, 2, 3, 4, 5 and 6. The typical asymmetry for the KL divergence is clearly visible.]]
| |
| | |
| The [[Kullback–Leibler divergence]] (KL-divergence), of Gamma(α<sub>''p''</sub>, β<sub>''p''</sub>) ("true" distribution) from Gamma(α<sub>''q''</sub>, β<sub>''q''</sub>) ("approximating" distribution) is given by<ref>W.D. Penny, [www.fil.ion.ucl.ac.uk/~wpenny/publications/densities.ps KL-Divergences of Normal, Gamma, Dirichlet, and Wishart densities]{{full|date=November 2012}}</ref>
| |
| :<math> D_{\mathrm{KL}}(\alpha_p,\beta_p; \alpha_q, \beta_q) = (\alpha_p-\alpha_q)\psi(\alpha_p) - \log\Gamma(\alpha_p) + \log\Gamma(\alpha_q) + \alpha_q(\log \beta_p - \log \beta_q) + \alpha_p\frac{\beta_q-\beta_p}{\beta_p} </math>
| |
| | |
| Written using the ''k'', θ parameterization, the KL-divergence of Gamma(''k<sub>p''</sub>, θ<sub>''p''</sub>) from Gamma(''k<sub>q''</sub>, θ<sub>''q''</sub>) is given by
| |
| :<math> D_{\mathrm{KL}}(k_p,\theta_p; k_q, \theta_q) = (k_p-k_q)\psi(k_p) - \log\Gamma(k_p) + \log\Gamma(k_q) + k_q(\log \theta_q - \log \theta_p) + k_p\frac{\theta_p - \theta_q}{\theta_q} </math>
| |
| | |
| === Laplace transform ===
| |
| The [[Laplace transform]] of the gamma PDF is
| |
| | |
| :<math>F(s) = (1 + \theta s)^{-k} = \frac{\beta^\alpha}{(s + \beta)^\alpha} .</math>
| |
| | |
| | |
| === [[Differential equation]] ===
| |
| | |
| | |
| <math>
| |
| \left\{\beta x f'(x)+f(x) (-\alpha \beta +\beta
| |
| +x)=0,f(1)=\frac{e^{-1/\beta } \beta ^{-\alpha }}{\Gamma (\alpha
| |
| )}\right\}
| |
| </math>
| |
| <br>
| |
| <math>
| |
| \left\{x f'(x)+f(x) (-k+\theta x+1)=0,f(1)=\frac{e^{-\theta }
| |
| \left(\frac{1}{\theta }\right)^{-k}}{\Gamma (k)}\right\}
| |
| </math>
| |
| | |
| == Parameter estimation ==
| |
| | |
| === Maximum likelihood estimation ===
| |
| The likelihood function for ''N'' [[independent and identically-distributed random variables|iid]] observations (''x''<sub>1</sub>, ..., ''x''<sub>''N''</sub>) is
| |
| | |
| :<math>L(k, \theta) = \prod_{i=1}^N f(x_i;k,\theta)</math>
| |
| | |
| from which we calculate the log-likelihood function
| |
| | |
| :<math>\ell(k, \theta) = (k - 1) \sum_{i=1}^N \ln{(x_i)} - \sum_{i=1}^N \frac{x_i}{\theta} - Nk\ln(\theta) - N\ln(\Gamma(k))</math>
| |
| | |
| Finding the maximum with respect to θ by taking the derivative and setting it equal to zero yields the [[maximum likelihood]] estimator of the θ parameter:
| |
| | |
| :<math>\hat{\theta} = \frac{1}{kN}\sum_{i=1}^N x_i</math>
| |
| | |
| Substituting this into the log-likelihood function gives
| |
| | |
| :<math>\ell = (k-1)\sum_{i=1}^N\ln{(x_i)} - Nk - Nk\ln{\left(\frac{\sum x_i}{kN}\right)} - N\ln(\Gamma(k))</math>
| |
| | |
| Finding the maximum with respect to ''k'' by taking the derivative and setting it equal to zero yields
| |
| | |
| :<math>\ln(k) - \psi(k) = \ln\left(\frac{1}{N}\sum_{i=1}^N x_i\right) - \frac{1}{N}\sum_{i=1}^N\ln(x_i)</math>
| |
| | |
| There is no closed-form solution for ''k''. The function is numerically very well behaved, so if a numerical solution is desired, it can be found using, for example, [[Newton's method]]. An initial value of ''k'' can be found either using the [[method of moments (statistics)|method of moments]], or using the approximation
| |
| | |
| :<math>\ln(k) - \psi(k) \approx \frac{1}{2k}\left(1 + \frac{1}{6k + 1}\right)</math>
| |
| | |
| If we let
| |
| | |
| :<math>s = \ln{\left(\frac{1}{N}\sum_{i=1}^N x_i\right)} - \frac{1}{N}\sum_{i=1}^N\ln{(x_i)}</math>
| |
| | |
| then ''k'' is approximately
| |
| | |
| :<math>k \approx \frac{3 - s + \sqrt{(s - 3)^2 + 24s}}{12s}</math>
| |
| | |
| which is within 1.5% of the correct value.<ref>Minka, Thomas P. (2002) "Estimating a Gamma distribution". http://research.microsoft.com/en-us/um/people/minka/papers/minka-gamma.pdf</ref> An explicit form for the Newton–Raphson update of this initial guess is:<ref>Choi, S.C.; Wette, R. (1969) "Maximum Likelihood Estimation of the Parameters of the Gamma Distribution and Their Bias", ''Technometrics'', 11(4) 683–690</ref>
| |
| | |
| :<math>k \leftarrow k - \frac{ \ln(k) - \psi(k) - s }{ \frac{1}{k} - \psi^{\prime}(k) }.</math>
| |
| | |
| === Bayesian minimum mean squared error ===
| |
| With known ''k'' and unknown θ, the posterior density function for theta (using the standard scale-invariant [[prior probability|prior]] for θ) is
| |
| :<math>P(\theta | k, x_1, \dots, x_N) \propto \frac{1}{\theta} \prod_{i=1}^N f(x_i; k, \theta)</math>
| |
| | |
| Denoting
| |
| | |
| :<math> y \equiv \sum_{i=1}^Nx_i , \qquad P(\theta | k, x_1, \dots, x_N) = C(x_i) \theta^{-N k-1} e^{-\frac{y}{\theta}}</math>
| |
| | |
| Integration over θ can be carried out using a change of variables, revealing that 1/θ is gamma-distributed with parameters α = ''Nk'', β = ''y''.
| |
| | |
| :<math>\int_0^{\infty} \theta^{-Nk - 1 + m} e^{-\frac{y}{\theta}}\, d\theta = \int_0^{\infty} x^{Nk - 1 - m} e^{-xy} \, dx = y^{-(Nk - m)} \Gamma(Nk - m) \!</math>
| |
| | |
| The moments can be computed by taking the ratio (''m'' by ''m'' = 0)
| |
| | |
| :<math>\mathbf{E} [x^m] = \frac {\Gamma (Nk - m)} {\Gamma(Nk)} y^m</math>
| |
| | |
| which shows that the mean ± standard deviation estimate of the posterior distribution for θ is
| |
| | |
| :<math> \frac {y} {Nk - 1} \pm \frac {y^2} {(Nk - 1)^2 (Nk - 2)} </math>
| |
| | |
| == Generating gamma-distributed random variables ==
| |
| Given the scaling property above, it is enough to generate gamma variables with θ = 1 as we can later convert to any value of β with simple division.
| |
| | |
| Using the fact that a Gamma(1, 1) distribution is the same as an Exp(1) distribution, and noting the method of [[exponential distribution#Generating exponential variates|generating exponential variables]], we conclude that if ''U'' is [[uniform distribution (continuous)|uniformly distributed]] on (0, 1], then −ln(''U'') is distributed Gamma(1, 1) Now, using the "α-addition" property of gamma distribution, we expand this result:
| |
| | |
| : <math>\sum_{k=1}^n {-\ln U_k} \sim \Gamma(n, 1)</math>
| |
| | |
| where ''U<sub>k</sub>'' are all uniformly distributed on (0, 1] and [[statistical independence|independent]]. All that is left now is to generate a variable distributed as Gamma(δ, 1) for 0 < δ < 1 and apply the "α-addition" property once more. This is the most difficult part.
| |
| | |
| Random generation of gamma variates is discussed in detail by Devroye,<ref>{{cite book|title=Non-Uniform Random Variate Generation|author=Luc Devroye|year=1986|publisher=Springer-Verlag|location=New York|url=http://luc.devroye.org/rnbookindex.html|ref=harv}} See Chapter 9, Section 3, pages 401–428.</ref> noting that none are uniformly fast for all shape parameters. For small values of the shape parameter, the algorithms are often not valid.<ref>Devroye (1986), p. 406.</ref> For arbitrary values of the shape parameter, one can apply the Ahrens and Dieter<ref name=AD>Ahrens, J. H. and Dieter, U. (1982). Generating gamma variates by a modified rejection technique. ''Communications of the ACM'', 25, 47–54. Algorithm GD, p. 53.</ref> modified acceptance–rejection method Algorithm GD (shape ''k'' ≥ 1), or transformation method<ref>{{cite journal | last1 = Ahrens | first1 = J. H. | last2 = Dieter | first2 = U. | year = 1974 | title = Computer methods for sampling from gamma, beta, Poisson and binomial distributions | journal = Computing | volume = 12 | pages = 223–246 | id = {{citeseerx|10.1.1.93.3828}} | doi=10.1007/BF02293108}}</ref> when 0 < ''k'' < 1. Also see Cheng and Feast Algorithm GKM 3<ref>Cheng, R.C.H., and Feast, G.M. Some simple gamma variate generators. Appl. Stat. 28 (1979), 290–295.</ref> or Marsaglia's squeeze method.<ref>Marsaglia, G. The squeeze method for generating gamma variates. Comput, Math. Appl. 3 (1977), 321–325.</ref>
| |
| | |
| The following is a version of the Ahrens-Dieter [[rejection sampling|acceptance–rejection method]]:<ref name=AD/>
| |
| | |
| # Let ''m'' be 1.
| |
| # Generate ''V<sub>3m−2</sub>'', ''V<sub>3m−1</sub>'' and ''V<sub>3m</sub>'' as independent uniformly distributed on (0, 1] variables.
| |
| # If <math>V_{3m - 2} \le v_0</math>, where <math>v_0 = \frac{e}{e + \delta}</math>, then go to step 4, else go to step 5.
| |
| # Let <math>\xi_m = V_{3m - 1}^{1 / \delta}, \ \eta_m = V_{3m} \xi_m^{\delta - 1}</math>. Go to step 6.
| |
| # Let <math>\xi_m = 1 - \ln {V_{3m - 1}}, \ \eta_m = V_{3m} e^{-\xi_m}</math>.
| |
| # If <math>\eta_m > \xi_m^{\delta - 1} e^{-\xi_m}</math>, then increment ''m'' and go to step 2.
| |
| # Assume ξ = ξ<sub>''m''</sub> to be the realization of Γ(δ, 1).
| |
| | |
| A summary of this is
| |
| | |
| : <math> \theta \left( \xi - \sum_{i=1}^{\lfloor{k}\rfloor} {\ln(U_i)} \right) \sim \Gamma (k, \theta)</math>
| |
| | |
| where
| |
| | |
| * <math>\scriptstyle \lfloor{k}\rfloor</math> is the integral part of ''k'',
| |
| * ξ has been generated using the algorithm above with δ = {''k''} (the fractional part of ''k''),
| |
| * ''U<sub>k</sub>'' and ''V<sub>l</sub>'' are distributed as explained above and are all independent.
| |
| | |
| While the above approach is technically correct, Devroye notes that it is linear in the value of ''k'' and in general is not a good choice. Instead he recommends using either rejection-based or table-based methods, depending on context.<ref>{{cite book|title=Non-Uniform Random Variate Generation|author=Luc Devroye|year=1986|publisher=Springer-Verlag|location=New York|url=http://luc.devroye.org/rnbookindex.html}} See Chapter 9, Section 3, pages 401–428.</ref>
| |
| | |
| ==Related distributions==
| |
| | |
| === Special cases ===
| |
| | |
| === Conjugate prior ===
| |
| In [[Bayesian inference]], the '''gamma distribution''' is the [[conjugate prior]] to many likelihood distributions: the [[Poisson distribution|Poisson]], [[Exponential distribution|exponential]], [[Normal distribution|normal]] (with known mean), [[Pareto distribution|Pareto]], gamma with known shape σ, [[Inverse-gamma distribution|inverse gamma]] with known shape parameter, and [[Gompertz distribution|Gompertz]] with known scale parameter. <!-- reference: see article [[conjugate prior]] //-->
| |
| | |
| The gamma distribution's [[conjugate prior]] is:<ref name="fink">Fink, D. 1995 [http://www.stat.columbia.edu/~cook/movabletype/mlm/CONJINTRnew%2BTEX.pdf A Compendium of Conjugate Priors]. In progress report: Extension and enhancement of methods for setting data quality objectives. (DOE contract 95‑831).</ref>
| |
| | |
| :<math>p(k,\theta | p, q, r, s) = \frac{1}{Z} \frac{p^{k-1} e^{-\theta^{-1} q}}{\Gamma(k)^r \theta^{k s}},</math>
| |
| | |
| where ''Z'' is the normalizing constant, which has no closed-form solution.
| |
| The posterior distribution can be found by updating the parameters as follows:
| |
| | |
| :<math>\begin{align}
| |
| p' &= p\prod\nolimits_i x_i,\\
| |
| q' &= q + \sum\nolimits_i x_i,\\
| |
| r' &= r + n,\\
| |
| s' &= s + n,
| |
| \end{align}</math>
| |
| | |
| where ''n'' is the number of observations, and ''x<sub>i</sub>'' is the ''i''th observation.
| |
| | |
| === Compound gamma ===
| |
| If the shape parameter of the gamma distribution is known, but the inverse-scale parameter is unknown, then a gamma distribution for the inverse-scale forms a conjugate prior. The [[compound distribution]], which results from integrating out the inverse-scale has a closed form solution, known as the [[compound gamma distribution]].<ref name=Dubey>{{cite journal|last=Dubey|first=Satya D. | title=Compound gamma, beta and F distributions|journal=Metrika|date=December 1970|volume=16|pages=27–31 |doi=10.1007/BF02613934| url=http://www.springerlink.com/content/u750hg4630387205/}}</ref>
| |
| | |
| === Others ===
| |
| * If ''X'' ~ Gamma(1, λ), then ''X'' has an [[exponential distribution]] with rate parameter λ.
| |
| * If ''X'' ~ Gamma(ν/2, 2), then ''X'' is identical to χ<sup>2</sup>(ν), the [[chi-squared distribution]] with ν degrees of freedom. Conversely, if ''Q'' ~ χ<sup>2</sup>(ν) and ''c'' is a positive constant, then ''cQ'' ~ Gamma(ν/2, 2''c'').
| |
| * If ''k'' is an [[integer]], the gamma distribution is an [[Erlang distribution]] and is the probability distribution of the waiting time until the ''k''th "arrival" in a one-dimensional [[Poisson process]] with intensity 1/θ. If
| |
| ::<math>X \sim \Gamma(k \in \mathbf{Z}, \theta), \qquad Y \sim \mathrm{Pois}\left(\frac{x}{\theta}\right),</math>
| |
| :then
| |
| ::<math>P(X > x) = P(Y < k).</math>
| |
| * If ''X'' has a [[Maxwell–Boltzmann distribution]] with parameter ''a'', then
| |
| ::<math>X^2 \sim \Gamma\left(\tfrac{3}{2}, 2a^2\right)</math>.
| |
| <!-- | | <!-- |
| * <math>Y \sim N(\mu = \alpha \beta, \sigma^2 = \alpha \beta^2)</math> is a [[normal distribution]] as <math>Y = \lim_{\alpha \to \infty} X</math> where ''X'' ~ Gamma(α, β). -->
| | There is a very different meaning of the term Gödel numbering relating to |
| * If ''X'' ~ Gamma(''k'', θ), then <math>\sqrt{X}</math> follows a [[generalized gamma distribution]] with parameters ''p'' = 2, ''d'' = 2''k'', and <math>a = \sqrt{\theta}</math> {{citation needed|date=September 2012}} .
| | [[numbering (computability theory)|numberings]] of the class of [[computable function]]s. COMMENTED OUT PER TALK --> |
| * If ''X'' ~ Gamma(''k'', θ), then 1/''X'' ~ Inv-Gamma(''k'', θ<sup>-1</sup>) (see [[Inverse-gamma distribution]] for derivation).
| |
| * If ''X'' ~ Gamma(α, θ) and ''Y'' ~ Gamma(β, θ) are independently distributed, then ''X''/(''X'' + ''Y'') has a [[beta distribution]] with parameters α and β.
| |
| * If ''X<sub>i</sub>'' ~ Gamma(α<sub>''i''</sub>, 1) are independently distributed, then the vector (''X''<sub>1</sub>/''S'', ..., ''X<sub>n</sub>''/''S''), where ''S'' = ''X''<sub>1</sub> + ... + ''X<sub>n</sub>'', follows a [[Dirichlet distribution]] with parameters α<sub>1</sub>, ..., α<sub>''n''</sub>.
| |
| * For large ''k'' the gamma distribution converges to Gaussian distribution with mean μ = ''k''θ and variance σ<sup>2</sup> = ''k''θ<sup>2</sup>.
| |
| * The gamma distribution is the [[conjugate prior]] for the precision of the [[normal distribution]] with known [[mean]].
| |
| * The [[Wishart distribution]] is a multivariate generalization of the gamma distribution (samples are positive-definite matrices rather than positive real numbers).
| |
| * The gamma distribution is a special case of the [[generalized gamma distribution]], the [[generalized integer gamma distribution]], and the [[generalized inverse Gaussian distribution]].
| |
| * Among the discrete distributions, the [[negative binomial distribution]] is sometimes considered the discrete analogue of the Gamma distribution.
| |
| * [[Tweedie distribution]]s – the gamma distribution is a member of the family of Tweedie [[exponential dispersion model]]s.
| |
| | |
| ==Applications==
| |
| | |
| {{Expand section|date=March 2009}}
| |
| | |
| The gamma distribution has been used to model the size of [[insurance policy|insurance claims]]<ref>p. 43, Philip J. Boland, Statistical and Probabilistic Methods in Actuarial Science, Chapman & Hall CRC 2007</ref> and rainfalls.<ref name="Aksoy">Aksoy, H. (2000) [http://journals.tubitak.gov.tr/engineering/issues/muh-00-24-6/muh-24-6-7-9909-13.pdf "Use of Gamma Distribution in Hydrological Analysis"], ''Turk J. Engin Environ Sci'', 24, 419 – 428.</ref> This means that aggregate insurance claims and the amount of rainfall accumulated in a reservoir are modelled by a [[gamma process]]. The gamma distribution is also used to model errors in multi-level [[Poisson regression]] models, because the combination of the [[Poisson distribution]] and a gamma distribution is a [[negative binomial distribution]].
| |
| | |
| In [[neuroscience]], the gamma distribution is often used to describe the distribution of [[Temporal coding|inter-spike intervals]].<ref name="Robson">J. G. Robson and J. B. Troy, "Nature of the maintained discharge of Q, X, and Y retinal ganglion cells of the cat", J. Opt. Soc. Am. A 4, 2301–2307 (1987)</ref> Although in practice the gamma distribution often provides a good fit, there is no underlying biophysical motivation for using it.
| |
| | |
| In [[Bacterial genetics|bacterial]] [[gene expression]], the [[Copy number analysis|copy number]] of a [[constitutively expressed]] protein often follows the gamma distribution, where the scale and shape parameter are, respectively, the mean number of bursts per cell cycle and the mean number of [[protein molecule]]s produced by a single mRNA during its lifetime.<ref name="Friedman">N. Friedman, L. Cai and X. S. Xie (2006) "Linking stochastic dynamics to population distribution: An analytical framework of gene expression", ''Phys. Rev. Lett.'' 97, 168302.</ref>
| |
| | |
| In [[genomics]], the gamma distribution was applied in [[peak calling]] step (i.e. in recognition of signal) in [[ChIP-chip]]<ref name="Reiss">DJ Reiss, MT Facciotti and NS Baliga (2008) [http://bioinformatics.oxfordjournals.org/content/24/3/396.full.pdf+html "Model-based deconvolution of genome-wide DNA binding"], ''Bioinformatics'', 24, 396–403 </ref> and [[ChIP-seq]]<ref name="Mendoza">MA Mendoza-Parra, M Nowicka, W Van Gool, H Gronemeyer (2013) [http://www.biomedcentral.com/1471-2164/14/834 "Characterising ChIP-seq binding patterns by model-based peak shape deconvolution"], ''BMC Genomics'', 14:834</ref> data analysis.
| |
|
| |
|
| The gamma distribution is widely used as a [[conjugate prior]] in Bayesian statistics. It is the conjugate prior for the precision (i.e. inverse of the variance) of a [[normal distribution]]. It is also the conjugate prior for the [[exponential distribution]].
| | ==Gödel sets== |
| | Gödel sets are sometimes used in set theory to encode formulas, and are similar to Gödel numbers, except that one uses sets rather than numbers to do the encoding. In simple cases when one uses a [[hereditarily finite set]] to encode formulas this is essentially equivalent to the use of Gödel numbers, but somewhat easier to define because the tree structure of formulas can be modeled by the tree structure of sets. Gödel sets can also be used to encode formulas in [[infinitary logic|infinitary languages]]. |
|
| |
|
| ==Notes== | | == See also == |
| | | * [[Church numeral]] |
| <references/>
| | * [[Description number]] |
| | * [[Gödel numbering for sequences]] |
| | * [[Gödel's incompleteness theorems]] |
| | * [[Kolmogorov_complexity#Chaitin.27s_incompleteness_theorem|Chaitin's incompleteness theorem]] |
|
| |
|
| == References == | | == References == |
|
| |
|
| * R. V. Hogg and A. T. Craig (1978) ''Introduction to Mathematical Statistics'', 4th edition. New York: Macmillan. (See Section 3.3.)' | | * {{Citation|last=Gödel|first= Kurt |title=Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I |journal=Monatsheft für Math. und Physik |volume=38|year= 1931| pages=173–198 |url=http://www.w-k-essler.de/pdfs/goedel.pdf}}. |
| * P. G. Moschopoulos (1985) ''The distribution of the sum of independent gamma random variables'', '''Annals of the Institute of Statistical Mathematics''', 37, 541–544 | | *''Gödel's Proof'' by [[Ernest Nagel]] and [[James R. Newman]] (1959). This book provides a good introduction and summary of the proof, with a large section dedicated to Gödel's numbering. |
| * A. M. Mathai (1982) ''Storage capacity of a dam with gamma type inputs'', '''Annals of the Institute of Statistical Mathematics''', 34, 591–597
| |
| | |
| ==External links==
| |
|
| |
|
| {{wikibooks|Statistics|Distributions/Gamma|Gamma distribution}} | | {{reflist}} |
| * {{springer|title=Gamma-distribution|id=p/g043300}}
| |
| * {{MathWorld|urlname=GammaDistribution|title=Gamma distribution}}
| |
| * [http://www.itl.nist.gov/div898/handbook/eda/section3/eda366b.htm Engineering Statistics Handbook]
| |
|
| |
|
| {{ProbDistributions|continuous-semi-infinite}}
| | == Further reading == |
| {{Common univariate probability distributions}}
| | * ''[[Gödel, Escher, Bach|Gödel, Escher, Bach: an Eternal Golden Braid]]'', by [[Douglas Hofstadter]]. This book defines and uses an alternative Gödel numbering. |
| | *''[[I Am a Strange Loop]]'' by [[Douglas Hofstadter]]. This is a newer book by Hofstadter that includes the history of Gödel's numbering. |
|
| |
|
| {{DEFAULTSORT:Gamma Distribution}} | | {{DEFAULTSORT:Godel Number}} |
| [[Category:Continuous distributions]] | | [[Category:Mathematical logic]] |
| [[Category:Factorial and binomial topics]] | | [[Category:Theory of computation]] |
| [[Category:Conjugate prior distributions]] | | [[Category:Works by Kurt Gödel|Numering]] |
| [[Category:Exponential family distributions]]
| |
| [[Category:Infinitely divisible probability distributions]]
| |
| [[Category:Probability distributions]]
| |
28 year-old Painting Investments Worker Truman from Regina, usually spends time with pastimes for instance interior design, property developers in new launch ec Singapore and writing. Last month just traveled to City of the Renaissance.
In mathematical logic, a Gödel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its Gödel number. The concept was used by Kurt Gödel for the proof of his incompleteness theorems. (Template:Harvnb)
A Gödel numbering can be interpreted as an encoding in which a number is assigned to each symbol of a mathematical notation, after which a sequence of natural numbers can then represent a sequence of symbols. These sequences of natural numbers can again be represented by single natural numbers, facilitating their manipulation in formal theories of arithmetic.
Since the publishing of Gödel's paper in 1931, the term "Gödel numbering" or "Gödel code" has been used to refer to more general assignments of natural numbers to mathematical objects.
Simplified overview
Gödel noted that statements within a system can be represented by natural numbers. The significance of this was that properties of statements - such as their truth and falsehood - would be equivalent to determining whether their Gödel numbers had certain properties. The numbers involved might be very long indeed (in terms of number of digits), but this is not a barrier; all that matters is that we can show such numbers can be constructed.
In simple terms, we devise a method by which every formula or statement that can be formulated in our system gets a unique number, in such a way that we can mechanically convert back and forth between formulas and Gödel numbers. Clearly there are many ways this can be done. Given any statement, the number it is converted to is known as its Gödel number. A simple example is the way in which English is stored as a sequence of numbers in computers using ASCII or Unicode:
- The word HELLO is represented by 72-69-76-76-79 using decimal ASCII.
- The logical statement x=y => y=x is represented by 120-061-121-032-061-062-032-121-061-120 using decimal ASCII.
Gödel's encoding
Gödel used a system based on prime factorization. He first assigned a unique natural number to each basic symbol in the formal language of arithmetic with which he was dealing.
To encode an entire formula, which is a sequence of symbols, Gödel used the following system. Given a sequence of positive integers, the Gödel encoding of the sequence is the product of the first n primes raised to their corresponding values in the sequence:
According to the fundamental theorem of arithmetic, any number obtained in this way can be uniquely factored into prime factors, so it is possible to recover the original sequence from its Gödel number (for any given number n of symbols to be encoded).
Gödel specifically used this scheme at two levels: first, to encode sequences of symbols representing formulas, and second, to encode sequences of formulas representing proofs. This allowed him to show a correspondence between statements about natural numbers and statements about the provability of theorems about natural numbers, the key observation of the proof.
There are more sophisticated (and more concise) ways to construct a Gödel numbering for sequences.
Example
In the specific Gödel numbering used by Nagel and Newman, the Gödel number for the symbol "0" is 6 and the Gödel number for the symbol "=" is 5. Thus, in their system, the Gödel number of the formula "0 = 0" is 26 × 35 × 56 = 243,000,000.
Lack of uniqueness
A Gödel numbering is not unique, in that for any proof using Gödel numbers, there are infinitely many ways in which these numbers could be defined.
For example, supposing there are K basic symbols, an alternative Gödel numbering could be constructed by invertibly mapping this set of symbols (through, say, an invertible function h) to the set of digits of a bijective base-K numeral system. A formula consisting of a string of n symbols would then be mapped to the number
In other words, by placing the set of K basic symbols in some fixed order, such that the ith symbol corresponds uniquely to the ith digit of a bijective base-K numeral system, each formula may serve just as the very numeral of its own Gödel number.
Application to formal arithmetic
Once a Gödel numbering for a formal theory is established, each inference rule of the theory can be expressed as a function on the natural numbers. If f is the Gödel mapping and if formula C can be derived from formulas A and B through an inference rule r; i.e.
then there should be some arithmetical function gr of natural numbers such that
This is true for the numbering Gödel used, and for any other numbering where the encoded formula can be arithmetically recovered from its Gödel number.
Thus, in a formal theory such as Peano arithmetic in which one can make statements about numbers and their arithmetical relationships to each other, one can use a Gödel numbering to indirectly make statements about the theory itself. This technique allowed Gödel to prove results about the consistency and completeness properties of formal systems.
Generalizations
In computability theory, the term "Gödel numbering" is used in settings more general than the one described above. It can refer to:
- Any assignment of the elements of a formal language to natural numbers in such a way that the numbers can be manipulated by an algorithm to simulate manipulation of elements of the formal language.
- More generally, an assignment of elements from a countable mathematical object, such as a countable group, to natural numbers to allow algorithmic manipulation of the mathematical object.
Also, the term Gödel numbering is sometimes used when the assigned "numbers" are actually strings, which is necessary when considering models of computation such as Turing machines that manipulate strings rather than numbers.
Gödel sets
Gödel sets are sometimes used in set theory to encode formulas, and are similar to Gödel numbers, except that one uses sets rather than numbers to do the encoding. In simple cases when one uses a hereditarily finite set to encode formulas this is essentially equivalent to the use of Gödel numbers, but somewhat easier to define because the tree structure of formulas can be modeled by the tree structure of sets. Gödel sets can also be used to encode formulas in infinitary languages.
See also
References
- Many property agents need to declare for the PIC grant in Singapore. However, not all of them know find out how to do the correct process for getting this PIC scheme from the IRAS. There are a number of steps that you need to do before your software can be approved.
Naturally, you will have to pay a safety deposit and that is usually one month rent for annually of the settlement. That is the place your good religion deposit will likely be taken into account and will kind part or all of your security deposit. Anticipate to have a proportionate amount deducted out of your deposit if something is discovered to be damaged if you move out. It's best to you'll want to test the inventory drawn up by the owner, which can detail all objects in the property and their condition. If you happen to fail to notice any harm not already mentioned within the inventory before transferring in, you danger having to pay for it yourself.
In case you are in search of an actual estate or Singapore property agent on-line, you simply should belief your intuition. It's because you do not know which agent is nice and which agent will not be. Carry out research on several brokers by looking out the internet. As soon as if you end up positive that a selected agent is dependable and reliable, you can choose to utilize his partnerise in finding you a home in Singapore. Most of the time, a property agent is taken into account to be good if he or she locations the contact data on his website. This may mean that the agent does not mind you calling them and asking them any questions relating to new properties in singapore in Singapore. After chatting with them you too can see them in their office after taking an appointment.
Have handed an trade examination i.e Widespread Examination for House Brokers (CEHA) or Actual Property Agency (REA) examination, or equal; Exclusive brokers are extra keen to share listing information thus making certain the widest doable coverage inside the real estate community via Multiple Listings and Networking. Accepting a severe provide is simpler since your agent is totally conscious of all advertising activity related with your property. This reduces your having to check with a number of agents for some other offers. Price control is easily achieved. Paint work in good restore-discuss with your Property Marketing consultant if main works are still to be done. Softening in residential property prices proceed, led by 2.8 per cent decline within the index for Remainder of Central Region
Once you place down the one per cent choice price to carry down a non-public property, it's important to accept its situation as it is whenever you move in – faulty air-con, choked rest room and all. Get round this by asking your agent to incorporate a ultimate inspection clause within the possibility-to-buy letter. HDB flat patrons routinely take pleasure in this security net. "There's a ultimate inspection of the property two days before the completion of all HDB transactions. If the air-con is defective, you can request the seller to repair it," says Kelvin.
15.6.1 As the agent is an intermediary, generally, as soon as the principal and third party are introduced right into a contractual relationship, the agent drops out of the image, subject to any problems with remuneration or indemnification that he could have against the principal, and extra exceptionally, against the third occasion. Generally, agents are entitled to be indemnified for all liabilities reasonably incurred within the execution of the brokers´ authority.
To achieve the very best outcomes, you must be always updated on market situations, including past transaction information and reliable projections. You could review and examine comparable homes that are currently available in the market, especially these which have been sold or not bought up to now six months. You'll be able to see a pattern of such report by clicking here It's essential to defend yourself in opposition to unscrupulous patrons. They are often very skilled in using highly unethical and manipulative techniques to try and lure you into a lure. That you must also protect your self, your loved ones, and personal belongings as you'll be serving many strangers in your home. Sign a listing itemizing of all of the objects provided by the proprietor, together with their situation. HSR Prime Recruiter 2010.
- Gödel's Proof by Ernest Nagel and James R. Newman (1959). This book provides a good introduction and summary of the proof, with a large section dedicated to Gödel's numbering.
43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.
Further reading