Foobar Structures (Exam Drill)

A foobar structure is a custom exercise from the SMAI exam (exam-SS25-with-solutions.pdf, problem 4.1). The definition:

A structure $\langle S, \upsilon \rangle$ where $S$ is a set and $\upsilon : S \times S \to \mathbb{N}$ is a TOTAL FUNCTION is called a foobar iff:
1. $\upsilon(a, a) = 1$ for all $a \in S$ (the diagonal is 1).
2. For all $a, b \in S$: $a = b$ iff $\upsilon(a, b) = \upsilon(b, a)$ (symmetric values characterize equality).

This is a perfect example of the magma-hierarchy idea: we have ONE set, ONE binary operation (returning $\mathbb{N}$), and TWO axioms — plus the meta-requirement that $\upsilon$ is total.

Worked problem 4.1.1 — find $\upsilon$ for $S = \{1\}$:
The only input pair is $(1, 1)$, and we need $\upsilon(1, 1) = 1$. So $\upsilon(1, 1) := 1$.

Worked problem 4.1.2 — find $\upsilon$ for $S = \{1, 2, 3\}$:
Constraints:
- $\upsilon(a, a) = 1$ for all $a$ → so $\upsilon(1,1) = \upsilon(2,2) = \upsilon(3,3) = 1$.
- For $a \neq b$: $\upsilon(a, b) = \upsilon(b, a)$ (must hold; otherwise $a = b$ would not follow). So $\upsilon$ must be SYMMETRIC on distinct elements.
One simple choice: $\upsilon(a, b) = 2$ for all $a \neq b$. Check: if $\upsilon(a, b) = \upsilon(b, a)$ for $a \neq b$, both equal 2 — yes. And if $\upsilon(a, b) = \upsilon(b, a) = 1$, then $a = b$ — yes.

Problem 4.1.3 — product of foobars (counterexample):
If $\langle S, \upsilon_S \rangle$ and $\langle T, \upsilon_T \rangle$ are foobars, is $\langle S \times T, \upsilon_{S \times T} \rangle$ a foobar, where $\upsilon_{S \times T}((s_1, t_1), (s_2, t_2)) = \upsilon_S(s_1, s_2) + \upsilon_T(t_1, t_2)$?
Answer: NO — the diagonal condition fails: $\upsilon_{S \times T}((s, t), (s, t)) = \upsilon_S(s, s) + \upsilon_T(t, t) = 1 + 1 = 2 \neq 1$.