| Peer-Reviewed

Algebra of Countably Functions and Theorems of Completeness

Received: 15 February 2019     Accepted: 18 March 2019     Published: 9 April 2019
Views:       Downloads:
Abstract

An algebraic approach to the theory of countable functions is given. Compositions (superpositions) of functions are used instead of recursions. Arithmetic and analytic algorithms are defined. All closed sets are founded. Mathematically precise definitions of logic algorithms with quantifiers of existence and universality are given. Logic algorithm for fast-growing function is built as example. Classification of functions is given. There are non-computable functions. These functions are fictitious (useless) and their set is continual. The set of computable functions is countable. Incompleteness of disjunction and negation, conjunction and negation, of Pierce, Sheffer and diagonal Webb functions is proved. The completeness of the set of one-place functions and any all-valued essential function (Slupecki theorem) is proved for computable functions. Existence of generators of all computable functions is proved too.

Published in Pure and Applied Mathematics Journal (Volume 8, Issue 1)
DOI 10.11648/j.pamj.20190801.11
Page(s) 1-9
Creative Commons

This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.

Copyright

Copyright © The Author(s), 2019. Published by Science Publishing Group

Keywords

Discrete Functions, Complete Sets of Functions, Algebra Countably-valued Functions, Logic Programming, Theory of Algorithms

References
[1] A. I. Mal'cev, Iterative Post algebras (Russian), Novosibirsk, Novosib. gos. un-t (1976).
[2] S. V. Jablonskij, Functional constructions in k-valued logic (Russian), Tr. mat. inst. Steklova, 5-142 (1958).
[3] E. L. Post, Two-valued iterative systems of mathematical logic, Princeton, Princeton Univ. Press (1941).
[4] D. Lau, Functions algebra on finite sets, Berlin, Springer (2006).
[5] S. S. Marchenkov, On FE-precomplete classes of countably valued logic (Russian), Discrete math., (2), 51–57 (2016).
[6] A. I. Mal'cev, Iterative algebras ans Post manifold, (Russian), Algebra and logic, (2), 5-24 (1966).
[7] A. Salomaa, On sequences of functions over an arbitrary system, Annales Universitatis Turkuensis AI (16), 5–13 (1963).
[8] A. Salomaa, Some analogues of Sheffer functions in infinite-valued logics, Acta philosophica Fennica, 227-235 (1963).
[9] G. P. Gavrilov, On functional completeness in countably valued logic, Problems of cybernetics, 5–64 (1965).
[10] G. P. Gavrilov, Precomplete classes of parcially countably value logic contained all functions of a single variable (Russian), Discrete analysis methods in graph theory and logical functions, 12–24 (1976).
[11] S. S. Marchenkov, On set power of precomplete classes in some classes of countably valued logic functions (Russian), Problems of cybernetics, 109–1981 (2015).
[12] Ju. I. Janov, A. A. Muchnik, On existence of k-valued closed classes without finite basis (Russian), Dokl. Acad. Nauk SSSR, (1), 44–46 (1959).
[13] IG Rosenberg, Über die functionale Vollständigkeit dem mehrvertigen Logiken von mehreren Verändlichen auf endlichen Mengen, Rozpravy Cs. Academie Ved, Ser. Math. Nat. Sci., 3-93 (1970).
[14] M. A. Malkov, Classification of Boolean functions and their closed sets, SOP transactions on applied mathematics, (1), 1-20 (2014).
[15] R. M. Robinson, Primitive recursive functions, Bull. Amer. Math. Soc., bf53, 925-942 (1947).
Cite This Article
  • APA Style

    Maydim Malkov. (2019). Algebra of Countably Functions and Theorems of Completeness. Pure and Applied Mathematics Journal, 8(1), 1-9. https://doi.org/10.11648/j.pamj.20190801.11

    Copy | Download

    ACS Style

    Maydim Malkov. Algebra of Countably Functions and Theorems of Completeness. Pure Appl. Math. J. 2019, 8(1), 1-9. doi: 10.11648/j.pamj.20190801.11

    Copy | Download

    AMA Style

    Maydim Malkov. Algebra of Countably Functions and Theorems of Completeness. Pure Appl Math J. 2019;8(1):1-9. doi: 10.11648/j.pamj.20190801.11

    Copy | Download

  • @article{10.11648/j.pamj.20190801.11,
      author = {Maydim Malkov},
      title = {Algebra of Countably Functions and Theorems of Completeness},
      journal = {Pure and Applied Mathematics Journal},
      volume = {8},
      number = {1},
      pages = {1-9},
      doi = {10.11648/j.pamj.20190801.11},
      url = {https://doi.org/10.11648/j.pamj.20190801.11},
      eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.pamj.20190801.11},
      abstract = {An algebraic approach to the theory of countable functions is given. Compositions (superpositions) of functions are used instead of recursions. Arithmetic and analytic algorithms are defined. All closed sets are founded. Mathematically precise definitions of logic algorithms with quantifiers of existence and universality are given. Logic algorithm for fast-growing function is built as example. Classification of functions is given. There are non-computable functions. These functions are fictitious (useless) and their set is continual. The set of computable functions is countable. Incompleteness of disjunction and negation, conjunction and negation, of Pierce, Sheffer and diagonal Webb functions is proved. The completeness of the set of one-place functions and any all-valued essential function (Slupecki theorem) is proved for computable functions. Existence of generators of all computable functions is proved too.},
     year = {2019}
    }
    

    Copy | Download

  • TY  - JOUR
    T1  - Algebra of Countably Functions and Theorems of Completeness
    AU  - Maydim Malkov
    Y1  - 2019/04/09
    PY  - 2019
    N1  - https://doi.org/10.11648/j.pamj.20190801.11
    DO  - 10.11648/j.pamj.20190801.11
    T2  - Pure and Applied Mathematics Journal
    JF  - Pure and Applied Mathematics Journal
    JO  - Pure and Applied Mathematics Journal
    SP  - 1
    EP  - 9
    PB  - Science Publishing Group
    SN  - 2326-9812
    UR  - https://doi.org/10.11648/j.pamj.20190801.11
    AB  - An algebraic approach to the theory of countable functions is given. Compositions (superpositions) of functions are used instead of recursions. Arithmetic and analytic algorithms are defined. All closed sets are founded. Mathematically precise definitions of logic algorithms with quantifiers of existence and universality are given. Logic algorithm for fast-growing function is built as example. Classification of functions is given. There are non-computable functions. These functions are fictitious (useless) and their set is continual. The set of computable functions is countable. Incompleteness of disjunction and negation, conjunction and negation, of Pierce, Sheffer and diagonal Webb functions is proved. The completeness of the set of one-place functions and any all-valued essential function (Slupecki theorem) is proved for computable functions. Existence of generators of all computable functions is proved too.
    VL  - 8
    IS  - 1
    ER  - 

    Copy | Download

Author Information
  • Department of Mathematics, Research Center for Artificial Intelligence, Moscow, Russia

  • Sections