Recursive Set

We say that a set $S$ is recursive (decidable) if there exists an algorithm that, given an element $x$ determines whether $x \in S$ .

Example: the set of even numbers is recursive. The algorithm takes $x$ represented in binary and checks whether its least signifficant digit is 0.

Example: the set of all pairs $(T,x)$ such that $T$ is a representation of Turing machine and $x$ is an input such that $T$ terminates on input $x$ , is not recursive.

Example: the set of encodings of all valid first-order logic formulas is not recursive.

Example: the set of all valid formulas of Presburger arithmetic is recursive.