Algebra of Countably Functions and Theorems of Completeness

Maydim Malkov

doi:doi:10.11648/j.pamj.20190801.11

| Peer-Reviewed |

Algebra of Countably Functions and Theorems of Completeness

Maydim Malkov

Received: 15 February 2019 Accepted: 18 March 2019 Published: 9 April 2019

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

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.

DOI	10.11648/j.pamj.20190801.11
Published in	Pure and Applied Mathematics Journal (Volume 8, Issue 1, February 2019)
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), 2024. 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

Plain Text BibTeX RIS

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

Maydim Malkov

Department of Mathematics, Research Center for Artificial Intelligence, Moscow, Russia

Download PDF

Sections

Plain Text BibTeX RIS

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