Sorolhatóság

Sorolhatóság is a term used in Hungarian mathematics and logic to describe the property of being listable or enumerable. In set theory it refers to whether the elements of a set can be arranged in a sequence, that is, whether there exists a systematic listing of the elements.

Formally, a set S is called sorolható (felsorolható) if there is a bijection between S and a subset of the natural numbers N. Equivalently, S is finite or countably infinite. In this sense, finite sets and countably infinite sets are sorolható, whereas sets that are uncountable, such as the real numbers, are not. The term is often used interchangeably with “countable,” though some authors reserve “countable” to mean finite or countably infinite and reserve “denumerable” for the infinite case.

In computability theory, a closely related concept is recursive enumerability. A subset A of N is called rekurzíve felírható or recursively enumerable (RE) if there exists a Turing machine that outputs all and only the elements of A, possibly with repetition, in some order. RE sets can be listed by an algorithm, but there may be no algorithm that decides membership (i.e., whether a given number belongs to A). Every decidable (recursive) set is RE, but the converse is not true; the halting problem is a classic example of an RE set that is not decidable.

Examples illustrate the distinction: the set of natural numbers, the set of prime numbers, and the set of computable real numbers are sorolható/RE; the set of all real numbers is not sorolható. The concept helps formalize ideas of listing, enumerability, and computable listing within mathematics.