# Infinite version of the Set card game

*edit 2023/06/17: I elaborated a bit more in the conclusion about the open problem of finding a minimal $\backslash 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 $\backslash lambda^\backslash mu$ cards with $\backslash mu\; =\; 4$ features (number of shapes, shape, shading and color), each of them taking $\backslash lambda\; =\; 3$ possible values (e.g. red, green or purple for the color). Given $\backslash kappa$ cards on the table, players must extract $\backslash lambda$ cards forming what is called a *Set*, which is defined as follows: for each of the $\backslash mu$ features, either the cards use the same value or they use pairwise distinct values.

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

- A card is a function from $\backslash mu$ (the features) to $\backslash lambda$ (the values).
- A set of cards $S$ is a
*Set*iff for any feature $\backslash alpha\; <\; \backslash mu$, the mapping $\backslash Phi\_\backslash alpha^S\; :\; S\; \backslash rightarrow\; \backslash lambda$that maps a card $c$ to the value $c(\backslash alpha)$ is either constant or one-to-one.

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

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

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

- If $\backslash mu\; =\; 0$ then the deck contains only one card $c\; =\; \backslash emptyset$. If $\backslash lambda\; \backslash geq\; 2$ such a set of $\backslash kappa$ cards does not exist. Otherwise we can just take $S\; =\; \backslash emptyset$ or $S\; =\{\backslash \{c\backslash \}\}$: these are
*Sets*since the definition is trivial for $\backslash mu\; =\; 0$. - If $\backslash mu\; \backslash geq\; 1$ and $\backslash lambda\; =\; 0$ then the deck is empty. We take $S\; =\; \backslash emptyset$ and for any $\backslash alpha\; <\; \backslash mu$, $\backslash Phi\_\backslash alpha^\backslash emptyset\; =\; \backslash emptyset$ is both constant and one-to-one.
- If $\backslash mu\; =\; 1$ and $\backslash lambda\; \backslash 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 $\backslash lambda$: it is a
*Set*since $\backslash Phi\_0$ is one-to-one. - If $\backslash lambda\; =\; 1$ then we can pick any singleton $S$: it is a
*Set*since for any feature $\backslash alpha\; <\; \backslash mu$ the mapping $\backslash Phi\_\backslash alpha^S$ is both constant and one-to-one. - If $\backslash lambda\; =\; 2$ then we can pick any pair of cards $S$: it is a
*Set*since for any feature $\backslash alpha\; <\; \backslash mu$ the mapping $\backslash Phi\_\backslash 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 $\backslash mu\; \backslash geq\; 2$ and $\backslash lambda\; \backslash geq\; 3$.

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

If $\backslash mu\; \backslash geq\; \backslash kappa\; \backslash geq\; \backslash lambda\; \backslash geq\; 3$ then we consider cards $c\_\backslash alpha$ for each $\backslash alpha\; <\; \backslash kappa$ defined for each $\backslash beta\; <\; \backslash mu$ as $c\_\backslash alpha\{(\backslash beta)\}\; =\; \backslash delta\_\{\backslash alpha,\; \backslash beta\}$ (using Kronecker delta). If we extract a subset $S$ from these cards and $\backslash alpha\_1,\; \backslash alpha\_2,\; \backslash alpha\_3\; <\; \backslash kappa\; \backslash leq\; \backslash mu$ are indices for elements of $S$ then $\backslash Phi\_\{\backslash alpha\_1\}^S$ respectively evaluates to 1, 0 and 0 for $\backslash alpha\_1,\; \backslash alpha\_2,\; \backslash alpha\_3$ so $S$ is not a *Set*.

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

## Finite number of values ($\backslash lambda\; <\; \backslash aleph\_0$)

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

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

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

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

- For $\backslash beta\; =\; 0$, we consider the smallest ordinal $\backslash gamma\; <\; \backslash nu\; \backslash leq\; \backslash lambda$ such that $\backslash alpha\; <\; \backslash alpha\_\backslash gamma$ and define $c\_\backslash alpha\{(0)\}\; =\; \backslash gamma$.
- For any $1\; \backslash leq\; \backslash beta\; <\; \backslash mu$, $\{c\_\backslash alpha\{(\backslash beta)\}\}\; =\; \backslash alpha$.

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

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

## Finite number of features ($\backslash mu\; <\; \backslash aleph\_0$)

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

- $S\_0\; =\; \backslash \{\; c\_\backslash alpha\; :\; \backslash alpha\; <\; \backslash lambda\; \backslash \}$
- For any $\backslash beta\; <\; \backslash mu$, we construct $S\_\{\backslash beta+1\}\; \backslash subseteq\; S\_\{\backslash beta\}$ of cardinality $\backslash lambda$. We note that $\backslash lambda$ is regular and
$$S\_\backslash beta\; =\; \{\backslash bigcup\_\{\backslash alpha\; \backslash in\; \backslash Phi\_\backslash beta^\{S\_\backslash beta\}\{(S\_\backslash beta)\}\}\; \{\backslash left(\backslash Phi\_\backslash beta^\{S\_\backslash beta\}\backslash right)\}^\{-1\}\{(\backslash \{\backslash alpha\backslash \})\}\; \}$$
so there are only two possible cases:

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

- $S\; =\; S\_\{\backslash mu\}$

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

Incidentally, although I said I would focus on the case $\backslash kappa\; =\; \backslash lambda$ the result of this session shows that we can extract a *Set* if more than $\backslash 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:

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

Note that for the standard game $3\; =\; \backslash lambda\; <\; \backslash 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 $\backslash aleph\_0\; \backslash leq\; \backslash mu\; <\; \{\backslash mi\{cf\}(\backslash lambda)\}\; =\; \backslash lambda\; \backslash leq\; \backslash 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 $\backslash kappa$ (an idea would be to use closed unbounded $S\_\backslash beta$ instead but I didn’t find a satisfying proof). I also failed to build a counter-example set of $\backslash lambda$ cards without any *Set* subset, despite several attempts.

More generally, an open problem is to determine the minimal number of cards $\backslash kappa$ (with $\backslash lambda\; \backslash leq\; \backslash kappa\; \backslash leq\; \backslash lambda^\backslash 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 $\backslash kappa\; >\; \backslash lambda$. In cases (1) and (5) the minimum value $\backslash kappa\; =\; \backslash lambda$ works ; and when $\backslash mu\; \backslash geq\; 2$ and $\backslash lambda\; \backslash geq\; 3$ are finite, the maximum value $\backslash kappa\; =\; \backslash lambda^\backslash mu$ means taking the full deck, which works too (e.g. it always contains the *Set* given by $\backslash forall\; \backslash alpha\; <\; \backslash lambda,\; \backslash forall\; \backslash beta\; <\; \backslash mu,\; c\_\backslash alpha(\backslash beta)\; =\; \backslash alpha$). Incidentally, note that the latter case is consistent with (2) and (3) since we have $\backslash lambda^\backslash mu\; >\; \backslash mu,\; \backslash lambda$. But in general for infinite parameters putting $\backslash kappa\; =\; \backslash lambda^\backslash mu$ cards on the table does not mean putting the full deck, so it’s less obvious whether we can extract a *Set*…