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.


3 Answers 3


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$ Oct 21, 2019 at 12:59

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.


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}$$


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .