Natural Numbers and $A_x=\{y \in A \mid y \leq x\}$

53 Views Asked by At

Suppose A is a arbitrary subset of Natural Numbers and $A_x=\{y \in A \mid y \leq x\}$ with respect to $ n \in A \Longleftrightarrow n \in A_n $ and $A_n$ is finte, which of them is True?

a) A and $A_n$ is decidable.

b) A and $A_n$ is not Necessarily decidable.

c) $A_n$ is decidable but A is not Necessarily.

d) without knowing more about A we couldn't answer.

This is an old Multiple Entrance Exam Question, anyone have any idea?

1

There are 1 best solutions below

0
On BEST ANSWER

Any finite set is decidable, so each $A_n$ is decidable.

Not every set is decidable, so $A$ might not be decidable.

The question is a bit awkward, because, while each $A_n$ is decidable, it is not true that the sequence $\{A_n\}$ is decidable. But if I had to guess, I'd take (c) to mean that each $A_n$ is decidable and $A$ is not necessarily.