Sets, Functions and Relations: every key term you need (+ practice quiz)
25 flashcard terms for Discrete Mathematics Topic 3, written to match the course framework. Study them here, then drill them as interactive flashcards, or test yourself with the 15-question quiz — free, no account needed.
An unordered collection of distinct objects called elements. Repetition and order carry no information, so listing an element twice describes the same set as listing it once.
Set builder notation
A way of describing a set by a defining property rather than a list, written as the collection of all x in some domain such that a stated predicate holds for x.
Empty set
The unique set with no elements. It is a subset of every set, and it must be distinguished from a set whose single element happens to be the empty set.
Subset
A set A is a subset of B when every element of A is also an element of B. A proper subset additionally requires that B contains at least one element not in A.
Set equality
Two sets are equal exactly when each is a subset of the other. Proving double inclusion is the standard method for establishing an identity between described sets.
Power set
The set of all subsets of a given set, including the empty set and the set itself. A set with n elements has a power set of size two to the n.
Cardinality
The size of a set. For finite sets it is the number of elements, and for infinite sets it is compared using bijections, which separates countable from uncountable.
Union of sets
The set of elements lying in at least one of the given sets. It corresponds to logical disjunction under set builder notation, and it is commutative and associative.
Intersection of sets
The set of elements lying in every one of the given sets. Sets whose intersection is empty are called disjoint, and pairwise disjoint families are central to counting arguments.
Set difference
The set of elements in the first set that are not in the second. Unlike union and intersection it is not commutative, and it equals intersection with the complement.
Symmetric difference
The set of elements lying in exactly one of two sets, equal to the union minus the intersection. It is the set analogue of exclusive or.
Complement of a set
The set of all elements of the universal set that do not belong to the given set. The notion is meaningless until a universal set is specified.
Cartesian product
The set of all ordered pairs whose first entry comes from the first set and second entry from the second. Its size is the product of the two sizes, which grounds the product rule of counting.
Function
An assignment giving each element of a domain exactly one element of a codomain. Totality and single valuedness are both required, so a rule leaving some input unassigned is not a function.
Domain and codomain
The domain is the set of allowed inputs of a function and the codomain is the declared set of possible outputs. The codomain is part of the function's definition, not derived from it.
Range of a function
The set of outputs actually attained, always a subset of the codomain. A function is surjective exactly when its range equals its codomain.
Injective function
A one to one function, meaning distinct inputs always give distinct outputs. Equivalently, whenever two outputs are equal the inputs were equal.
Surjective function
An onto function, meaning every element of the codomain is the image of at least one element of the domain, so nothing in the codomain is missed.
Bijective function
A function that is both injective and surjective, pairing the domain and codomain perfectly. Only bijections have inverse functions, and they are the tool for comparing cardinalities.
Composition of functions
Applying one function to the output of another. Composition is associative but generally not commutative, and it preserves injectivity and surjectivity in predictable ways.
Binary relation
Any subset of the Cartesian product of two sets, which simply records which pairs are related. Functions are the special relations where each input appears in exactly one pair.
Reflexive, symmetric and transitive
The three properties of a relation on one set: every element relates to itself, relation reverses freely, and two linked steps compose into one direct link.
Equivalence relation
A relation that is reflexive, symmetric and transitive. Its equivalence classes partition the underlying set, and conversely every partition arises from exactly one such relation.
Partial order
A relation that is reflexive, antisymmetric and transitive, modelling comparisons such as divisibility or subset inclusion in which some pairs may simply be incomparable.
Countable set
A set that is finite or can be placed in bijection with the positive integers. The rationals are countable while the reals are not, as Cantor's diagonal argument shows.