Hello Meloman, and welcome to Wikipedia! I hope you like it here and decide to stay.
Here are some tips to help you get started:
- Read the tutorial and learn how to edit a page.
- Experiment in the sandbox.
- Follow the Simplified Ruleset.
- Try to edit from a neutral point of view.
- Use talk pages to communicate with other editors.
- Be bold in updating pages.
- Eventually, read the Manual of Style and learn about the Five Pillars of Wikipedia.
- And most importantly, have fun!
If you need any help, see the help pages and glossary, add a question to the help desk, or ask me on my talk page.
I hope you will enjoy editing and being a Wikipedian. Good luck! — Bcat
Hello Melloman. I edited first-order logic since your statement that dyadic predicate logic is decidable is incorrect. The other statement regarding a recursive set of axioms is correct, but I suggest changing it to a recursively enumerable set. If the set is not recursively enumerable then there is no way of determining whether some statement is an axiom of the theory. It also does not imply that the axioms form a recursive set. Nortexoid 29 June 2005 01:33 (UTC)
- Thank you for correcting my remark on dyadic logic :) Meloman
- Unfortunately, this definition of first-order (FO) theory does not cover properly the notion: instead, this is the definition of a FO recursively-enumerable (also called recursively axiomatizable) theory. Moreover, there is a theorem (I cannot give you a reference right now, but the idea is rather simple) that if a FO theory is axiomatizable using a r.e. set of axioms, then it can be axiomatized using recursive set of axioms, so your new definition is precisely the same as was before. At the same time, there exist FO theories of arbitrary complexity!
- I cannot say much about this other than that there exists r.e. sets that are not recursive. If a theory T is set of statements that is r.e., it does not imply that T is recursive--only semirecursive (although the converse is true). Perhaps you are thinking of finitely axiomatizable theories. Nortexoid 30 June 2005 05:54 (UTC)
- Yes, "If a theory T is set of statements that is r.e., it does not imply that T is recursive--only semirecursive". What I mean is that if it is axiomatizable with a r.e. set of axioms, then it is axiomatizable with a recursive set of axioms.
- I cannot say much about this other than that there exists r.e. sets that are not recursive. If a theory T is set of statements that is r.e., it does not imply that T is recursive--only semirecursive (although the converse is true). Perhaps you are thinking of finitely axiomatizable theories. Nortexoid 30 June 2005 05:54 (UTC)
- Take TA (true arithmetic - the set of arithmetic sentences that are true on standard interpretation): it is neither recursive (i.e., not in \Sigma_0 in arithmetic hierarchy), nor rec.enumerable (i.e., not in \Sigma_1), nor in any \Sigma_n. In fact, it is not an arithmetic set at all! Which intuitively means that it is highly undecidable. But it is a theory.
- The proper notion is: a FO theory is a set of FO sentences that contains FO logic (so called predicate calculus) and closed under rules of (MP) and (Gen). In particular, a widely explored is the following notion: the FO theory of a (given) class of FO structures. In general, it is niether recursive, nor r.e. Detail on definitions are, e.g., here.
- Simply consistent but not omega-consistent theories may not be closed under Generalization, but they are still FO theories. Unless they have an induction axiom or an omega-rule, that definition does not in general hold. I'm unqualified to speak on true arithmetic. Nortexoid 30 June 2005 05:54 (UTC)
- Yes, I had some doubts about (Gen) rule at the moment I wrote the note above. What I wanted to say is that the FO theory of a class of FO structures need not to be recursively axiomatizable, but it is a theory. And there is a vast (meta)theory about it and about duality between classes of structures and FO theories. That's why I added "(recursively-)enumerable" prefix to the definition of a FO theory, in order not to rule out other important FO theories.
Start a discussion with Meloman
Talk pages are where people discuss how to make content on Wikipedia the best that it can be. Start a new discussion to connect and collaborate with Meloman. What you say here will be public for others to see.
