Seemingly complex logic/set-theoretic puzzle

Question

I got this puzzle some time ago and it has been bugging me since, I cant solve it - but it is supposedly solvable, I am interested in a solution or any tips on how to proceed.

In front of you is an entity named Adam. Adam is a solid block with a single speaker, through which he hears and communicates. For all propositions (statements that are either true or false) $p$, if $p$ is true and logically knowable to Adam, then Adam knows that $p$ is true. Adam is confined to his physical form, cannot move, and only has the sense of hearing. The only sounds Adam can make are to play one of two pre-recorded audio messages. One message consists of a very high note played for one second, and the other one a very low note played for one second.

Adam has mentally chosen a specific subset of the Universe of ordinary mathematics. The Universe of ordinary mathematics is defined as follows:

Let $S_0$ be the set of natural numbers:

$$S_0 = \{1,2,3,\ldots\}$$

$S_0$ has cardinality $\aleph_0$, the smallest and only countable infinity.

The power set of a set $X$, denoted $2^X$, is the set of all subsets of $X$. The power set of a set always has a cardinality larger than the set itself, $$|2^X| = 2^{|X|}$$

Let $S_1 = S_0 \cup 2^{S_0}$. $S_1$ has cardinality $2^{\aleph_0} = \beth_1$.

Let $S_2 = S_1 \cup 2^{S_1}$. $S_2$ has cardinality $2^{\beth_1} = \beth_2$.

In general, let $S_{n+1} = S_n \cup 2^{S_n}$. $S_{n+1}$ has cardinality $2^{\beth_n} = \beth_{n+1}$.

The Universe of ordinary mathematics is defined as $$\bigcup_{i=0}^\infty S_i$$

This Universe contains all sets of natural numbers, all sets of real numbers, all sets of complex numbers, all ordered $n$-tuples for all $n$, all functions, all relations, all Euclidean spaces, and virtually anything that arises in standard analysis.

The Universe of ordinary mathematics has cardinality $\beth_\omega$.

Your goal is to determine the subset Adam is thinking of, while Adam is trying to prevent you from doing so. You are only allowed to ask Adam yes/no questions in trying to accomplish your task. Adam must respond to each question, and does so by playing a single note. After Adam hears your question, he either chooses the low note to mean yes and the high note to mean no, or the high note to mean yes and the low note to mean no, for that question only. He also decides to either tell the truth or lie for each question after hearing it. If at any time you ask a question which cannot be answered by Adam without him contradicting himself, Adam will either play the low note or the high note, ignoring the question entirely.

Adam has given you an infinite amount of time to accomplish your task. More specifically, the set of both questions asked by you and notes played by Adam can be of any cardinality. If in your strategy this set is uncountably large, for any number of possibilities of Adam's chosen subset, you must describe the order that the elements of this set take place in as completely as possible.

During your questioning, you are keeping track of the following numbers:

$B_1 = $ The number of questions in which Adam had the option of truthfully responding in the affirmative. (This number and the following numbers can of course be cardinal numbers.)

$B_2 = $ The number of questions in which Adam had the option of truthfully responding in the negative.

$B_3 = $ The number of questions in which Adam had the option of falsely responding in the affirmative.

$B_4 = $ The number of questions in which Adam had the option of falsely responding in the negative.

$B_5 = $ The number of questions in which Adam responded with the high note.

$B_6 = $ The number of questions in which Adam responded with the low note.

$B_7 = $ The number of questions.

Let $C = B_1+B_2+B_3+B_4+B_5+B_6+B_7$

A strategy exists which will eventually allow you to determine Adam's chosen subset. Describe such a strategy in which $C$ is as small as possible, for all possibilities of Adam's chosen subset.

Answer 1

First, observe that you can get around the difficulty that you don't know if high means yes or low in the following way. If you really want to ask the question $\varphi$, you should instead ask the question "high means yes for this round if and only if $\varphi$". If high means yes, then this is the same as asking $\varphi$. But if high means no, then it is like asking $\neg\varphi$, and so we may interpret a high anwer to this question as yes to $\varphi$. This transformation therefore ensures that we can in effect know that high means yes. (I mentioned a similar trick in this MO answer about guessing a number, when there can be wrong answers.)

For the lying issue, let me assume that by lying, you mean that Adam first decides whether to lie or tell the truth, and then calculates what a truthful answer would be, and then when telling the truth plays the appropriate tone, but if lying plays the opposite tone. With this interpretation, a similar trick allows us to extract the desired information. Namely, if you want to ask $\psi$, instead ask "you have decided to be truthful for this question iff $\psi$". If Adam decides to be truthful, then this question is answered the same as $\psi$. If he decides to lie, then he calculates what a truthful answer would be, given that he has already decided to lie, which is the opposite of $\psi$, and so he says the opposite of this. In this way, the double negation of the transformation allows us to get the desired information.

Combining the two transformations allows us to get answers to any desired question.

Now, we simply proceed as follows. Since it seems permissible in the world of your question, let us enumerate all the elements of what you call the universe of ordinary mathematics, and ask of each such element whether it is in Adam's set, using the transformations above. In this way, we find out exactly the set of which he is thinking.

The end result is $\beth_\omega$ many questions. This is the optimal in the sense that any smaller bound on the number of questions would be less than $\beth_n$ for some $n$, with only $\beth_{n+1}$ many possible patterns of answers, but there are $\beth_{\omega+1}$ many sets that Adam might be considering.

Incidently, what you call the universe of ordinary mathematics is closely related to what is known in set theory as $V_{\omega+\omega}$, which is a model of the Zermelo axioms of set theory, one of the first axiomatizations of set theory. The $V$ hierarchy begins with $V_0$ being the empty set, and $V_{\alpha+1}=P(V_\alpha)$ and $V_\lambda=\bigcup_{\alpha\lt\lambda} V_\alpha$ for limit ordinals $\lambda$. Your universe is contained within $V_{\omega+\omega}$, but is actually missing huge parts of $V_{\omega+1}$, because you started only with the natural numbers, rather than the hereditary finite sets. For example, the set $\{\ a_k\mid k\in\mathbb{N}\ \}$, where $a_k=\{\{\{\cdots\}\}\}$ has depth $k$, is missing from your universe, but exists in $V_{\omega+1}$. It follows that your world of mathematics does not have the set HF consisting of all hereditary finite sets, or any similar set with unbounded finite depths. From this, it follows that your world does not satisfy some of the very elementary axioms of set theory, which would allow you to construct HF from the natural numbers. For example, the set mentioned above is the result of a very simple induction on finite-depth finte sets.

The fact that $V_{\omega+\omega}$ itself has no sets of size $\beth_\omega$ is precisely what led to the realization that the Zermelo axioms are too weak to prove even that $\beth_\omega$ exists. This realization led directly to the addition of the Replacement axiom to the axioms of set theory, resulting in the theory now known as ZFC.

Answer 2

I wonder why Adam cannot reason as follows:

If the answer to the question is yes, then I will answer truthfully and use the high note to mean "yes". Thus I will play the high note.

If the answer to the question is no, then I will answer truthfully and use the high note to mean "no".
Thus I will play the high note.

Suppose I get asked a question of the form "Does the high note mean 'yes' iff $\varphi$?" Well, I don't know whether the high note means yes until I know what the answer to the question is. But if $\varphi$ is true and I assume that the high note means 'yes', then the answer is 'yes', which I will signify by playing the high note. So this is at least a consistent answer. If $\varphi$ is true and I assume that the high note means "no", then the answer to the question is "no", which I will signify by playing the high note. Thus, so long as $\varphi$ is true, it doesn't matter whether I think the high note means 'yes' or 'no', since both assumptions are consistent and lead to the same answer: play the high note.

Now suppose $\varphi$ is false. Assume first that the high note means 'yes'. Then the answer to the question is 'no', so since I will answer truthfully and play the high note, the answer is no. That's a contradiction. So now let me assume that the high note means 'no'. Then the answer to the question is 'yes', so then the high note signifies 'yes', also a contradiction! What do I do in this situation? Ah, the rules say that if there is no way to answer without contradicting myself, then I can answer however I want. I will play the high note, since I am after all supposed to be giving away as little information as possible and if I play the high note every time then I am obviously giving away no information whatsoever.

Answer 3

Based on the answers proposed to this question, I think this problem is ill-defined. The set of possible questions and assignment of truth valuations is not well defined. A fair definition of a "question" would be to specify a sset $X \subseteq \beth_\omega$, where yes means that the chosen set is inside $X$ and no means it is not. In this case, Pete's answer obviously proves that Adam always has a winning strategy.