This problem is proposed by bobson (the surjective condition is added by me). For convenience, denote the set of all non-empty finite subsets of $\mathbb{N}_0$ by $X$, and let $g:X\rightarrow \mathbb{N}$ such that \[ g(A)=\sum_{i\in A} 2^i \quad\forall A\in X\]It's easy to show that $g$ is bijective. From (iii), combined with Lucas' thm, one can get that $g^{-1}(a)\subseteq g^{-1}(f(a,b))$ and $g^{-1}(b)\subseteq g^{-1}(f(a,b))$. Hence, \[g^{-1}(a)\cup g^{-1}(b) \subseteq g^{-1}(f(a,b)) \quad \forall a,b\in\mathbb{N} ......(1)\]Since $f$ is surjective, we can assume that for a given non-negative integer $k$, $f(x,y)=2^k$. From (1), $g^{-1}(x)\cup g^{-1}(y) \subseteq \{ k\}$. Because $g^{-1}(x)$ and $g^{-1}(y)$ are both non-empty, they are both $\{ k\}$. That is, $x=y=2^k$. So, \[f(2^k,2^k)=2^k\quad \forall k\in\mathbb{N}_0.......(2)\]For $a,b\in\mathbb{N}$ s.t. $g^{-1}(a)\cap g^{-1}(b) = \O$, one can show that $g(g^{-1}(a)\cup g^{-1}(b))=a+b$. Also, from (1), we can get that $f(a,b)\geq g(g^{-1}(a)\cup g^{-1}(b))=a+b$. Combined with (i), \[f(a,b)=a+b\quad when\quad g^{-1}(a)\cap g^{-1}(b) = \O.......(3)\]Lemma For all $n\in\mathbb{N}$, $f(n,n)=n$. Proof: We can prove it by induction. If $|g^{-1}(n)|=1$, then the lemma is equivalent to (2). If the lemma holds when $|g^{-1}(n)|=i$, then if $|g^{-1}(n)|=i+1$, suppose that $k\in g^{-1}(n)$. By (ii), (2), (3) and the assumption, \[f(n,n)=f(f(n-2^k,2^k),f(2^k,n-2^k))=f(f(f(n-2^k,2^k),2^k),n-2^k)=f(f(n-2^k,f(2^k,2^k)),n-2^k)=f(f(n-2^k,2^k),n-2^k)\]\[=f(n,n-2^k)=f(f(2^k,n-2^k),n-2^k)=f(2^k,f(n-2^k,n-2^k))=f(2^k,n-2^k)=n\]And the lemma is proved. Back to the main problem. $\forall a,b\in\mathbb{N}$, if $g^{-1}(a)\cap g^{-1}(b)\neq \O$, let $c=g(g^{-1}(a)\cap g^{-1}(b))$. By the lemma and (3), \[f(a,b)=f(f(a-c,c),f(c,b-c))=f(f(f(a-c,c),c),b-c)=f(f(a-c,f(c,c)),b-c)=f(f(a-c,c),b-c)=f(a,b-c)=a+b-c\]which means that $f(a,b)=g(g^{-1}(a)\cup g^{-1}(b))$. In conclusion, $f(a,b)=g(g^{-1}(a)\cup g^{-1}(b))\forall a,b\in\mathbb{N}$, and one can easily verify that $f$ is a solution. Indeed, $f$ is the bitwise-or operation.

Denote $\&$ to be the bitwise and operation and $|$ as the bitwise or operation. We work in base two. From condition iii, by Lucas's Theorem, $f(a,b) \& a = a$ and $f(a,b) \& b = b$ so $f(a,b) \& (a | b) = (a|b)$. In particular, pick $b$ such that $a\&b=0$. Then $f(a,b) \ge a+b$ because $a|b = a+b$, but since $f(a,b)\le a+b$ by condition i, $f(a,b)=a+b=a|b$. Now pick $b$ such that $\max\{a,b\}$ has $k$ digits in base 2 and $a|b = 2^k-1$. Then $f(a,b)\ge 2^k-1$. Since $f(a,b) \& (a | b) = (a|b) = 2^k-1$, the next smallest possible value of $f(a,b)$ is $2^{k+1}-1 > 2(2^k-1) \ge a+b$ contradiction with condition i, so $f(a,b) = 2^k-1 = a|b$. The hard part is where $a|b \ne 2^k-1$ and $a\&b \ne 0$. This case will use condition ii but since it's almost midnight here I'll leave this case for tomorrow.

We claim the answer is binary OR (which clearly works), denoted by $\odot$. We'll denote $f(a,b)$ as $a \boxtimes b$, which is associative and surjective and prove that $a \boxtimes b$ is $a \odot b$ for $a,b \le 2^k$ by induction on $k$. The base case $k = 0$ is clear (meaning $1 \boxtimes 1 = 1$). Assume now it's true up to $2^{k-1}$. First, note that by Lucas theorem, whenever $n < 2^k$ we get \[ n \boxtimes 2^k = 2^k \boxtimes n = 2^k + n. \](since the $f$-value is also $\le 2^k+n$). Now, for $a,b < 2^{k-1}$ we get \[ (a+2^{k-1}) \boxtimes b = 2^{k-1} \boxtimes a \boxtimes b = 2^{k-1} \boxtimes (a \odot b) = 2^{k-1} + a \odot b. \]Similarly for the symmetric case. Finally, \begin{align*} (a+2^{k-1}) \boxtimes (b+2^{k-1}) &= a \boxtimes 2^{k-1} \boxtimes 2^{k-1} \boxtimes b = a \boxtimes 2^{k-1} \boxtimes b \\ &= (a + 2^{k-1}) \boxtimes b = 2^{k-1} + a \odot b. \end{align*}So all that remains is to show $2^k \boxtimes 2^k = 2^k$, which follows from surjectivity since $a \boxtimes b \ge \min\{a,b\}$. Thus induction done.

The answer is $f(x,y)=x|y$ only. It clearly works. Now I show it is the only solution. Claim 1: $f(2^k,2^k)=2^k$ Proof: there exists $x,y$ such that $f(x,y)=2^k$. By the binomial coefficient condition, $x=y=2^k$ Claim 2: $f(x,2^k)=x|2^k$ where $|$ denotes bitwise OR. Proof: If $2^k$-bit is off for $x$ then $f(x,2^k)=x+2^k$ because $f(x,2^k)$ has all bits of $x$ and $2^k$ so $f(x,2^k)\ge x+2^k$ and by $f(x,2^k)\le x+2^k$ equality must hold. $f(x+2^k, 2^k)=f(x, f(2^k,2^k))=x+2^k$ Analogously $f(x,2^k)=x|2^k$ We will strong induct on $y$ to prove $f(x,y)=x|y$ for all $x,y$. The base case, $y=2^b$ has been resolved above. Suppose $2^b<y<2^{b+1}$, then $f(2^b, y-2^b)=y$ It follows $f(x,y)=f(x,f(2^b,y-2^b))=f(f(x,2^b),y-2^b)=f(x|2^b, y-2^b)=x|2^b|(y-2^b)=x|y$ completing the induction. The last two equalities follow from the inductive hypothesis as $2^b,y-2^b<y$ and are positive.

Denote by $|$ the binary OR operation. Use $a\subseteq b$ to mean $a|b=b$. Claim. The weird binomial coefficient condition is equivalent to $(a|b)\subseteq f(a,b)$. Proof. This is immediate from Lucas's Theorem. Corollary. If $a\&b=0$, then $f(a,b)=a+b$. Now by the surjectivity condition, we need $f(a,b)=2^n$ for some $a,b$ for any nonnegative integer $n$. But \[(a|b)\subseteq f(a,b)\rightarrow (a|b)=2^n\rightarrow a=b=2^n,\]so $f(2^n,2^n)=2^n$ for any nonnegative integer $n$. Claim. $f(2^n,a)=2^n|a$ for any nonnegative integer $n$ and positive integer $a$. Proof. We casework on $a\%2^{n+1}$. Case 1, $a\%2^{n+1}<2^n$. Then this is obvious by the corollary from earlier. Case 2, $a\%2^{n+1}\ge 2^n$. If $a=2^n$, we already have the result. Otherwise, by the previous case, we have \[a=(a-2^n)+2^n=f(2^n,a-2^n)=f(f(2^n,2^n),a-2^n)=f(2^n,f(2^n,a-2^n))=f(2^n,a).\] Now for any $f(a,b)$, simply decompose $b$ into its binary form by the corollary from earlier, then OR each component with $a$ since we are given associativity. This gives us $f(a,b)=\boxed{a|b}$, which works. QED.

BOX SIMULATOR I LOVE BOXTIMES OPERATOR. Replace $f$ with $\boxtimes$ since I was given the problem this way. Note that the second condition is equivalent to $a \boxtimes b$ having a $1$ in base $2$ whenever one of $a$ or $b$ has one. Claim: $a \boxtimes b = a \lor b$ works. Proof. Surjectivity follows as $a \boxtimes a = a$. Associativity follows as logical or is associative. This lies in bounds as $\max\{a, b\} \le a \lor b \le a + b$ follows inductively on digits. $\blacksquare$ Now suppose such a $\boxtimes$ operator exists. Claim: $a \boxtimes b = 2^n$ holds if and only if $a = b = 2^n$. Proof. If either $a$ or $b$ has digits that are larger or smaller in base $2$ other than at $2^n$, then the result doesn't hold. It must follow that $a$ and $b$ are both $2^n$. $\blacksquare$ Claim: $a \boxtimes b = a \lor b$ if $a \lor b = a + b$. Proof. It follows as $a + b \ge a \boxtimes b \ge a \lor b$ as desired. $\blacksquare$ Claim: $a \boxtimes b = a \lor b$. Proof. Decompose in binary $a = 2^{i_1} + 2^{i_2} + \dots + 2^{i_n}$ for $i_1 > i_2 > \dots > i_n$ and $b = 2^{j_1} + 2^{j_2} + \dots + 2^{j_n}$. As such, it follows that \[ a \boxtimes b = 2^{i_1} \boxtimes 2^{i_2} \boxtimes \dots \boxtimes 2^{i_n} \boxtimes 2^{j_1} \boxtimes \dots \boxtimes 2^{j_n} \]Then since $2^a \boxtimes 2^b = 2^b \boxtimes 2^a$ and $2^a \boxtimes 2^a$ we can remove any duplicate powers of $2$, then remerge into the desired result. $\blacksquare$

BOX SIMULATOR I LOVE BOXTIMES OPERATOR. Replace $f$ with $\boxtimes$ since I was given the problem this way. Also, I copied your first sentence. We claim that $f$ must be the $\emph{bitwise-or}$ operator, denoted $\vert$. This is clearly associative, and it is surjective because $a\vert a = a$. It is also at least both $a$ and $b$ and at most $a+b$. We will later show that it satisfies the second condition. By Lucas Theorem, we have that the binomial coefficient condition implies that $$(a\vert b)\vert a\boxtimes b = a\boxtimes b$$and we wish to prove that $a\vert b = a\boxtimes b$. Note that $a\boxtimes b = a\vert b$ satisfies the condition. First, note that if $a$ and $b$ have no overlapping bits, then $a\vert b = a+b$, implying that $a\boxtimes b = a\vert b = a+b$. Therefore, $$2^x\boxtimes 2^y = 2^x+2^y = 2^x\vert 2^y$$whenever $x\neq y$. Furthermore, we claim that $2^x\boxtimes 2^x = 2^x$. This is because $\boxtimes$ is surjective, and the binomial coefficient $\binom{2^n}{k}$ can only be odd when $k=0$ or $k=2^n$. This implies that $\boxtimes$ can only take the value $2^x$ when both $a$ and $b$ are $2^x$. Finally, $a$ can be written as the sum of distinct powers of $2$ in one way (binary representation), which we denote as $$2^{a_1} + 2^{a_2} + \dots 2^{a_i}$$and define an analogous sum for $b$ (using the variable $j$ instead of $i$). We can write, by associativity, $$a\boxtimes b = (2^{a_1} + 2^{a_2} + \dots 2^{a_i})\boxtimes (2^{b_1} + 2^{b_2} + \dots 2^{b_j}) = 2^{a_1}\vert 2^{a_2} \vert \dots \vert 2^{b_1}\vert 2^{b_2} \dots = a\vert b$$since the operation $\vert$ is associative.

Replace $f$ with $\boxtimes$ since I was given the problem this way. Let the binary OR function be denoted as $\vert$, which clearly satisfies the given conditions. We will prove that $a \boxtimes b = a \vert b$ using induction on $a,b \le 2^n$. The base case $n=0$ is true, as it is clear that $1 \boxtimes 1 = 1$. Suppose the inductive hypothesis is true up to $2^{k-1}$. For $n<2^k$, \[n \boxtimes 2^k = 2^k \boxtimes n = 2^k+n ,\] by Lucas' Theorem. Applying this for integers $a,b<2^{k-1}$, we get \begin{align*} (a+2^{k-1}) \boxtimes b &= (a \boxtimes 2^{k-1}) \boxtimes b \\ &= 2^{k-1} \boxtimes (a \boxtimes b) \\ &= 2^{k-1} \boxtimes (a \vert b) \\ &= 2^{k-1} + (a \vert b). \end{align*} Similarly, \begin{align*} (b+2^{k-1}) \boxtimes a &= (b \boxtimes 2^{k-1}) \boxtimes a \\ &= 2^{k-1} \boxtimes (a \boxtimes b) \\ &= 2^{k-1} \boxtimes (a \vert b) \\ &= 2^{k-1} + (a \vert b). \end{align*} Finally, \begin{align*} (a+2^{k-1}) \boxtimes (b+2^{k-1}) &= a \boxtimes 2^{k-1} \boxtimes 2^{k-1} \boxtimes b \\ &= (a \boxtimes 2^{k-1}) \boxtimes b \\ &= (a + 2^{k-1}) \boxtimes b \\ &= 2^{k-1} + (a \vert b), \end{align*} if and only if $2^{k-1} \boxtimes 2^{k-1} = 2^{k-1}$, which is true due to the surjectivity condition. $\square$.

We show that the answer is binary OR where all numbers are expressed in binary by induction. Suppose that the operation is binary OR for all $n<2^k.$ The base case $k=0$ is simple because $2^k \boxtimes 2^k=2^k$ due to surjectivity.Note that $2^k \boxtimes n=2^k+n$ by Lucas and this is true because the max is also $2^k+n.$ Let $a,b<2^k.$ Then \begin{align*} (a+2^k) \boxtimes b = 2^k\boxtimes a \boxtimes b&=2^k+a\boxtimes b \\ (a+2^k)\boxtimes (b+2^k) = 2^k\boxtimes 2^k \boxtimes a\boxtimes b&=2^k+a \boxtimes b. \end{align*}This completes the induction.$\blacksquare$

The only solution is the bitwise OR function, which works. Consider numbers in base $2$. Let the $i$th bit of a number be the $i$th digit from the right of a number in base $2$. Claim: If the $i$th bit of $a$ or $b$ is $1$, then the $i$th bit of $a \boxtimes b$ is $1$. Proof: FTSoC, assume there exits a bit of $a$ is $1$, but not of $a \boxtimes b$. Then take the right most such bit, say it's the $i$th bit. Then, since it's the right most bit, the $i$th bit in $a \boxtimes b - a$ must be a $1$. Thus, when we add $a \boxtimes b-a$ and $a$, we must carry the $i$th bit, which, by Kummer's theorem, means that $2$ divides $\binom{a \boxtimes b}{a}$, a contradiction. $\square$ A result of this claim is that, for any $a \neq b$, $2^a \boxtimes 2^b = 2^a+2^b$ because $2^a \boxtimes 2^b \le 2^a+2^b$. Claim: $2^n \boxtimes 2^n = 2^n$ for any integer $n \ge 0$ Proof: Subjectivity implies the existence of $a$ and $b$ such that \[a \boxtimes b = 2^n\]The above claim finishes since $a$ and $b$ can only be $2^n$ since they're positive. $\square$ To finish, take the binary representaions of $a$ and $b$ and consider $a \boxtimes b$. Since $2^a \boxtimes 2^b = 2^a+2^b = 2^b \boxtimes 2^a$, we can rearrange the $\boxtimes$ operations to have the box operation of the $i$th bit in $a$ to be applied to the $i$th bit of $b$. Then associativity means we can combine these two $i$th bits to be one $i$th bit. Thus $a \boxtimes b$ is just the $\boxtimes$ of all bits in either $a$ or $b$. This is equivlent to $\boxtimes$ being the OR operation as desired.

Very nice. We claim that $ a \boxtimes b$ is the bitwise OR of the the two numbers, which clearly works by Lucas. Claim 1: $2^k \boxtimes 2^k = 2^k$ $\textit{Proof:}$ By surjectivity there exists $x,y$ such that $x \boxtimes y = 2^k$ and therefore $x=y=2^k$ and so $2^k \boxtimes 2^k$ Claim 2: $2^k \boxtimes a$ is bitwise OR of $2^k$ and $a$. $\textit{Proof:}$ $2^k \boxtimes a = a \boxtimes 2^k = a+2^k$ for $a \leq 2^k$ by Lucas', and $(a+2^k) \boxtimes 2^k = a \boxtimes 2^k = a+2^k$, finishing the proof of the claim. Now we induct on $b$ to get that $a \boxtimes b = a \mid b$, let $2^{k-1}<b<2^k$ then $a \boxtimes b = a \boxtimes ((b-2^{k-1}) \boxtimes 2^{k-1}) = (a \boxtimes (b-2^{k-1})) \boxtimes 2^{k-1} = a \mid b$ as desired.

The answer is the binary or operation $a \vee b$, i.e. the $2^k$-place value of $a \vee b$ is $1$ if and only if the $2^k$-place value of $a$ is $1$ or the $2^k$-place value of $b$ is $1$. This clearly satisfies all the conditions; in particular it satisfies the third by Kummer's theorem as no carries are performed when subtracting $a$ or $b$ from $a \vee b$ in base two. We let $a_k$ denote the $2^k$-place value of $a$ and similar for $b_k$. Claim: $f(a, b)_k = 1$ if $a_k = 1$ or $b_k = 1$. Proof: By Kummer's theorem again; otherwise we have a carry in binary subtraction! $\blacksquare$ Claim: $f\left(2^k, 2^k\right) = 2^k$. Proof: Note that there exist $x$ and $y$ such that $f(x, y) = 2^k$ by surjectivity of $f$. But $x_k$ and $y_k$ are the only digits in $x$ and $y$ that can be $1$, so the result follows. $\blacksquare$ Note that $f(a, b) \geq \operatorname{max}(a, b)$ for all $a, b$. Now we perform a strong induction on $a$, the first entry of $f$. For the base case $a=1$, note that $f(b, 1) \leq b+1$ by the first condition. Now, if $b$ is even, then $f(a, b)_0 = 1$ by the claim, so we must have $f(b, 1) = b+1$; if $b$ is odd, then either $f(b, 1) = b$ or $f(b, 1) \geq b+2$. We must have $f(b, 1) = b$. For the inductive step, we have two cases: First Case: Suppose that $a$ is not a power of two. Then by partitioning the $d \geq 2$ nonzero digits in $a$, there exist two positive integers $x, y < a$ such that $a = x \vee y = f(x, y)$ by the inductive hypothesis. So now write \[f(a, b) = f(f(x, y), b) = f(x, f(y, b)) = x \vee y \vee b = a\vee b\]by the inductive hypothesis. Second Case: Suppose that $a=2^k$ is a power of two. Claim: Suppose $r_k = 0$ for some positive integer $r$. Then $f\left(2^k, r\right) = f\left(r, 2^k\right) = 2^k+r$. Proof: $f\left(r, 2^k\right) \leq 2^k+r$ by the first condition. On the other hand, looking at the digits of $f\left(r, 2^k\right)$ that must be $1$, we also have $f\left(r, 2^k\right) \geq 2^k+r$, and the result follows. $\blacksquare$ For the remaining values $f\left(2^k, b\right)$ where $b_k = 1$, let $b = 2^k + b'$; then $f(2^k, b') = b$ by the claim. It follows that \[f\left(2^k, b\right) = f\left(2^k, f\left(2^k, b'\right)\right) = f\left(f\left(2^k, 2^k\right), b'\right) = f\left(2^k, b'\right) = b\]by the second claim. This completes the induction. Remark: The surjectivity condition is only used once to show that $f\left(2^k, 2^k\right) = 2^k$. Forgetting Lucas's theorem made this problem more enjoyable.