Post's theorem shows that RE, together with its complement co-RE, correspond to the first level of the arithmetical hierarchy.
Теорема Поста показывает, что RE вместе с дополнительным co-RE соответствуют первому уровню арифметической иерархии.