Today in my Computing class i came across the theorem which states that., If language $L$ and $\Sigma^*\setminus L$ are recursively enumerable then L is recursive (total turing machine).
Which looks very similar to the Δ elemantary class which has the property that if a model $M$ and its complement are Δ elementary class then $M$ is elementary.
So i am curious as to how do some of the elementary and Δ elementary classes relate to recursively enumerable and recursive languages?
For example: Connected graphs are not elementary class. How does that problem translate to turing machine? (As i can write a halting program to find whether a graph is connected or not).
EDIT: Seems like decidability of First-order theories has got lot to do with the recursive-enumerability of the Language (Godel's theorem). I instinctively feel that there is some more relation to Δ elementary and recursively enumerable languages and i still dont completely get it. Or does a elementary class decide the 'decidability' of the theory?