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 .
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 cards with features (number of shapes, shape, shading and color), each of them taking possible values (e.g. red, green or purple for the color). Given cards on the table, players must extract cards forming what is called a Set, which is defined as follows: for each of the features, either the cards use the same value or they use pairwise distinct values.
Formally, this can be generalized for any cardinal as follows:
- A card is a function from (the features) to (the values).
- A set of cards is a Set iff for any feature , the mapping
that maps a card to the value is either constant or one-to-one.
Given a value such that , can we always extract a Set when cards are put on the table? Or said otherwise, is there a set of cards from which we cannot extract any Set?
Trivial cases ( or )
Given cards, we can always extract a Set in the following trivial cases:
- If then the deck contains only one card . If such a set of cards does not exist. Otherwise we can just take or : these are Sets since the definition is trivial for .
- If and then the deck is empty. We take and for any , is both constant and one-to-one.
- If and , a card is fully determined by its value , so distinct cards give distinct values. So we can pick any of size : it is a Set since is one-to-one.
- If then we can pick any singleton : it is a Set since for any feature the mapping is both constant and one-to-one.
- If then we can pick any pair of cards : it is a Set since for any feature the mapping 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 and .
Not enough cards on the table ()
If then we consider cards for each defined for each as (using Kronecker delta). If we extract a subset from these cards and are indices for elements of then respectively evaluates to 1, 0 and 0 for so is not a Set.
👉🏼 For the rest of this blog post, we’ll assume and will even focus on the minimal case .
Finite number of values ()
Let’s consider a finite number of values and define the card for each as follows: for (again Kronecker delta) and for . Since , the latter case shows that contains exactly cards. Since , the only way to extract a subset of size would be to take all the cards. But they don’t form a Set since by construction .
👉🏼 For the rest of the blog post, I’ll assume is infinite.
Singular number of values ()
If is a singular cardinal, then we consider a cofinal sequence of length and define the card for as follows:
- For , we consider the smallest ordinal such that and define .
- For any , .
Since , the latter case shows that these are distinct cards. Consider . If evaluates to a constant value then has size at most . If instead is one-to-one then it takes at most distinct values so again . Hence is not a Set.
👉🏼 For the rest of the blog post, I’ll assume is an infinite regular cardinal.
Finite number of features ()
In this section, we assume that the number of features is finite. Let’s consider cards and extract a Set by induction as follows:
- For any , we construct of cardinality . We note that is regular and
so there are only two possible cases:
- If is of cardinality then pick elements from with pairwise distinct image by .
- Otherwise, if there is such that is of cardinality , then let it be our .
Then by construction, is of size and for any , which means that is either constant or one-to-one.
Incidentally, although I said I would focus on the case the result of this session shows that we can extract a Set if more than 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 or then we can always find a Set from cards.
- If then for any such that there is a set of cards from which we cannot extract any Set.
- If there is a set of cards from which we cannot extract any Set.
- If and is singular then there is a set of cards from which we cannot extract any Set.
- If , then we can always find a Set from cards.
Note that for the standard game 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 . 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 (an idea would be to use closed unbounded instead but I didn’t find a satisfying proof). I also failed to build a counter-example set of cards without any Set subset, despite several attempts.
More generally, an open problem is to determine the minimal number of cards (with ) 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 . In cases (1) and (5) the minimum value works ; and when and are finite, the maximum value means taking the full deck, which works too (e.g. it always contains the Set given by ). Incidentally, note that the latter case is consistent with (2) and (3) since we have . But in general for infinite parameters putting cards on the table does not mean putting the full deck, so it’s less obvious whether we can extract a Set…