# What is the term for this set

I have a set of related data/objects for which, when undergoing some algorithm, there should be only one valid match. Is there a unique term for this type of set?

A common practical use case would be a list displayed for user selection, or a list of keys that should have a single corresponding entry in a database table.

To illustrate this, here are a few examples:

• [True, False] (boolean)
• [Forward, Neutral, Reverse] (state machine status)
• [Rare, Medium, Well] (user preference)
• [Credit, Debit] (reference type)

In each of these cases, only one element in the set will be contextually valid, where the context may be a database record, an instance of an object in memory, or a question on a survey.

Examples of sets that wouldn't meet this criteria:

• [Garage, Kitchen, Bedroom, Bathroom] (rooms in a home)
• [Email, Phone, Text] (method of communication)
• [All Countries in Europe] (places I visited)

In these cases, the set is used as a bucket from which a selection may be made - but the selection is not necessarily expected to be a single item in the set.

• What do you mean by "only one valid match"? – David Richerby Jul 28 '14 at 18:34
• @DavidRicherby - I mean that the algorithm expected to be used in context (e.g. what the user selected, what the database contains) as related to this set will always yield only one result. So within an expected context, the objects in the set are mutually exclusive. – PinnyM Jul 28 '14 at 18:36
• This question contains all kinds of vagueness. From what I can gather, I think you should read about unique key or primary key in the context of database. I think that might be the vocabulary you're missing. – Apiwat Chantawibul Jul 28 '14 at 19:48
• @Billiska - The question is intentionally generic because it's not limited to a database context. As stated, the algorithm may simply involve user input, or some other context. Unique database keys are a type of implementation that will enforce this functionality - I am looking for a term that describes the set of data used in such an implementation. – PinnyM Jul 28 '14 at 20:02
• @PinnyM Generic questions are sometimes useful, sometimes not. There often is field-/domain-specific terminology which may be "hidden" by abstraction. – Raphael Jul 29 '14 at 14:49

None of your examples holds up: each has queries that allow multiple answers, and each has queries that allow only singleton answers.

So you are really after a property of queries. On the most abstract level, given a set $S$ the term you are looking for is function:

$\qquad f : Q \to S \\ \qquad f(q) = s \text{ s.t. } q(s) = 1$

where $Q$ is the set of queries (predicates), i.e. $Q \subseteq S \to \{0,1\}$. Note how $f$ is a (well-defined) function if and only if all $q \in Q$ have a support (set of values on which $q$ is $1$) of size $1$.

If queries end up being true for (i.e. returning) multiple values, we call $f$ a relation. Or, alternatively, a function that maps queries to (possibly empty) sequences of results, i.e.

$\qquad f : Q \to S^*$.

• Thanks - this is very close, but I am trying to determine if there is a specific name for a set that satisfies such a function. From the way your are explaining it, I have this backward. But can one turn this around and say that for the specific query with a support of size 1, we can define a set as S - and describe that set with some unique term? Or would you say that we simply do not consider this set to be a special case, but rather with the way I intend to use it (and this intent would be encapsulated in the function you described). – PinnyM Jul 29 '14 at 0:06
• @PinnyM Yes, I don't think the sets are in any way special. That does neither mean that nobody invented notation/words for this nor that you can not. For instance, "We call $S$ $Q$-unique if and only if $f_Q$ is a function/mapping." Definitely possible, if it helps you to talk/write about things. – Raphael Jul 29 '14 at 6:16
• @GuyCoder Nope, sorry. I made it up on the spot. (It's not very well thought out, too.) – Raphael Jul 29 '14 at 18:44
• @GuyCoder Sorry, I thought it was clear that I invented it. Duly noted. As for the relevance of the question, I don't get the issue either. But apparently I could help PinnyM anyway, so what? ;) – Raphael Jul 29 '14 at 20:03
• @GuyCoder the question would be relevant if you needed to differentiate between a collection used for radio buttons, and a collection used for checkboxes. The case that I was dealing with is a parallel of that, but from a business logic perspective, and the code logically branches based on this distinction. – PinnyM Jul 29 '14 at 23:58

If I'm understanding you correctly, what you're describing loosely corresponds to disjoint sums, which you see a lot in type theory and functional programming.

For example, in Haskell you could do something like:

data Room = Garage | Kitchen | Bedroom | Bathroom


We call Garage, Kitchen etc. "constructors" for the type Room. Note that constructors can take arguments, for example you could have

data Room = Garage | Kitchen | Bedroom | Bathroom | Suite (Int, Int)


if you wanted to store the floor and room number for suites.

When you access a value of type Room, you need to pattern match it against its constructors, like this:

cleaningInstructions :: Room -> String
cleaningInstructions Garage = "It's messy, leave it alone"
cleaningInstructions Suite (roomNum, floorNum) = "Clean well for our guests"
...


and so on.

On the theory side, disjoint sums are the category-theoretic dual to Products (i.e. tuples). A product is where you have a thing of type 1, AND a thing of type 2, etc. They correspond well to the AND operation. Disjoint sums correspond to XOR: you have type 1 or type 2, but never both.