Artículos con la etiqueta ‘A. N.Kolmogorov’

A Galois connection between classical and intuitionistic logics

Por • 11 dic, 2013 • Category: Ciencia y tecnología

In a 1985 commentary to his collected works, Kolmogoroff remarked that his 1932 paper «was written in hope that with time, the logic of solution of problems will become a permanent part of the logical curriculum. Creation of a unified logical apparatus dealing with objects of two types – propositions and problems – was intended.» We construct such a formal system QHC, which is a conservative extension of both the intuitionistic predicate calculus QH and the classical predicate calculus QC, and sheds new light on the basics of intuitionism:
1) The only new connectives ? and ! of QHC induce a Galois connection (i.e., a pair of adjoint functors) between the Lindenbaum algebras of QH and QC.
2) Kolmogoroff’s double negation translation of QC into QH extends to an interpretation of QHC in QH that is the identity on QH.
3) Goedel’s provability translation of QH into the classical modal logic QS4 extends to an interpretation of QHC in QS4, which is identified with a fragment of QHC.
Some models of QHC are constructed, including a sheaf-valued model inspired by dependent type theory, which appears to be of interest even as a model of QH (not to be confused with the well-known open-set-valued sheaf models of QH), since it can be seen as a rather accurate formalization of the BHK interpretation of intuitionistism.
The paper is addressed to a general mathematical audience and includes a rather unconventional introduction to intuitionistic logic, featuring (a) a motivation via Hilbert’s 24th Problem and Lafont’s observation that in classical logic, any two proofs of a given theorem are «homotopic»; (b) a derivation of Tarski topological models of QH via a model in «Venn diagrams» of a classical first-order theory extracted from the clauses of the BHK interpretation.

Partial Probability and Kleene Logic

Por • 27 oct, 2013 • Category: Crítica

There are two main approach to probability, one of set-theoretic character where probability is the measure of a set, and another one of linguistic character where probability is the degree of confidence in a proposition. In this work we give an unified algebraic treatment of these approaches through the concept of valued lattice, obtaining as a by-product a translation between them. Then we introduce the concept of partial valuation for DMF-algebras (De Morgan algebras with a single fixed point for negation), giving an algebraic setting for probability of partial events. We introduce the concept of partial probability for propositions, substituting classical logic with Kleene’s logic. In this case too we give a translation between set-theoretic and linguistic probability. Finally, we introduce the concept of conditional partial probability and prove a weak form of Bayes’s Theorem.

Novel measures based on the Kolmogorov complexity for use in complex system behavior studies and time series analysis

Por • 9 oct, 2013 • Category: Crítica

We have proposed novel measures based on the Kolmogorov complexity for use in complex system behavior studies and time series analysis. We have considered background of the Kolmogorov complexity and also we have discussed meaning of the physical as well as other complexities. To get better insights into the complexity of complex systems and time series analysis we have introduced the three novel measures based on the Kolmogorov complexity: (i) the Kolmogorov complexity spectrum, (ii) the Kolmogorov complexity spectrum highest value and (iii) the overall Kolmogorov complexity. The characteristics of these measures have been tested using a generalized logistic equation. Finally, the proposed measures have been applied on different time series originating from: the model output (the biochemical substance exchange in a multi-cell system), four different geophysical phenomena (dynamics of: river flow, long term precipitation, indoor 222Rn concentration and UV radiation dose) and economy (stock prices dynamics). Results which are obtained offer deeper insights into complexity of the system dynamics behavior and time series analysis when the proposed complexity measures are applied.