Sets, Relations and Functions: Complete Beginner's Guide

A set is a collection of distinct objects grouped together, such as the set of vowels in English or the set of all students in your class. Each object in the set is called an element, and we write a ∈ A to say "a is an element of set A". Sets are written with curly braces, like A = {1, 2, 3}, and the order of elements does not matter, so {1, 2, 3} and {3, 2, 1} are exactly the same set.

Sets matter because almost every field of computer science is built on them. Databases store tables that behave like sets of rows, programming languages provide set data types, and search engines treat documents and keywords as sets so they can match queries against content. Relations and functions grow directly out of set theory, and they are the mathematical backbone of databases, spreadsheets and every program that turns an input into an output.

Key Concepts

• Subset: A is a subset of B (written A ⊆ B) if every element of A is also in B. Example: {1, 2} ⊆ {1, 2, 3}.
• Power set: the set of all subsets of A, written P(A). If A has n elements, P(A) has 2^n elements, including the empty set and A itself.
• Union (A ∪ B): elements that are in A or in B. Intersection (A ∩ B): elements that are in both. Difference (A − B): elements in A but not in B.
• Cartesian product (A × B): the set of all ordered pairs (a, b) with a in A and b in B. If A has m elements and B has n elements, A × B has m × n pairs.
• Relation: any subset of A × B, a collection of connections between elements of two sets, such as "student X is enrolled in course Y".
• Function: a special relation where every element of A is paired with exactly one element of B. A is the domain, B is the codomain, and the values actually produced form the range.
• Injective (one-to-one): different inputs always give different outputs. Surjective (onto): every element of the codomain is hit by some input. Bijective: both at once, a perfect pairing.

Formulas

• Number of subsets: a finite set with n elements has exactly 2^n subsets. Example: n = 3 gives 8 subsets, from the empty set up to the full set.
• Inclusion–exclusion: |A ∪ B| = |A| + |B| − |A ∩ B|. The overlap is subtracted because it was counted twice. Valid for finite sets; for three sets it extends to |A ∪ B ∪ C| = |A| + |B| + |C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|.
• Functions from A to B: if A has m elements and B has n elements, there are n^m possible functions, because each of the m inputs has n independent choices.
• One-to-one functions: n × (n−1) × … × (n−m+1). This holds only when n ≥ m; if the codomain is smaller than the domain, zero one-to-one functions exist.

Worked Example

A survey of 100 students finds that 60 like cricket, 50 like football, and 25 like both. How many like at least one sport, and how many like neither?

1. Let C be the set of cricket fans and F the set of football fans. We know |C| = 60, |F| = 50 and |C ∩ F| = 25.
2. Apply inclusion–exclusion: |C ∪ F| = 60 + 50 − 25 = 85.
3. So 85 students like at least one of the two sports.
4. Students who like neither = total students − those who like at least one = 100 − 85 = 15.
5. Sanity check: the 25 students who like both were counted inside the 60 and again inside the 50, so subtracting 25 once removes exactly the double count, and 85 is sensibly less than 100.

Common Misconceptions

• "Sets care about order and repeats." They do not. {1, 2, 2, 3} is just {1, 2, 3}: duplicates collapse and order is irrelevant. Order matters only in ordered pairs and tuples, which is why the coordinates (2, 3) and (3, 2) are different points.
• "Every relation is a function." Wrong. A relation that pairs one input with two different outputs is not a function. A function allows each input exactly one output, though several inputs may share the same output.
• "The range and the codomain are the same thing." The codomain is the set of allowed outputs you declare up front; the range is the set of outputs that actually occur. For f(x) = x² with codomain "all real numbers", the range is only the non-negative reals.

Real-World Applications

• Databases: every table is a set of rows, and SQL joins are built on Cartesian products filtered down to the matching pairs.
• Search engines: a query's keyword set is intersected with each document's keyword set to decide which pages match.
• Access control: security systems model "which users may use which resources" as a relation between a set of users and a set of resources.
• Programming: hash sets, dictionaries and functions in code are direct, practical implementations of these mathematical ideas.

Sets give us a precise language for collections, relations describe connections between collections, and functions describe reliable input-to-output rules. With the counting formulas you can measure overlaps, possible mappings and subsets exactly — the same tools that databases and search engines rely on every single day.