What’s wrong with this “proof” that $\mathbb{R}$ is enumerable?

The fake proof:

  • We know that $ \mathbb{R}$ is uncountable, hence we cannot enumerate over it.
  • But what we do know is that $ \mathbb{Q}$ , the set of rationals, is countable, and even denumerable.
  • We also know that we can construct $ \mathbb{R}$ through what are called Dedekind cuts.
  • We choose to let the partition itself denote a new number and go forth to define mathematical operations on it as to be compatible with the rest of the numbers (mainly $ \mathbb{Q}$ and our new number $ x$ )

Sidenote: I think so far this is standard, and contains nothing false. The actual argument starts below this line.

  • Let us denote the set containing $ x$ as $ S_1 := \mathbb{Q}\cup\{x\}$ . For convenience, the superscript of $ S_1$ is how many new such numbers we have added through the cuts.

  • Since $ \mathbb{Q}$ is countable, we can enumerate over every single rational $ q\in\mathbb{Q}$ to produce an $ r\in\mathbb{R}$ . Do this process $ n$ times and you end up with $ S_n = \mathbb{Q}\cup{x_1}\cup{x_2}\cup\dots\cup{x_n}$ .

  • But $ S_n$ is also enumerable since it has a finite more elements than $ \mathbb{Q}$ .

  • Hence – After enumerating over the entirety of $ \mathbb{Q}$ – Start enumerating over the entirety of $ S_n\setminus\mathbb{Q}$

  • Now we will end up with even newer numbers to put in our set, which we will now call $ S_{n,k}$ where $ n$ represents the enumeration over $ \mathbb{Q}$ and $ k$ represents the enumeration over $ S_n\setminus\mathbb{Q}$ . Do this ad infinitum and you will eventually describe $ \mathbb{R}$ .

I know I went wrong somewhere, I just don’t know where.

Family of Computably Enumerable Sets

Please help prove the following statement:

There exists an single-valued computable enumeration of a family of computably enumerable sets.

Definitions:

1) Let $ S$ be nonempty countable set (possibly finite). Any surjective map $ \nu\colon \omega \twoheadrightarrow S$ from the set $ \omega$ of natural numbers onto the set $ S$ is called an enumeration.

2) An enumeration $ \nu$ is single-valued if $ \nu$ is a bijective, i.e. $ \nu$ (x) /= $ \nu$ (y) for any x /= y

Union of a decidable language with complement of a recursively enumerable language

So the question wants to prove or disprove that ‘a Union of a decidable/recursive(i understand them to be the same) language and the complement of a recursively enumerable language is a recursive/decidable language.’

I think that it is false and the union is recursively enumerable. Since if such a Turing Machine exists that accepts the union, then it must be powerful enough to accept words of the union from the RE language, which would then make it automatically powerful enough to accept the words from the recursive / decidable language.

Is this reasoning right, or am I making a logical mistake somewhere?

Use the Rice’s theorem to prove that the following property of a Recursive Enumerable language L is undecidable

This exercise was taken from the book “Languages and Machines: An Introduction to the Theory of Computation” by Thomas Sudkamp. It refers to exercise 12 (b) chapter 12. Given a language L which is recursive enumerable, I have to prove that the following property is undecidable:

  • L is finite

The text says that it is sufficient to prove that it is a non trivial property.

I tried to solve the exercise as follow:

Consider the empty language $ \emptyset$ , which contains only the empty string λ, in other words $ \emptyset$ = {$ \lambda$ }. Then $ \emptyset^-$ which is the negation of the empty set, will contains some string which is not $ \lambda$ . By doing this, I’ve found a language which is finite and does satisfy the property, but I’ve also found another language which doesn’t satisfy the property because $ \emptyset^-$ it is not finite. In conclusion the property it is not trivial, and by the Rice’s theorem it is impossible to decide that property.

I’m not sure if I’m doing the right thing here and I haven’t found any solution to this exercise… Can anyone help or at least tell me if I’m doing it right?

Thank you very much.

Turing machine and Recursively Enumerable Language

Whether a TM accepts Recursively enumerable language. Decidable or not?

And what if the question was whether a TM accepts a RE language. Decidable or not?


According to my understanding the first one should be decidable right, as it is $ TRIVIAL$ property of TM to accept $ REL$

and the second one should be partially decidable right? as $ Membership$ problem for recursively enumerable language is undecidable, so can we conclude from it that our question whether a turing machine accepts $ a$ RE language is also undecidable?