Suppose that $f:P(\mathbb N)\longrightarrow \mathbb N$ and $A$ is a subset of $\mathbb N$. We call $f$ $A$-predicting if the set $\{x\in \mathbb N|x\notin A, f(A\cup x)\neq x \}$ is finite. Prove that there exists a function that for every subset $A$ of natural numbers, it's $A$-predicting. proposed by Sepehr Ghazi-Nezami
Problem
Source: Iran 3rd round 2011-final exam-p7
Tags: function, algebra proposed, algebra
15.09.2011 23:55
Nice! Suppose $A,B \in P(\mathbb{N})$ Put $A \sim B$ if $|A \bigtriangleup B|< \infty$ By this equivalence relation we can write $P(\mathbb{N}) = \bigcup _{i} I_{i}$ , now by axiom of choice select $A_{i}\in I_{i}$, Now for every $X\in I_{j}$ let $f(X)=max(X\cup A_{j})$.
12.06.2020 07:21
Please someone make the above solution clear to me...I can't understand it....Please....
12.06.2020 17:14
@above: Because, it's not written precisely. So, the idea is to consider the equivalence relation: $A\sim B$ iff $A\Delta B$ is finite (their symmetric difference). It's indeed an equivalence relation, so let $C_i, i\in I$ be the corresponding classes of equivalence, where $I$ is some index set (uncountable). Choose a set $A_i$ from each class $C_i$ and define a function $f: P(\mathbb{N})\to \mathbb{N}$ as follows. $f(A_i):=1, \forall i\in I$. For any other $A\subset \mathbb{N}$, let $C_{\alpha}, \alpha\in I$ be the class of equivalence for which $A\in C_{\alpha}$. We define $f(A):=\max(A\Delta A_{\alpha})$. It's well defined since $A\Delta A_{\alpha}$ is finite. One can check, this function satisfies the requirement. Comment. I suppose, such function cannot be construct without AC. The checking it satisfies what needed is simple, but the question is how one can grope the right way of constructing $f$. One can try expanding the definition of $f$ over $P(\mathbb{N})$, starting from defining it on the empty set as $f(\emptyset)=1$. The fact $P(\mathbb{N})$ is not countable is not an issue, since we can map $P(\mathbb{N})$ to some initial segment of ordinals. So, suppose we have already defined $f$ over subsets of naturals complying to the requirement and $A$ is a subset of $ \mathbb{N}$, such that $f(A)$ is not yet defined. We should provide some values for $f(A)$ and $f(A\cup {x})$. The problem here is, it may happen we have already defined $f(A\cup \{x\})$ for many $x\in\mathbb{N}$, so at this point we have no control to define $f(A\cup \{x\})$ the way we want it. This is not good. So, we must somehow simultaneously define $f$ over $A$ and all other sets that differ from $A$ in one, or finitely many elements. So, it should be done in one transaction. That's why we consider some set $A$ and all other sets that differ form $A$ in only finite number of elements. Defining $f(A)$ arbitrarily, one can easily guess how to define $f$ over the rest of those sets.