# Maximal size of a family of incompatible partial finite functions with common domain size

Suppose $$X$$ is a set and $$\{ a_i : i < M \}$$ is a set of subsets of $$X$$, each of finite size $$n$$. Suppose for each $$i$$, $$f_i : a_i \to \{ 0,1 \}$$ is a function, and for $$i, there is some $$x$$ such that $$f_i(x) \not= f_j(x)$$.

What is the largest possible value of $$M$$? It should be $$2^n$$ as in the obvious case $$|X| = n$$, but I cannot formulate a proof.

• Is $X$ finite? Is $n$ finite? Is $M$ finite? Commented Apr 29 at 13:55
• @AsafKaragila I clarified that $n$ is finite. I don't assume anything about $X$ or $M$.
– mbsq
Commented Apr 29 at 14:09
• @kodlu For each $i$ we assign a function $f_i$ with domain $a_i$ and codomain $\{0,1\}$. I thought that was clear.
– mbsq
Commented Apr 29 at 14:11
• I wouldn't be surprised if there's a combinatorial proof that $M=2^n$ is the largest you can get by some counting argument, e.g. pick $a_0$, then find $n$ things which disagree on the various elements; then for each one of those find $n$ things which disagree with it, etc. and somehow concluding that if there are more than $2^n$ functions, then there will be one that is necessarily equal to another. Or some such. Commented Apr 29 at 14:17
• When you say $f_i(x) \ne f_j(x)$, it implies that $x \in a_i \cap a_j$, right? Then I think you get an inequality $f(n) \le 1 + \sum_{k \ge 1} \binom{n}{k} f(n - k)$, by grouping by which $x \in a_0$ the other $a_i$ differ on and then for each group removing those $x$. Replacing by $f(n) \le 2^n f(n - 1)$ already gives $f(n) \le 2^{\sim \frac12 n^2}$. Commented Apr 29 at 14:40

Measure theory to the rescue!

WLOG we can assume that $$X$$ is countably infinite (exercise). Consider the Lebesgue measure on the Cantor space $$2^X$$.

Suppose we are given a family of partial functions each of size $$n$$ as hypothesized. Each $$f_i$$ determines a basic clopen set $$C_i$$ of measure $$2^{-n}$$. Since they pairwise disagree at some coordinate, these sets are pairwise disjoint. Since the whole space has measure 1, there are at most $$2^n$$-many sets $$C_i$$.

• This is great! Actually you don't even need measure theory beyond counting finite sets: by contradiction assume $M > 2^n$, pass to a finite subset still bigger than $2^n$, and then take $X = \bigcup a_i$, which is a finite union of finite sets hence finite. (I assume this is similar to the reduction to $X$ countable that you had in mind.) Commented May 2 at 7:32

Let's call a family of $$f_i$$ as above an $$n$$-family. Let us show by induction on $$n$$ that an $$n$$-family can't have size larger than $$2^n$$.

Suppose we know this is true for all $$n, but there is an $$m$$-family $$\mathcal{F}$$ of size $$2^{m}$$ and some $$f \not\in \mathcal{F}$$ with domain $$\{x_n : n < m \}$$ such that $$\mathcal{F} \cup \{f\}$$ still forms an $$m$$-familiy.

Consider $$\mathcal{F}_0 = \{g \in \mathcal{F} : x_0 \not\in \operatorname{dom}(g) \vee g(x_0) = f(x_0) \}$$. Then note that $$\vert \mathcal{F}_0\vert \geq 2^{m-1}$$, because if $$\vert \mathcal{F} \setminus \mathcal{F}_0 \vert > 2^{m-1}$$, then $$\{ g \restriction (\operatorname{dom}(g) \setminus \{x_0 \} ) : g \in \mathcal{F} \setminus \mathcal{F}_0\}$$ is an $$m-1$$-family of size $$>2^{m-1}$$.

Now continue like this and define $$\mathcal{F}_n = \{ g \in \mathcal{F}_{n-1} : x_n \notin \operatorname{dom}(g) \vee g(x_n) = f(x_n) \}$$ and show that $$\vert \mathcal{F}_n \vert \geq 2^{m-n}$$.

After $$m$$ steps we have reached $$\vert \mathcal{F}_m\vert \geq 2^0 = 1$$. Let $$g \in \mathcal{F}_m$$. Then there should be $$n$$ so that $$g(x_n) \neq f(x_n)$$ but there isn't by construction.

• Very nice. But one thing-- Should you pick $F_0$ to be a subset of the set you defined of size exactly equal to $2^{m-1}$? That way you can continue the induction and say $| F_0 \setminus F_1 | \leq 2^{m-2}$, etc.
– mbsq
Commented Apr 29 at 22:53
• I don't think it matters, does it? If a set has size at least $2^m$ and is partitioned into two subsets, one of the pieces has size at least $2^{m-1}$. Commented Apr 29 at 23:38
• I must say I'm not 100% convinced by my own argument right now, since I don't see in the general case how to get the $m-n$-family if it is not guaranteed that all members of $\mathcal{F}_{n-1}$ contain all $x_0, ..., x_{n-1}$ in their domain. Commented Apr 29 at 23:52
• On the first comment, you're right (oops). On the second, I tried to repair it but I messed up...
– mbsq
Commented Apr 30 at 0:50
• How do you get $|\mathcal{F}_1| \ge 2^{m - 2}$? You can't necessarily remove both $x_0$ and $x_1$ from the domains to get an $m - 2$ family since $x_0$ might not be in all the domains to begin with. Commented Apr 30 at 9:04