Uncountably many functions coinciding only finitely many values

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.


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

Tags:

Set Theory

Cardinals

Related

Prove that $x^3+2y^3+4z^3\equiv6xyz \pmod{7} \Rightarrow x\equiv y\equiv z\equiv 0 \pmod{7}$ Showing that $\overline{\mathbb{Z}}/n\overline{\mathbb{Z}}$ is infinite Are there a finite number of trees with $k$ leaves and no vertices of degree $2$? Number of integer solutions to the diophantine equation How many right triangles can be built from points Does the Fundamental Theorem of Algebra follow from the real Spectral Theorem? A bijection $\phi:\mathbb R \to \mathbb R$ that must be an identity Use proof by mathematical induction to prove explicit formula for recursive sequence is correct Intuition behind the paradox of instantaneous heat propagation Show: $\int_0^1\int_0^1\frac{dx\,dt}{(xt)^2+xt+1}=\frac{2}{\sqrt3}\mathrm{Cl}_2\left(\tfrac{2\pi}{3}\right)$ Show that $\sum_{k=0}^{n+1}\left(\binom{n}{k}-\binom{n}{k-1}\right)^2 = \frac{2}{n+1}\binom{2n}{n}$ Show for isometry $T:V \rightarrow V$, $\frac{1}{n}\sum_{i=0}^{n-1} T^i$ converges to the orthogonal projection on $ker(T-I)$.

Recent Posts