How is it possible that some infinite sets are decidable?

Question

Note: as you can probably tell, I'm a layman without mathematical maturity but very interested in the foundations of math.

Def. A set is decidable if and only if there is an effective method for telling, for each thing that might be a member of the set, whether or not it really is a member.

Def. Effective method for solving a problem is a method for computing the answer that, if followed correctly and as far as necessary, is logically bound to give the right answer, and no wrong answer in a finite number of steps.

I learned that sets like natural numbers, even numbers, etc. are decidable. I'm having trouble wrapping my mind around how it is possible to have a finite method to decide all the members of an infinite set.

I think I need to understand this deeply to learn about the difference between denumerable sets and uncountable sets. I tried to follow Cantor's proof about uncountable sets, but I have trouble why a power set for example is uncountable.

Edit: Also, are all uncountable sets undecidable?

Answer 1

You are mixing several things from different parts of logic and set theory.

1. When we talk about decidable sets, the standard context is sets of natural numbers, or sets of tuples of natural numbers. And we are talking about them in the sense that there is a Turing machine that given a natural number will always stop and tell us whether or not this number is in the given set.

   Turing machines can be thought of as computers. But not as physical computers. Those are ideal computers which are not limited by time, space, or energy constraints.

   So given a natural number, $n$ is it even? Well, we need to go through all the natural numbers $k$ and ask if $k+k=n$. But in fact we only need to do it for $k\leq n$. So after at most $n$ steps we know if something is even or if it is not even. Therefore the even numbers form a decidable set.

   Bit harder, but the set of prime numbers is also decidable. To judge whether or not $p$ is a prime we need to go through all the natural numbers $n<p$ and ask if there is some $k<p$ such that $n\cdot k=p$. Sure, it might take some time, but it's simple from a complexity point of view. After $p^2$ steps, we can decide if $p$ is a prime or not.

2. When we talk about uncountable sets, this is normally in the setting of some set theory (which may or may not be in the background of what you're doing). There we only talk about existence of bijection between your set and the fixed set $\Bbb N$. If there is such bijection, your set is countable, otherwise it is not.

   You are not required to construct the bijection, or somehow provide a description for it. At least not in the classical settings of mathematics. You simply need to prove that there is one, or that there cannot be one. Cantor's diagonal argument shows that there cannot be a bijection between $\Bbb R$ and $\Bbb N$, so it is therefore the case that $\Bbb R$ is uncountable.

The two concepts are not really related. Decidable sets are countable (or finite), pretty much by the fact by definition as subsets of $\Bbb N$. But in the context of computability theory, the only sets of interest are subsets of $\Bbb N$ (or tuples of natural numbers, as we remarked above). So uncountability does not really come into play here.

Answer 2

Well, a set $A\subseteq{\Bbb N}_0^k$ is decidable if its characteristic function $$\chi_A(x) = \left\{ \begin{array}{ll} 1 & \mbox{if } x\in A,\\ 0 & \mbox{otherwise} \end{array} \right.$$ is computable, i.e., recursive. This can be viewed as ''an effective method'' for telling whether a set $A$ is decidable or not; it can determine whether an element $x$ lies in $A$ or not independent of the property whether $A$ is infinite or not.

There are several closure properties: If $A,B$ are decidable, then $A\cup B$, $A\cap B$ and $\overline A$ are decidable.

Answer 3

For an example of an infinite decidable set, consider the set of all even natural numbers. When have a natural number written down, it is very easy to determine if it is even or not, so the set is decidable. (If it's written down in decimal notation you only need to look at the last digit). Yet there are infinitely many even numbers.

Note that when we say that the method must determine whether each thing is in the set, we don't require that the method has actually been performed on all of the things. It is enough that we're sure that for each thing separately it would be possible to apply the method to it and get the right answer.

---

The notion of "decidable" is usually only used about subsets of a countable set -- usually that countable set is $\mathbb N$, but it can also be the set of all finite bit/byte strings or even the set of all finite sequences of numbers or letters. What these all have in common is that we can imagine writing an element of the set down in full detail and feeding it to some kind of computing machine.

Therefore all decidable sets are countable, because if you have an uncountable set it won't even make sense to ask if it is decidable or not.

There are possible generalizations of the concept to certain uncountable settings, but they are not what one means if one simply says "decidable".

Answer 4

Your confusion is simple but somewhat subtle. You're confusing 'for any' with 'for every'.

It is true that there can be no algorithm for deciding a property - say, even-ness - for every natural number. Obviously that cannot be done in a finite number of steps.

But that is not what an algorithm is required to do. An algorithm is required to be able to answer, for any number you give it, whether that particular number has that property. It's true that you cannot give it infinite numbers to check, and it cannot check infinite numbers. But that doesn't matter. As long as it can give you the correct answer for any number you give it, the set in question is decidable.