Computably enumerable set

Imagine a machine making a long list.

It can name things one by one. It might never stop. It can list many numbers in a row. The list does not have to be in order. You might see a small number first. Then you might see a big one. A machine can also check if a number is on the list. If the number is there, the machine finds it. But if it is not, the machine might work forever.

This is how some sets work.

Imagine a machine making a long list of numbers.

This machine can name items one by one. We call such a set computably enumerable. This name means the machine can list every member. The list can be very long. It might even go on forever. The machine does not have to list them in order. It might list a large number before a small one.

A machine can also check if a number belongs to the set. If the number is in the set, the machine will find it. This is called semidecidability. But if the number is not in the set, the machine might run forever. It will not give you an answer. This is different from a computable set. For those sets, the machine can say "no" too.

Math experts also use the name Diophantine sets. Yuri Matiyasevich found a way to link these ideas. He showed these sets can be found using math equations. These special equations use whole numbers. This work helped solve a famous puzzle called Hilbert's Tenth Problem.

If you have two such sets, you can join them together. You can also find where they overlap. The new sets will still be computably enumerable.

Imagine a machine that works to create a list. It might list numbers one by one. This machine can go on forever if the list is infinite. It does not have to list numbers in order. It might list a huge number before a tiny one. We call a set of numbers like this a computably enumerable set. People also call these sets r.e. or c.e. for short.

These sets have a special way of working. If a number is truly in the set, the machine will find it. This part is called semidecidability. You can think of it like a search that eventually stops. However, there is a catch for numbers not in the set. If a number is not in the set, the machine might run forever. It may never give you a final answer. This is different from a computable set. A computable set is one where the machine can always say "no" too.

Math history shows us different ways to see these sets. Long ago, people used Diophantine sets to describe them. These sets use math equations with whole numbers. A mathematician named Yuri Matiyasevich studied these deeply. He used them to help solve a famous puzzle. This puzzle was known as Hilbert's Tenth Problem. His work showed that every computably enumerable set is a Diophantine set.

There are many specific types of these sets in math. Some are called simple sets or creative sets. These sets are computably enumerable but they are not computable. We also look at the complement of a set. If the opposite of a set is computably enumerable, we call it co-c.e. The complexity class for these sets is called co-RE. There are also sets called productive sets. These special sets are not computably enumerable at all.

Computably enumerable sets follow very steady rules. If you have two such sets, you can combine them. You can find where they overlap or join them together. The new sets will still be computably enumerable. You can also find the preimage of these sets. This means they stay within the same math family. This helps experts understand how different groups of numbers behave. It is like seeing how different shapes fit together in a puzzle.

In the field of computability theory, mathematicians study what can and cannot be solved by an algorithm. One important concept is the computably enumerable set, often abbreviated as c.e. or r.e. A set of natural numbers is computably enumerable if there is an algorithm that can list its members one by one. This process is also called enumeration. If the set is infinite, the algorithm will continue to run forever. However, every single member of the set will eventually appear on the list after a finite amount of time. These members do not need to appear in any specific order, such as from smallest to largest.

There are several ways to define these sets through different mathematical lenses. One way is through semidecidability. A set is semidecidable if an algorithm can confirm when a number belongs to the set. If the input number is in the set, the algorithm will eventually halt and provide an answer. However, if the number is not in the set, the algorithm might run forever without returning any information. This is why these sets are sometimes called partially decidable. In contrast, a set is considered completely decidable, or computable, if the algorithm can always tell you whether a number is in or out of the set.

Another way to view these sets is through the concept of a partial computable function. A set is computably enumerable if it is the domain of such a function. This means the function is defined only for the specific inputs that are members of the set. Alternatively, a set can be described as the range of a total computable function. This means the algorithm produces the members of the set as its output. If the set is infinite, the function can even be chosen to be injective, meaning it never repeats the same value twice. These different perspectives are mathematically equivalent.

History shows us that these ideas emerged through different mathematical paths. Diophantine sets were actually the first way to describe these groups of numbers. Diophantine sets are defined using polynomials with integer coefficients. The variables in these polynomials range over the natural numbers. A set is Diophantine if it contains exactly the non-negative numbers in the range of such a polynomial. A mathematician named Yuri Matiyasevich later proved a major connection here. He showed that every computably enumerable set is also a Diophantine set. This discovery was part of the negative solution to Hilbert's Tenth Problem.

We can find many specific examples of these sets in advanced mathematics. For instance, the set of all provable sentences in an axiomatic system is computably enumerable. There are also special categories like simple sets and creative sets. Both of these types are computably enumerable, but they are not computable. On the other hand, productive sets are a different category because they are not computably enumerable at all. We also study the complement of these sets. If the complement of a set is computably enumerable, we call that set co-computably-enumerable, or co-c.e.

Computably enumerable sets follow predictable rules when they interact with one another. If you take two c.e. sets, A and B, their intersection is also a c.e. set. This means the set of numbers found in both A and B is also listable. Similarly, the union of two c.e. sets is also computably enumerable. You can even combine them into ordered pairs using the Cantor pairing function. The resulting set will remain within the c.e. family. This stability allows mathematicians to build complex systems from simpler parts.

These concepts are deeply connected to the broader study of computational complexity and logic. In complexity theory, the class containing all computably enumerable sets is known as RE. In recursion theory, researchers study the lattice of these sets under inclusion. The Church-Turing thesis also plays a role here. It suggests that any effectively calculable function can be handled by a Turing machine. This connects the abstract idea of an algorithm to the physical reality of computation. Understanding these sets helps us define the very limits of what machines can ever know.