# Uncountably many functions coinciding only finitely many values

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

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.

• +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. – 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}$$