Newton da Costa
Encyclopedia
Newton Carneiro Affonso da Costa (born on 16 September in 1929 in Curitiba
, Brazil
) is a Brazilian mathematician
, logician, and philosopher. He studied engineering and mathematics at the Federal University of Paraná
in Curitiba
and the title of his 1961 Ph.D. Dissertation was Topological spaces and continuous functions.
and its application to various fields such as philosophy, law
, computing
, and artificial intelligence
. He is one of the founders of this non-classical logic
. In addition, he constructed the theory of quasi-truth that constitutes a generalization of Alfred Tarski
's theory of truth, and applied it to the foundations of science.
, generalized Galois theory
, axiom
atic foundations of quantum theory and relativity
, complexity theory
, and abstract logics. Da Costa has significantly contributed to the philosophy of logic
, paraconsistent modal logic
s, ontology
, and philosophy of science
. He served as the President of the Brazilian Association of Logic and the Director of the Institute of Mathematics at the University of Sao Paulo
. He received many awards and held numerous visiting scholarships at universities and centers of research in all continents.
Da Costa and physicist Francisco Antônio Dória
axiomatized large portions of classical physics
with the help of Suppes predicates. They used that technique to show that for the axiomatized version of dynamical systems theory
, chaotic properties of those systems are undecidable and Gödel-incomplete, that is, a sentence like X is chaotic is undecidable within that axiomatics. They later exhibited similar results for systems in other areas, such as mathematical economics.
Da Costa believes that the significant progress in the field of logic will give rise to new fundamental developments in computing and technology, especially in connection with non-classical logics and their applications.
. He is also co-author with Chris Mortensen of the definitive pre-1980 history of variable-binding term operators in classical first order logic: “Notes on the theory of variable-binding term operators”, History and Philosophy of Logic, vol.4 (1983) 63-72.
, Da Costa has published two papers with conditional relative proofs of the consistency of P = NP with the usual
set-theoretic axioms ZFC. The results they obtain are similar to the results of DeMillo and Lipton (consistency of P = NP with fragments of arithmetic) and those of Sazonov and Maté (conditional proofs of the consistency of P = NP with strong systems).
Basically da Costa and Doria define a formal sentence [P = NP]' which is the same as P = NP in the standard model for arithmetic; however, because [P = NP]' by its very definition includes a disjunct that is not refutable in ZFC, [P = NP]' is not refutable in ZFC, so ZFC + [P = NP]' is consistent (assuming that ZFC is). The paper then continues by an informal proof of the implication
However, a review by Ralf Schindler points out that this last step is too short and contains a gap. A recently published (2006) clarification by the authors shows that their intent was to exhibit a conditional result that was dependent on what they call a "naïvely plausible condition". The 2003 conditional result can be reformulated, according to da Costa and Doria 2006 (in press), as
So far no formal argument has been constructed to show that ZFC + [P = NP]' is omega-consistent.
In his reviews for Mathematical Reviews
of the da Costa/Doria papers on P=NP, logician Andreas Blass
states that "the absence of rigor led to numerous errors (and ambiguities)"; he also rejects da Costa's "naïvely plausible condition", as this assumption is "based partly on the possible non-totality of [a certain function] F and partly on an axiom equivalent to the totality of F".
Curitiba
Curitiba is the capital of the Brazilian state of Paraná. It is the largest city with the biggest economy of both Paraná and southern Brazil. The population of Curitiba numbers approximately 1.75 million people and the latest GDP figures for the city surpass US$61 billion according to...
, Brazil
Brazil
Brazil , officially the Federative Republic of Brazil , is the largest country in South America. It is the world's fifth largest country, both by geographical area and by population with over 192 million people...
) is a Brazilian mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
, logician, and philosopher. He studied engineering and mathematics at the Federal University of Paraná
Universidade Federal do Paraná
Federal University of Paraná is a university headquartered in Curitiba, Paraná, Brazil.Established on December 19, 1912 and initially named as Universidade do Paraná , the Universidade Federal do Paraná – UFPR is regarded as the oldest Brazilian university.In 1920, the federal government split...
in Curitiba
Curitiba
Curitiba is the capital of the Brazilian state of Paraná. It is the largest city with the biggest economy of both Paraná and southern Brazil. The population of Curitiba numbers approximately 1.75 million people and the latest GDP figures for the city surpass US$61 billion according to...
and the title of his 1961 Ph.D. Dissertation was Topological spaces and continuous functions.
Paraconsistency
Da Costa's international recognition came especially through his work on paraconsistent logicParaconsistent logic
A paraconsistent logic is a logical system that attempts to deal with contradictions in a discriminating way. Alternatively, paraconsistent logic is the subfield of logic that is concerned with studying and developing paraconsistent systems of logic.Inconsistency-tolerant logics have been...
and its application to various fields such as philosophy, law
Law
Law is a system of rules and guidelines which are enforced through social institutions to govern behavior, wherever possible. It shapes politics, economics and society in numerous ways and serves as a social mediator of relations between people. Contract law regulates everything from buying a bus...
, computing
Computing
Computing is usually defined as the activity of using and improving computer hardware and software. It is the computer-specific part of information technology...
, and artificial intelligence
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
. He is one of the founders of this non-classical logic
Non-classical logic
Non-classical logics is the name given to formal systems which differ in a significant way from standard logical systems such as propositional and predicate logic. There are several ways in which this is done, including by way of extensions, deviations, and variations...
. In addition, he constructed the theory of quasi-truth that constitutes a generalization of Alfred Tarski
Alfred Tarski
Alfred Tarski was a Polish logician and mathematician. Educated at the University of Warsaw and a member of the Lwow-Warsaw School of Logic and the Warsaw School of Mathematics and philosophy, he emigrated to the USA in 1939, and taught and carried out research in mathematics at the University of...
's theory of truth, and applied it to the foundations of science.
Other fields; foundations of physics
The scope of his research also includes model theoryModel theory
In mathematics, model theory is the study of mathematical structures using tools from mathematical logic....
, generalized Galois theory
Galois theory
In mathematics, more specifically in abstract algebra, Galois theory, named after Évariste Galois, provides a connection between field theory and group theory...
, axiom
Axiom
In traditional logic, an axiom or postulate is a proposition that is not proven or demonstrated but considered either to be self-evident or to define and delimit the realm of analysis. In other words, an axiom is a logical statement that is assumed to be true...
atic foundations of quantum theory and relativity
Theory of relativity
The theory of relativity, or simply relativity, encompasses two theories of Albert Einstein: special relativity and general relativity. However, the word relativity is sometimes used in reference to Galilean invariance....
, complexity theory
Complex systems
Complex systems present problems in mathematical modelling.The equations from which complex system models are developed generally derive from statistical physics, information theory and non-linear dynamics, and represent organized but unpredictable behaviors of systems of nature that are considered...
, and abstract logics. Da Costa has significantly contributed to the philosophy of logic
Philosophy of logic
Following the developments in Formal logic with symbolic logic in the late nineteenth century and mathematical logic in the twentieth, topics traditionally treated by logic not being part of formal logic have tended to be termed either philosophy of logic or philosophical logic if no longer simply...
, paraconsistent modal logic
Modal logic
Modal logic is a type of formal logic that extends classical propositional and predicate logic to include operators expressing modality. Modals — words that express modalities — qualify a statement. For example, the statement "John is happy" might be qualified by saying that John is...
s, ontology
Ontology
Ontology is the philosophical study of the nature of being, existence or reality as such, as well as the basic categories of being and their relations...
, and philosophy of science
Philosophy of science
The philosophy of science is concerned with the assumptions, foundations, methods and implications of science. It is also concerned with the use and merit of science and sometimes overlaps metaphysics and epistemology by exploring whether scientific results are actually a study of truth...
. He served as the President of the Brazilian Association of Logic and the Director of the Institute of Mathematics at the University of Sao Paulo
University of São Paulo
Universidade de São Paulo is a public university in the Brazilian state of São Paulo. It is the largest Brazilian university and one of the country's most prestigious...
. He received many awards and held numerous visiting scholarships at universities and centers of research in all continents.
Da Costa and physicist Francisco Antônio Dória
Francisco Antonio Doria
Francisco Antônio de Moraes Accioli Dória is a Brazilian mathematician, philosopher, and genealogist. Francisco Antônio Dória received his B.S...
axiomatized large portions of classical physics
Classical physics
What "classical physics" refers to depends on the context. When discussing special relativity, it refers to the Newtonian physics which preceded relativity, i.e. the branches of physics based on principles developed before the rise of relativity and quantum mechanics...
with the help of Suppes predicates. They used that technique to show that for the axiomatized version of dynamical systems theory
Dynamical systems theory
Dynamical systems theory is an area of applied mathematics used to describe the behavior of complex dynamical systems, usually by employing differential equations or difference equations. When differential equations are employed, the theory is called continuous dynamical systems. When difference...
, chaotic properties of those systems are undecidable and Gödel-incomplete, that is, a sentence like X is chaotic is undecidable within that axiomatics. They later exhibited similar results for systems in other areas, such as mathematical economics.
Da Costa believes that the significant progress in the field of logic will give rise to new fundamental developments in computing and technology, especially in connection with non-classical logics and their applications.
Variable-binding term operators
Da Costa is co-discoverer of the truth-set principle and co-creator of the classical logic of variable-binding term operators—both with John CorcoranJohn Corcoran (logician)
.John Corcoran is a logician, philosopher, mathematician, and historian of logic. He is best known for his philosophical work, helping us to understand such central concepts as the nature of inference, the relationship between logic and epistemology, and the place of proof theory and model theory...
. He is also co-author with Chris Mortensen of the definitive pre-1980 history of variable-binding term operators in classical first order logic: “Notes on the theory of variable-binding term operators”, History and Philosophy of Logic, vol.4 (1983) 63-72.
P = NP
Together with Francisco Antônio DóriaFrancisco Antonio Doria
Francisco Antônio de Moraes Accioli Dória is a Brazilian mathematician, philosopher, and genealogist. Francisco Antônio Dória received his B.S...
, Da Costa has published two papers with conditional relative proofs of the consistency of P = NP with the usual
set-theoretic axioms ZFC. The results they obtain are similar to the results of DeMillo and Lipton (consistency of P = NP with fragments of arithmetic) and those of Sazonov and Maté (conditional proofs of the consistency of P = NP with strong systems).
Basically da Costa and Doria define a formal sentence [P = NP]' which is the same as P = NP in the standard model for arithmetic; however, because [P = NP]' by its very definition includes a disjunct that is not refutable in ZFC, [P = NP]' is not refutable in ZFC, so ZFC + [P = NP]' is consistent (assuming that ZFC is). The paper then continues by an informal proof of the implication
- If ZFC + [P = NP]' is consistent, then so is ZFC + [P = NP].
However, a review by Ralf Schindler points out that this last step is too short and contains a gap. A recently published (2006) clarification by the authors shows that their intent was to exhibit a conditional result that was dependent on what they call a "naïvely plausible condition". The 2003 conditional result can be reformulated, according to da Costa and Doria 2006 (in press), as
- If ZFC + [P = NP]' is omega-consistent, then ZFC + [P = NP] is consistent.
So far no formal argument has been constructed to show that ZFC + [P = NP]' is omega-consistent.
In his reviews for Mathematical Reviews
Mathematical Reviews
Mathematical Reviews is a journal and online database published by the American Mathematical Society that contains brief synopses of many articles in mathematics, statistics and theoretical computer science.- Reviews :...
of the da Costa/Doria papers on P=NP, logician Andreas Blass
Andreas Blass
Andreas Raphael Blass is a mathematician, currently a professor at the University of Michigan. He specializes in mathematical logic, particularly set theory, and theoretical computer science....
states that "the absence of rigor led to numerous errors (and ambiguities)"; he also rejects da Costa's "naïvely plausible condition", as this assumption is "based partly on the possible non-totality of [a certain function] F and partly on an axiom equivalent to the totality of F".
Articles and lectures
- N.C.A. da Costa, Sistemas Formais Inconsistentes. Curitiba, Brazil: Universidade Federal do Paraná, 1963.
- N.C.A. da Costa, Review of the article by Corcoran, Hatcher, and Herring on variable-binding term operators, Zentralblat fur Mathematik, vol. 247, pp. 8–9, 1973.
- N.C.A. da Costa, On the theory of inconsistent formal systems. Notre Dame Journal of Formal Logic 1974 ; 15: 497-510.
- N.C.A. da Costa (with L. Dubikajtis), On Jaskowski's Discussive Logic. Non-Classical Logics, Model Theory and Computability, North-Holland Publishing Company, Amsterdam, pp. 37–56, 1977.
- N.C.A. da Costa (with C. Mortensen), Notes on the theory of variable-binding term operators, History and Philosophy of Logic, vol.4, pp. 63–72, 1983.
- N.C.A. da Costa, Pragmatic probability. Erkenntnis 1986; 25: 141-162.
- N.C.A. da Costa (with Walter Carnielli), Paraconsistent deontic logics. Philosophia – The Philos. Quarterly of Israel, vol.16, numbers 3 and 4, pp. 293–305, 1988.
- N.C.A. da Costa (with V.S. Subrahmanian), Paraconsistent logic as a formalism for reasoning about inconsistent knowledge bases. Artificial Intelligence in Medicine 1989; 1: 167-174.
- N.C.A. da Costa (with F.A. Doria), Undecidability and incompleteness in classical mechanics, International J. Theoretical Physics, vol. 30 (1991), 1041-1073.
- N.C.A. da Costa, Paraconsistent logic. In Stanisław Jaškowski Memorial Symposium, pp. 29–35. Department of Logic, Nicholas Copernicus University of Toruń. 1998.
- N.C.A. da Costa (with O. Bueno and S. French), Is there a Zande Logic? History and Philosophy of Logic 1998; 19: 41-54.
- N.C.A. da Costa (with O. Bueno and A.G. Volkov), Outline of a paraconsistent category theory. In P Weingartner (ed.), Alternative Logics: Do Sciences Need them? Berlin: Springer-Verlag, 2004, pp. 95–114.
- N.C.A. da Costa (with F. A. Doria), Consequences of an exotic definition for P = NP. Applied Mathematics and Computation, vol. 145 (2003), 655-665, and Addendum to `Consequences...' . Applied Mathematics and Computation, vol. 172 (2006), 1364-1367.
- N.C.A. da Costa (with F. A. Doria), Computing the future, in Computability, Complexity and Constructivity in Economic Analysis, ed. K. V. Velupillai, Blackwell, 2005.
- N.C.A. da Costa (with F. A. Doria), Some thoughts on hypercomputation, Applied Mathematics and Computation, in press (2006).
Books
- N.C.A. da Costa, Lógica Indutiva e Probabilidade. Hucitec-EdUSP, 2a. ed., São Paulo, 1993.
- N.C.A. da Costa, Logique Classique et Non-Classique. Paris, Masson, 1997.
- N.C.A. da Costa, O conhecimento científico. São Paulo, Discurso Editorial, 2a. Ed., 1999.
- N.C.A. da Costa, J.M. Abe, J.I. da Silva Filho, A.C. Murolo and C.F.S. Leite Lógica Paraconsistente Applicada. São Paulo, Atlas, 1999.
- N.C.A. da Costa and S. French, Science and Partial Truth: A Unitary Approach to Models and Scientific Reasoning. (Oxford Studies in Philosophy of Science), Oxford University Press, 2003.