Talk:Definable set

Relation to decidable sets

This is to the anonymous editor from California who is trying to add the following sentence:

It is a weaker notion of decidable set since there may not be an algorithm that halts on every input formula.

I am not opposed to adding an explanation of the connection between definable sets (in a possibly finite, possibly countable, possibly uncountable model of an arbitrary theory) and decidable sets (i.e. certain subsets of the natural number). But then we have to do it correctly. This sentence lacks context, to the point that I can't make out whether it's just misleading or plain wrong. After your latest edit comment I am not sure if you are at the right article. Are you confusing definable sets with recursively enumerable sets? The usual context of model theory is full first-order logic including negation, and if a set is definable, defined by a formula φ(x) say, then its complement is also definable: by the formula ¬φ(x). --Hans Adler (talk) 09:22, 26 October 2008 (UTC)

I agree that the sentence about decidability doesn't belong in the lede, and I also don't follow the edit summary here at all. My first thought is there are lots of definable sets in ZFC (for example, ω₅) for which it doesn't make much sense to ask about decidability. It is true that in the context of theories of arithmetic definability is a weaker form of decidability. For example, in Peano arithmetic, the definable sets are exactly the sets in the arithmetical hierarchy, while the decidable sets are the Δ^0_1 sets. But like Hans says, if a set if definable then so is its complement. — Carl (CBM · talk) 20:13, 27 October 2008 (UTC)