TLDR: Decidability in logic refers to whether a decision problem has an effective method to derive the correct answer. Some logical systems are decidable, meaning there is a method to determine whether a formula is valid or not. However, many important problems are undecidable, meaning there is no method to determine membership in all cases. Decidability also applies to theories, which are sets of formulas. A theory is decidable if there is an effective procedure to determine whether a formula is a member of the theory or not. There are several examples of decidable and undecidable theories in mathematics.

Decidability in logic is all about whether we can effectively determine the answer to a decision problem. In logic, a decision problem is a true/false problem that can be answered with a yes or no. For example, in propositional logic (a simple form of logic), we can determine whether a propositional formula is valid or not using the truth-table method. This means that propositional logic is decidable.

However, when we move to more complex logical systems like first-order logic and higher-order logic, things become more challenging. In general, these systems are undecidable, meaning there is no effective method to determine whether a formula is valid or not. This is because these systems allow for more expressive power and can describe more complex mathematical structures.

Decidability also applies to theories, which are sets of formulas that are closed under logical consequence. A theory is decidable if there is an effective procedure to determine whether a formula is a member of the theory or not. For example, the theory of real closed fields and Presburger arithmetic are decidable, meaning we can effectively determine whether a formula belongs to these theories or not.

On the other hand, there are undecidable theories like the theory of groups and Robinson arithmetic. These theories have been proven to be undecidable, meaning there is no effective method to determine membership in all cases.

In summary, decidability in logic is about whether we can effectively determine the answer to a decision problem or whether a formula belongs to a theory. Some logical systems and theories are decidable, while others are undecidable. Undecidability is often a result of the expressive power and complexity of the logical system or theory.

Related Links:

• Logic
• Undecidable problem