more from Herbert B. Enderton

Single Idea 9996

[catalogued under 5. Theory of Logic / K. Features of Logics / 7. Decidability]

Full Idea

A set of expressions is 'decidable' iff there exists an effective procedure (qv) that, given some expression, will decide whether or not the expression is included in the set (i.e. doesn't contradict it).

Gist of Idea

Expressions are 'decidable' if inclusion in them (or not) can be proved


Herbert B. Enderton (A Mathematical Introduction to Logic (2nd) [2001], 1.7)

Book Reference

Enderton,Herbert B.: 'A Mathematical Introduction to Logic' [Academic Press 2001], p.62

A Reaction

This is obviously a highly desirable feature for a really reliable system of expressions to possess. All finite sets are decidable, but some infinite sets are not.