MHB Why Can Effectively Enumerated Theories Not Be Effectively Decidable?

  • Thread starter Thread starter agapito
  • Start date Start date
Click For Summary
An effectively axiomatized theory T allows for the effective enumeration of its well-formed formulas (wff's), but it cannot be effectively decidable due to the lack of an algorithm to determine whether a formula belongs to T. While the set of all formulas in a first-order language is decidable, if a formula A is not in T, it may never be proved by any enumerated derivation, leaving uncertainty about its status. Church's theorem further establishes that predicate calculus is undecidable, reinforcing this limitation. However, if T is consistent, effectively axiomatized, and complete, it becomes decidable, allowing for a definitive determination of A's membership in T. This distinction highlights the complexities of decidability in mathematical logic.
agapito
Messages
46
Reaction score
0
Given an arbitrary effectively axiomatized theory T, the set of its wff's can be effectively enumerated. Why can it not also be effectively decidable? Under the definition of "effectively axiomatized theory" it is effectively decidable what is a wff of its language. Thus my question, thanks for all help.
 
Physics news on Phys.org
agapito said:
Given an arbitrary effectively axiomatized theory T, the set of its wff's can be effectively enumerated. Why can it not also be effectively decidable? Under the definition of "effectively axiomatized theory" it is effectively decidable what is a wff of its language.
I assume a theory $T$ is called effectively axiomatized if its set of axioms is decidable. (The following argument does not change if the set of axioms is only enumerable.) Then indeed $T$ is enumerable. We can systematically construct all derivations, and every formula in $T$ turns out to be the last formula of some derivation. It is also true that the set of all formulas in the given first-order language, whether in or outside $T$, is decidable. However, there is no a priori algorithm to determine whether a formula is in $T$. Namely, if a formula $A$ is not in $T$, then it is never proved by any derivation we enumerate, but we can not be sure that this is the case, i.e., that some future derivation does not prove it. And, as Church's theorem shows, predicate calculus is undecidable.

Note that if $T$ is consistent, effectively axiomatized and complete, which means that $A\in T$ or $\not A\in T$ for every formula $A$ in the language, then $T$ is decidable. Asked whether $A\in T$, we search through all derivations and will eventually encounter either $A$ or $\neg A$ because one or the other is in $T$. If $\neg A\in T$, then $A\notin T$ due to consistency.

Does this help?
 
Evgeny.Makarov said:
I assume a theory $T$ is called effectively axiomatized if its set of axioms is decidable. (The following argument does not change if the set of axioms is only enumerable.) Then indeed $T$ is enumerable. We can systematically construct all derivations, and every formula in $T$ turns out to be the last formula of some derivation. It is also true that the set of all formulas in the given first-order language, whether in or outside $T$, is decidable. However, there is no a priori algorithm to determine whether a formula is in $T$. Namely, if a formula $A$ is not in $T$, then it is never proved by any derivation we enumerate, but we can not be sure that this is the case, i.e., that some future derivation does not prove it. And, as Church's theorem shows, predicate calculus is undecidable.

Note that if $T$ is consistent, effectively axiomatized and complete, which means that $A\in T$ or $\not A\in T$ for every formula $A$ in the language, then $T$ is decidable. Asked whether $A\in T$, we search through all derivations and will eventually encounter either $A$ or $\neg A$ because one or the other is in $T$. If $\neg A\in T$, then $A\notin T$ due to consistency.

Does this help?

Very helpful indeed, I appreciate it.
 
Hello, I'm joining this forum to ask two questions which have nagged me for some time. They both are presumed obvious, yet don't make sense to me. Nobody will explain their positions, which is...uh...aka science. I also have a thread for the other question. But this one involves probability, known as the Monty Hall Problem. Please see any number of YouTube videos on this for an explanation, I'll leave it to them to explain it. I question the predicate of all those who answer this...
I'm taking a look at intuitionistic propositional logic (IPL). Basically it exclude Double Negation Elimination (DNE) from the set of axiom schemas replacing it with Ex falso quodlibet: ⊥ → p for any proposition p (including both atomic and composite propositions). In IPL, for instance, the Law of Excluded Middle (LEM) p ∨ ¬p is no longer a theorem. My question: aside from the logic formal perspective, is IPL supposed to model/address some specific "kind of world" ? Thanks.
Back
Top