Discover published sets by community

A binary relation that is reflexive, antisymmetric, and transitive. Example: The subset relation '⊆' among sets.

A method of mathematical proof that establishes the truth of an infinite sequence of cases by proving a base case and an inductive step. Example: Proving that $\sum_{i=1}^n i = \frac{n(n+1)}{2}$ for all positive integers n by induction.

A natural number greater than 1 that has no positive divisors other than 1 and itself. Example: 7 is a prime number because it can only be divided evenly by 1 and 7.

A method where the solution to a problem depends on solutions to smaller instances of the same problem. Example: The Fibonacci sequence defined by $F_n = F_{n-1} + F_{n-2}$, with base cases $F_1 = 1$ and $F_0 = 0$.

An extension of propositional logic that deals with predicates and quantifiers. Example: 'For all x, if x is a human then x is mortal'.

A set of ordered pairs of elements. Example: The '$<$' (less than) relation on natural numbers, such as (2, 3) where 2 is less than 3.

A collection of objects called vectors, where two operations (vector addition and scalar multiplication) are defined and satisfy eight axioms. Example: The set of all 2-tuples of real numbers forms a vector space under usual addition and scalar multiplication.

An algorithm to determine the greatest common divisor (GCD) of two integers. Example: The GCD of 270 and 192 can be found using Euclid's Algorithm.

A branch of logic that deals with propositions which can be true or false. Example: The statement 'It is raining' is a proposition that can be true or false.

An optimization problem in which an optimal solution is selected from a finite set of objects. Example: Finding the shortest possible route that visits each city exactly once in the Traveling Salesman Problem.

A well-defined series of steps for performing a computation or solving a problem. Example: The Euclidean algorithm for finding the greatest common divisor of two integers.

A set equipped with two operations that generalize the operations of addition and multiplication. Example: The set of integers, Z, forms a ring under addition and multiplication.

An algebraic structure consisting of a set equipped with two operations for addition and multiplication, where every nonzero element has a multiplicative inverse. Example: The set of rational numbers forms a field.

A property of whole numbers where one number is divisible by another if there is no remainder left when divided. Example: 24 is divisible by 6 because $24 \div 6 = 4$ with no remainder.

A collection of points, called vertices, connected by lines, called edges. Example: A friendship network where vertices represent people and edges represent friendships.

A selection of objects without regard to the order in which they are selected. Example: The combinations of 2 elements from the set {1, 2, 3} are {1, 2}, {1, 3}, and {2, 3}.

A measure of the amount of time and/or space required by an algorithm as a function of the size of the input. Example: The sorting algorithm quicksort has average-case time complexity O(n log n).

A set equipped with an operation that combines any two elements to form a third element and that satisfies four conditions: closure, associativity, identity, and inverses. Example: The integers with addition form a group.

The measure of the likelihood that an event will occur, expressed as a number between 0 and 1. Example: The probability of rolling a three on a six-sided die is $\frac{1}{6}$.

A binary relation that is reflexive, symmetric, and transitive. Example: The equality relation '=' on the set of real numbers.

An algebraic structure where any two elements have a unique supremum (join) and an infimum (meet). Example: The set of all subsets of a given set forms a lattice under the operations of union and intersection.

A connected graph with no cycles. Example: A family tree is a representation of genealogical data structured as a tree.

The principle that if n items are put into m containers, with n > m, then at least one container must contain more than one item. Example: If 13 pigeons are put into 12 pigeonholes, at least one pigeonhole must contain at least two pigeons.

A system of arithmetic for integers, where numbers wrap around upon reaching a certain value called the modulus. Example: The result of 8 + 5 under modulo 10 arithmetic is 3.

The set of all ordered pairs obtained by combining each element of one set with each element of another set. Example: The Cartesian product of sets A = {1,2} and B = {3,4} is AxB = {(1,3),(1,4),(2,3),(2,4)}.

A collection of distinct objects considered as a whole. Example: The set of natural numbers, N, which includes {1, 2, 3, ...}.

An arrangement of objects in a specific order. Example: The permutations of {1, 2, 3} are {(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)}.

A rectangular array of numbers or expressions arranged in rows and columns that can represent linear transformations or coefficients of a system of linear equations. Example: $\begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}$ is a 2x2 matrix.

A one-to-one correspondence between the vertex sets of two graphs that preserves the edge structure. Example: Two graphs that can be drawn in a way that makes them look identical are isomorphic.

A theorem that gives a unique solution to simultaneous linear congruences with pairwise coprime moduli. Example: Finding an integer x such that $x \equiv 2 \pmod{3}$ and $x \equiv 3 \pmod{5}$ can be solved using the Chinese Remainder Theorem.

A path in a graph which visits each vertex exactly once. Example: A Hamiltonian path in a graph representing cities might represent an efficient tour of a salesman visiting each city.

A mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity, often used to classify algorithms according to how their run time or space requirements grow as the input size grows. Example: The time complexity of bubble sort is O(n^2).

A relation from a set of inputs to a set of possible outputs where each input is related to exactly one output. Example: $f(x) = x^2$ maps from real numbers to non-negative real numbers.

A mathematical structure that captures the essentials of logic operations and binary variables. Example: The AND, OR, and NOT operations on true/false values constitute a Boolean algebra.

The study of securing communication in the presence of adversaries. Example: Using RSA encryption to securely transmit messages over the internet.