Is it possible to have uncountably many functions of the type $$f:\mathbb{N}\longrightarrow\{0,1\}$$ pairwise coinciding only on finitely many values?

My guess is no, but I cannot come with a proof of this.


No, let $f,g,h:\mathbb{N}\rightarrow\{0,1\}$ and suppose that $f$ and $g$ coincide pairwise on only finitely many values. Let $$X=\{n\in\mathbb{N}:f(n)\neq g(n)\}.$$ Note that $X$ is cofinite. Now suppose $f$ and $h$ coincide pairwise on only finitely many values. Note that $$Y=\{n\in\mathbb{N}:f(n)\neq h(n)\}$$ is cofinite. Then, since for all $n$ we have that if $f(n)\neq g(n)$ and $f(n)\neq h(n)$, then $g(n)=h(n)$, we find $$X\cap Y=\{n\in\mathbb{N}:f(n)\neq h(n),\ f(n)\neq g(n)\}=\{n\in\mathbb{N}:g(n)=h(n)\}$$ is infinitely large, as the intersection of two cofinite sets if cofinite.


In fact, you can't even have 3 such functions!

Suppose $f_0, f_1, f_2 : \mathbb{N}\mapsto \{0;1\}$ satisfy $A_i := \{n \in\mathbb{N}\ \mid \ f_0(n) = f_i(n)\}$ is finite for $i=1,2$.

Then, for every $n\notin A_1\cup A_2$, we must have $f_1(n) = f_2(n)$. Hence $f_1$ and $f_2$ coincide on an infinite set.

  • $\begingroup$ +1. You could also say that $\Bbb N=A_0\cup A_1\cup A_2$ (.. otherwise $\{f_0(n),f_1(n),f_3(n)\}$ would have $3$ members for some $n$...) so at least one of $A_0, A_1, A_2$ is infinite. $\endgroup$ – DanielWainfleet Oct 21 '19 at 12:59

Interpreting the functions as indicator functions of subsets of $\mathbb N$ the question can be reformulated as:

Is there an uncountable collection $\mathcal A$ of subsets of $\mathbb N$ such that $(A\Delta B)^{\complement}$ is finite for every pair $A,B\in\mathcal A$?

Or equivalently:

Is there an uncountable collection $\mathcal A$ of subsets of $\mathbb N$ such that $A\cap B$ and $A^{\complement}\cap B^{\complement}$ are both finite for every pair $A,B\in\mathcal A$?

The answer on this is "no" and (as suggested in the comment of bof) for this it is enough to observe that finiteness of $(A\Delta B)^{\complement}$, $(A\Delta C)^{\complement}$ and $(B\Delta C)^{\complement}$ implies the absurd conclusion that $\mathbb N$ is finite on base of: $$\mathbb N\subseteq(A\Delta B)^{\complement}\cup(A\Delta C)^{\complement}\cup(B\Delta C)^{\complement}\tag1$$for any triple $(A,B,C)$ of subsets of $\mathbb N$.

For verification of $(1)$ observe that every $n\in\mathbb N$ we can find sets $U\in\{A,A^{\complement}\}$,$V\in\{B,B^{\complement}\}$,$W\in\{C,C^{\complement}\}$ such that $n\in U\cap V\cap W$ and it is not difficult to verify that: $$U\cap V\cap W\subseteq(A\Delta B)^{\complement}\cup(A\Delta C)^{\complement}\cup(B\Delta C)^{\complement}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.