Discrete Mathematics: Cardinality and Equipotency

These flashcards cover core vocabulary and definitions related to cardinality and equipotency in discrete mathematics.

Equipotency

Two sets A and B are said to be equipotent if there exists a bijective function f: A → B, indicating they have the same cardinality.

Cardinality

A measure of the 'number of elements' in a set; formally defined through equipotency and bijections.

Finite Set

A set that is not equipotent to any of its proper subsets, implying it can be counted to a final number.

Denumerable Set

An infinite set that can be put into one-to-one correspondence with the natural numbers; also known as countably infinite.

Uncountable Set

An infinite set that cannot be placed in one-to-one correspondence with the natural numbers; examples include the set of real numbers.

Cantor-Schröder-Bernstein Theorem

If there exist injections (one-to-one functions) from set A to set B and from set B to set A, then A and B are equipotent.

Bijection

A function that is both injective (one-to-one) and surjective (onto), establishing a perfect pairing between two sets.

Equivalence Relation

A relation that is reflexive, symmetric, and transitive; equipotency acts as an equivalence relation on the class of all sets.

Injective Function

A function f is injective if it maps distinct elements of its domain to distinct elements in its codomain.

Surjective Function

A function f is surjective if every element in the codomain has a pre-image in the domain.

Galileo's Paradox

The surprising conclusion that the set of natural numbers is equipotent to the set of even natural numbers, despite the latter being a proper subset.

Dedekind-Infinite Set

A set that is equipotent to at least one of its proper subsets, making it infinite in the sense defined by Richard Dedekind.

Mapping

The process of associating elements of one set with elements of another set via a function.

Nominal Size

The formal size of sets in terms of cardinality rather than numerical counting.

Diagonal Argument

A proof technique used by Cantor to demonstrate that the set of real numbers is uncountable by constructing a number that cannot be in any purported enumeration.

Pigeonhole Principle

A principle that asserts if n items are put into m containers, with n > m, then at least one container must contain more than one item.

Properties of Equipotency

Conditions under which the concept of equipotency behaves structurally like equality, supporting classification of sets by their size.

Cardinality of Finite Sets

The unique integer n such that a finite set E is equipotent to the set of the first n natural numbers.