Infinite version of the Set card game

14 Jun 2023

edit 2023/06/17: I elaborated a bit more in the conclusion about the open problem of finding a minimal $\kappa$.

The Set Game

I visited A Coruña last week for the Web Engines Hackfest and to participate to internal events with my fellow Igalians. One of our tradition being to play board games, my colleague Ioanna presented a card game called Set. To be honest I was not very good at it, but it made me think of a potential generalization for infinite sets that is worth a blog post…

Basically, we have a deck of $\lambda^\mu$ cards with $\mu = 4$ features (number of shapes, shape, shading and color), each of them taking $\lambda = 3$ possible values (e.g. red, green or purple for the color). Given $\kappa$ cards on the table, players must extract $\lambda$ cards forming what is called a Set, which is defined as follows: for each of the $\mu$ features, either the cards use the same value or they use pairwise distinct values.

Formally, this can be generalized for any cardinal $\lambda$ as follows:

• A card is a function from $\mu$ (the features) to $\lambda$ (the values).
• A set of cards $S$ is a Set iff for any feature $\alpha < \mu$, the mapping $\Phi_\alpha^S : S \rightarrow \lambda$

  that maps a card $c$ to the value $c(\alpha)$ is either constant or one-to-one.

Given a value $\kappa$ such that $\lambda \leq \kappa \leq \lambda^\mu$, can we always extract a Set when $\kappa$ cards are put on the table? Or said otherwise, is there a set of $\kappa$ cards from which we cannot extract any Set?

Trivial cases ($\lambda \leq 2$ or $\mu \leq 1$)

Given $\kappa \geq \lambda$ cards, we can always extract a Set $S$ in the following trivial cases:

• If $\mu = 0$ then the deck contains only one card $c = \emptyset$. If $\lambda \geq 2$ such a set of $\kappa$ cards does not exist. Otherwise we can just take $S = \emptyset$ or $S ={\{c\}}$: these are Sets since the definition is trivial for $\mu = 0$.
• If $\mu \geq 1$ and $\lambda = 0$ then the deck is empty. We take $S = \emptyset$ and for any $\alpha < \mu$, $\Phi_\alpha^\emptyset = \emptyset$ is both constant and one-to-one.
• If $\mu = 1$ and $\lambda \geq 1$, a card $c$ is fully determined by its value $c(0)$, so distinct cards give distinct values. So we can pick any $S$ of size $\lambda$: it is a Set since $\Phi_0$ is one-to-one.
• If $\lambda = 1$ then we can pick any singleton $S$: it is a Set since for any feature $\alpha < \mu$ the mapping $\Phi_\alpha^S$ is both constant and one-to-one.
• If $\lambda = 2$ then we can pick any pair of cards $S$: it is a Set since for any feature $\alpha < \mu$ the mapping $\Phi_\alpha^S$ is either constant or one-to-one (depending on whether the two cards display the same value or not).

👉🏼 For the rest of this blog post, I’ll assume $\mu \geq 2$ and $\lambda \geq 3$.

Not enough cards on the table ($\kappa \leq \mu$)

If $\mu \geq \kappa \geq \lambda \geq 3$ then we consider cards $c_\alpha$ for each $\alpha < \kappa$ defined for each $\beta < \mu$ as $c_\alpha{(\beta)} = \delta_{\alpha, \beta}$ (using Kronecker delta). If we extract a subset $S$ from these cards and $\alpha_1, \alpha_2, \alpha_3 < \kappa \leq \mu$ are indices for elements of $S$ then $\Phi_{\alpha_1}^S$ respectively evaluates to 1, 0 and 0 for $\alpha_1, \alpha_2, \alpha_3$ so $S$ is not a Set.

👉🏼 For the rest of this blog post, we’ll assume $\mu < \kappa$ and will even focus on the minimal case $\kappa = \lambda$.

Finite number of values ($\lambda < \aleph_0$)

Let’s consider a finite number of values $\lambda \geq 3$ and define the card $c_\alpha$ for each $\alpha < \lambda$ as follows: $c_\alpha(\beta) = \delta_{\alpha, 0}$ for $\beta=0$ (again Kronecker delta) and $c_\alpha(\beta) = \alpha$ for $0 < \beta < \mu$. Since $\mu \geq 2$, the latter case shows that $S = \{ c_\alpha : \alpha < \lambda \}$ contains exactly $\lambda$ cards. Since $\kappa = \lambda < \aleph_0$, the only way to extract a subset of size $\lambda$ would be to take all the cards. But they don’t form a Set since by construction ${\Phi_0{(c_0)}} = 1 \neq 0 = {\Phi_0{(c_1)}} = {\Phi_0{(c_2)}}$.

👉🏼 For the rest of the blog post, I’ll assume $\lambda$ is infinite.

Singular number of values ($\mi{cf}(\lambda) < \lambda$)

If $\lambda$ is a singular cardinal, then we consider a cofinal sequence ${\{ \alpha_{\gamma}, \gamma < \nu \}} \subseteq \lambda$ of length $\nu < \lambda$ and define the card $c_\alpha$ for $\alpha < \lambda$ as follows:

• For $\beta = 0$, we consider the smallest ordinal $\gamma < \nu \leq \lambda$ such that $\alpha < \alpha_\gamma$ and define $c_\alpha{(0)} = \gamma$.
• For any $1 \leq \beta < \mu$, ${c_\alpha{(\beta)}} = \alpha$.

Since $\mu \geq 2$, the latter case shows that these are $\lambda$ distinct cards. Consider $S \subseteq {\{c_\alpha, \alpha < \lambda \}}$. If $\Phi_0^S$ evaluates to a constant value $\gamma < \nu$ then $S = {\left(\Phi_0^S\right)}^{-1}(\{\gamma\})$ has size at most ${|\alpha_\gamma|} < \lambda$. If instead $\Phi_0^S$ is one-to-one then it takes at most $\nu$ distinct values so again ${|S|} \leq \nu < \lambda$. Hence $S$ is not a Set.

👉🏼 For the rest of the blog post, I’ll assume $\lambda$ is an infinite regular cardinal.

Finite number of features ($\mu < \aleph_0$)

In this section, we assume that the number of features $\mu$ is finite. Let’s consider $\lambda$ cards $c_\alpha$ and extract a Set $S$ by induction as follows:

• $S_0 = \{ c_\alpha : \alpha < \lambda \}$
• For any $\beta < \mu$, we construct $S_{\beta+1} \subseteq S_{\beta}$ of cardinality $\lambda$. We note that $\lambda$ is regular and $$S_\beta = {\bigcup_{\alpha \in \Phi_\beta^{S_\beta}{(S_\beta)}} {\left(\Phi_\beta^{S_\beta}\right)}^{-1}{(\{\alpha\})} }$$

  so there are only two possible cases:

  • If $\Phi_\beta^{S_\beta}{(S_\beta)}$ is of cardinality $\lambda$ then pick $\lambda$ elements from $S_\beta$ with pairwise distinct image by $\Phi_\beta^{S_\beta}$.
  • Otherwise, if there is $\alpha < \lambda$ such that ${\left(\Phi_\beta^{S_\beta}\right)}^{-1}{(\{\alpha\})}$ is of cardinality $\lambda$, then let it be our $S_{\beta+1}$.
• $S = S_{\mu}$

Then by construction, $S$ is of size $\lambda$ and for any $\beta < \mu$, $S \subseteq S_{\beta+1}$ which means that $\Phi_\beta^S = { {(\Phi_\beta^{S_\beta})}_{| S}}$ is either constant or one-to-one.

Incidentally, although I said I would focus on the case $\kappa = \lambda$ the result of this session shows that we can extract a Set if more than $\lambda$ cards are put on the table!

Summary and open questions

Above are the results I found from a preliminary investigation, which can be summarized as follows:

1. If $\lambda \leq 2$ or $\mu \leq 1$ then we can always find a Set from $\kappa \geq \lambda$ cards.
2. If $3 \leq \lambda \leq \mu$ then for any $\kappa$ such that $\lambda \leq \kappa \leq \mu$ there is a set of $\kappa$ cards from which we cannot extract any Set.
3. If $2 \leq \mu < \lambda < \aleph_0$ there is a set of $\lambda$ cards from which we cannot extract any Set.
4. If $2 \leq \mu$ and $\lambda$ is singular then there is a set of $\lambda$ cards from which we cannot extract any Set.
5. If $2 \leq \mu < \aleph_0 \leq {\mi{cf}(\lambda)} = \lambda$, then we can always find a Set from $\kappa \geq \lambda$ cards.

Note that for the standard game $3 = \lambda < \mu = 4$ the only of the results above that applies is (2). Indeed, having only three or four cards on the table is generally not enough to extract a Set!

So far, I was not able to find an answer for the case $\aleph_0 \leq \mu < {\mi{cf}(\lambda)} = \lambda \leq \kappa$. It looks like the inductive construction from the previous paragraph could work, but it’s not clear what guarantees that taking intersection at limit step would preserve size $\kappa$ (an idea would be to use closed unbounded $S_\beta$ instead but I didn’t find a satisfying proof). I also failed to build a counter-example set of $\lambda$ cards without any Set subset, despite several attempts.

More generally, an open problem is to determine the minimal number of cards $\kappa$ (with $\lambda \leq \kappa \leq \lambda^\mu$) to put on the table to ensure players can always extract a Set subset… or even if such a number actually exists! If it does, then in cases (2) (3) (4) we only know $\kappa > \lambda$. In cases (1) and (5) the minimum value $\kappa = \lambda$ works ; and when $\mu \geq 2$ and $\lambda \geq 3$ are finite, the maximum value $\kappa = \lambda^\mu$ means taking the full deck, which works too (e.g. it always contains the Set given by $\forall \alpha < \lambda, \forall \beta < \mu, c_\alpha(\beta) = \alpha$). Incidentally, note that the latter case is consistent with (2) and (3) since we have $\lambda^\mu > \mu, \lambda$. But in general for infinite parameters putting $\kappa = \lambda^\mu$ cards on the table does not mean putting the full deck, so it’s less obvious whether we can extract a Set…