Sets are a powerful construct used in many mathematical, logical, and computer science-related applications. They are relied on heavily within the fields of machine learning, linguistics, and computing theory. The basic concepts of set theory can be expressed using several formats of set notation.
Many symbols in set notation are ubiquitous among fields of logical design. For example, most equality operators have inverse inequality operators to mirror the logic expressed. Very few non-mathematicians have complete working knowledge of set notation. However, anyone studying within the fields of math or computer science can benefit from having a basic working knowledge of the most common symbols and meaning of set notation.
What’s in a Set, Anyway?
A set is simply a collection of unique elements. Sets are often formally notated as a comma-separated series of elements contained within two curly brackets. For example, {1, 2, 3, 4, 5} is a set because all the elements are unique but {1, 1, 2, 3, 4, 5} is not a set because element 1 appears two times.
When comparing sets, two are considered equal if and only if they contain the exact same elements. It is worth noting that sets can contain any type of element and are not restricted to numerical values only. In computer programming, for example, a set could contain Objects, lists, pointers, strings, or any other comparable language construct.
Set Notation
Sets are defined in several ways, some using the notational syntax of others, some more informal than others. Below are some of the most common types of set notation one is likely to run into out in the wild.
Verbose Notation
Verbose set notation, also called semantic notation, is the “wordy” way to define sets. This uses natural language to express the conditions, members, and range of a given set. For example, to define a set of all integers in the range 1-5, inclusive, one would use the following semantic notation:
Semantic Notation: Let S be the set whose members are the first 5 positive integers inclusive.
Roster Notation
Roster notation, also known as enumeration notation, defines a set by explicitly listing members between the curly brackets. This notation is regarded as the informal notation but commonly used. It can use an ellipsis to abbreviate large spans of membership in a more concise form.
- Complete Roster Membership:
{1, 2, 3, 4, 5} - Abbreviated Roster membership:
{1, 2, ..., 5}
Infinite Notation
Sets are often used to describe an infinitely large collection of members. In such cases, the ellipsis notation is used again to indicate directional infiniteness. For example, infiniteness in membership can be notated as follows:
- All positive integers:
{1, 2, 3, ...} - All integers:
{..., 1, 2, 3, ...}
Set-Builder Notation
Set-builder notation is similar to Roster and infinite notation. It can explicitly list membership, abbreviate membership using the ellipsis, and also represent unidirectional and bidirectional infiniteness. Set-builder notation is unique in that members are conditionally defined, commonly via means such as functions or predicates.
W = {n | w starts with the letter 'a', and length(w) < 5}
This set-builder notation represents the set V of all w (words) where the word starts with the letter a and is fewer than 5 characters in length. More simply; every word from the w section of the dictionary that’s fewer than 6 letters long.
Set-builder notation often utilizes a predicate to define members as well. This notation often makes more complex or cumbersome conditions expressible in more concise notation. For example, the set of all positive integers greater than 4 not in the set B can be expressed as such:
A = {x | x ∈ B ∧ x > 4 }
This expression establishes the set A from ll members of set B that are greater in value than 4. The | symbol expresses the condition “given that” and the ∧ symbol is the symbolic notation for and. There are many more set symbols that can be used here as in other forms of symbolic notation.
Membership Notation
It is often necessary to refer to the members of a set such that one can express the conditionality of their inclusion. For example, set inclusion can be notated using the set membership symbol ∈. There are several such notations each of which offer a specific benefit.
Set Membership
The set membership symbol ∈ denotes an element, or collection of elements, membership in a set. For example, to communicate the integers 1, 2, 3 being contained in the set {1, 2, 3, 4, 5} one would use the following notation:
Given A = {1, 2, 3}; A ∈ {1, 2, 3, 4, 5}
This notation can be used for sub-sets and single elements alike. For example, expressing the membership of the single integer 4 in the above set can be done as follows:
4 ∈ {1, 2, 3, 4, 5}
As with many equality comparators in the fields of math, statistics, and computer science, the set membership operator can also be negatively expressed using the ∉ symbol. For example, to communicate that 6 is not a member of the above set, one can use the following notation:
6 ∉ {1, 2, 3, 4, 5}
Likewise, this operator can be used to denote the lack of a subset membership as well:
Given B = {1, 2, 3}; B ∉ {1, 2, 3, 4, 5}
Special Sets
Among set theory, there are several special sets that are commonly expressed. While this article doesn’t focus on the whole of set theory, the notation of these sets is worth note was given their prevalence among common formulas used in applications such as machine learning.
Empty Set
The empty set defines a collection of exactly zero elements. It is represented as an empty set of curly brackets or a zero with a strike-through as such: {} or ∅. This set, sometimes referred to informally as the “null set,” is used for applications such as defining the combination of other sets in conditions resulting in values otherwise inexpressible in set notation.
For example {1, 2, 3} ∩ {3, 4, 5} = {} defines the empty set resulting from the intersection of two sets sharing exactly zero members.
Review
Set theory is foundational to many modern applications of mathematic ranging from machine learning, business intelligence, and statistical analysis. The field of set theory is large and dynamic but the notations used throughout are concise. Some syntax is more exotic than others but having a basic awareness of the notation by which common sets are expressed is a useful skill when studying modern computing applications. It was years before I bit the bullet and started familiarizing myself with such notations. All I can say is this: Damnit. I should have studied this years ago!
