Set Theory Basics

Membership: the one primitive idea

A set is an unordered collection of distinct objects called its elements. The only fundamental relationship is membership: an object either belongs to a set or it does not. We write x in A to say x is an element of A, and x not in A otherwise. There is nothing between belonging and not belonging, which is what makes set reasoning so clean.

Two features follow immediately from this definition. Order does not matter, so the set containing 1, 2, 3 is the same set as the one containing 3, 2, 1. And duplicates do not count, so listing an element twice adds nothing; a set either contains an object or it does not. Two sets are equal exactly when they have the same members, which is the standard way to prove set equality: show every element of one is an element of the other, and vice versa.

Subsets and the empty set

A set A is a subset of a set B when every element of A is also an element of B, written A is a subset of B. Note that a set is always a subset of itself, and that the definition allows A and B to be equal. When A is a subset of B but not equal to it, we call A a proper subset.

The empty set, the set with no elements at all, is a subset of every set. This surprises people, but it follows directly from the definition: to fail to be a subset, A would need an element that is not in B, and the empty set has no elements to serve as a counterexample. The empty set is unique and acts as a kind of zero for many set operations.

• A is a subset of B when every member of A is a member of B.
• Every set is a subset of itself.
• The empty set is a subset of every set.
• Prove A equals B by showing each is a subset of the other.

Union, intersection, and complement

The union of A and B, written A union B, is the set of elements that are in A, or in B, or in both. The intersection, A intersect B, is the set of elements in both A and B at once. If two sets have no elements in common their intersection is the empty set, and they are called disjoint. These two operations mirror the logical connectives or and and.

The complement of a set A, relative to a fixed universe of discourse, is the set of all elements in the universe that are not in A. Complement mirrors logical negation. Because these operations track the connectives so closely, the laws of logic carry straight over: for instance, De Morgan's laws say the complement of A union B equals the complement of A intersected with the complement of B, and similarly with union and intersection swapped.

Venn diagram intuition

A Venn diagram draws each set as a region, usually a circle, inside a rectangle representing the universe. Overlapping regions represent intersections, the combined shaded area represents a union, and the area outside a circle represents a complement. For two or three sets, these pictures make many set identities visually obvious before you prove them formally.

Use Venn diagrams to build intuition and to spot conjectures, but treat them as a guide rather than a proof. A picture with two or three circles cannot capture every configuration once you have four or more sets, and a formal proof works from the definitions of membership. The reliable pattern is to sketch the diagram to see why an identity should hold, then confirm it with an element-chasing argument.

Cardinality: measuring size

The cardinality of a set is the number of elements it contains, written with vertical bars, so the cardinality of A is A between bars. For finite sets this is just a count. A key result for combining sizes is the inclusion-exclusion principle: the cardinality of A union B equals the cardinality of A plus the cardinality of B minus the cardinality of A intersect B, because elements in the overlap would otherwise be counted twice.

Cardinality also extends to infinite sets, where it becomes genuinely surprising. Two sets have the same cardinality when their elements can be matched up one to one. Remarkably, the set of natural numbers and the set of even numbers have the same cardinality under this definition, even though one seems half the size of the other, and the real numbers form a strictly larger infinity than the naturals. These ideas sit at the foundation of what is and is not computable.

• Cardinality counts the elements of a set.
• Inclusion-exclusion: size of A union B equals size of A plus size of B minus size of the overlap.
• Infinite sets are compared by one-to-one matching.
• The naturals and the reals are different sizes of infinity.

Why sets matter in computer science

Set operations map directly onto everyday programming. Relational databases are built on unions, intersections, and differences of record sets; a SQL join is a set operation dressed in table syntax. Type systems reason about sets of possible values, and many algorithms are cleanest when framed as manipulations of sets of states, keys, or vertices.

Because of this, the notation you learn here is not academic decoration; it is the shared language you will use to specify data models, describe algorithm invariants, and reason about correctness. Getting comfortable with membership, subset, and the three core operations now makes the more advanced material on relations, functions, and graphs feel like natural extensions rather than new subjects.