Cardinality

Cardinality is a fundamental concept in set theory, a branch of mathematics concerned with the study of sets, or collections of objects. It is also essential in logic, where understanding the size of a set can influence the construction of logical arguments. The concept of cardinality allows mathematicians to compare the size of different sets, even when those sets are infinite. This exploration will discuss in depth what cardinality means, how it is used, and several examples to strengthen understanding of the concept.

What is cardinality?

Cardinality refers to the number of elements in a set. For finite sets, it is simply the count of distinct elements. For example, the set {a, b, c} has a cardinality of 3 because it has three elements. However, when dealing with infinite sets, the concept of cardinality becomes more abstract and interesting.

In formal terms, the cardinality of a set A is denoted by |A|. If there is a one-to-one correspondence (or bijection) between two sets, then they are said to have the same cardinality.

Cardinality of finite sets

Let's start with some simple examples of finite sets:

• The set A = {1, 2, 3} has cardinality |A| = 3 because it has three elements.
• The set B = {apple, banana} has cardinality |B| = 2 because it has two elements.

When comparing finite sets, you can say that two sets have the same cardinality if they have the same number of elements. For example, if C = {x, y, z}, then |C| = 3, and we see that the sets A and C have the same cardinality.

Visualization of finite set cardinality

Here, each ellipses {1, 2, 3} represents an element in the set, and we can see that there are three distinct ellipses, giving us a visual version of the cardinality of the set.

Infinite sets and their cardinality

Infinite sets are a different game altogether. Examples of infinite sets include:

• The set of natural numbers N = {1, 2, 3, ...}
• The set of even numbers E = {2, 4, 6, ...}
• The set of all integers Z = {..., -3, -2, -1, 0, 1, 2, 3, ...}

For infinite sets, cardinality is not determined by simply counting the elements. Instead, we use a method called one-to-one correspondence.

One-to-one correspondence

Two sets have the same cardinality if there is a bijection between them; that is, every element of one set is paired with exactly one element of the other set, and vice versa.

For example, consider the natural numbers N = {1, 2, 3, ...} and the even numbers E = {2, 4, 6, ...}. At first glance these sets seem to have different sizes because one is a subset of the other. However, we can create a one-to-one correspondence between them:

    f(n) = 2n

This function associates every natural number n with an even number f(n), and shows that these two infinite sets have the same cardinality.

Types of infinite cardinality

There are different kinds of infinity in set theory. The cardinality of the set of natural numbers is represented by the Hebrew letter aleph null, ℵ₀ (aleph-null), indicating that it is the smallest kind of infinity.

Visual representation of infinite sets

Here each row represents a natural number together with its corresponding even number, which shows that the cardinality of the set of natural numbers, despite their obvious difference, is the same as that of the set of even numbers.

Comparison of infinite sets

The concept of comparing the cardinalities of infinite sets led to some of the most profound discoveries in mathematics.

Consider the rational numbers, which are represented by the set Q. They form another paradox. How can we compare the cardinality of the rational numbers to that of the natural numbers?

Despite the density of rational numbers between any two integers, it can be shown that the set of rational numbers is countable and thus has the same cardinality as the set of natural numbers. The argument involves arranging the rational numbers in an array and walking diagonally through them.

Diagonal argument for rational numbers

First, imagine listing the rational numbers where the fractions ( a/b ) are arranged so that a and b both count upwards:

    1/1, 1/2, 1/3, ...
    2/1, 2/2, 2/3, ...
    3/1, 3/2, 3/3, ...

By traversing this array on a diagonal path, we can cover all rational numbers and map them to natural numbers. This approach proves that the cardinality of rational numbers is ℵ₀.

Uncountable sets

Some sets are more "massively" infinite than others. The classic example involves the set R of real numbers, which contains all possible decimal numbers. The real numbers are uncountable, meaning that their cardinality is strictly greater than that of the natural numbers.

Power sets and Cantor's theorem

A practical way to look at large infinities comes from Cantor's theorem, which states that the power set of any set (the set of all its subsets) always has a cardinality larger than the set itself. This discovery points to a whole hierarchy of infinities.

The role of cardinality in logic

Beyond set theory, cardinality plays a role in logic, particularly in areas involving model theory and computability. Understanding the size of models with particular properties can affect proofs and theorems related to logical systems.

Logical implications of cardinality

For example, consider the Löwenheim-Skolem theorem in logic, which states that if the model of a first-order theory is infinite, then it will all have models of cardinality at least as large as the language of the theory. This theorem underlies important results in understanding how the size of linguistic systems affects their model structures.

Summary

Cardinality is a concept that highlights the difference and equivalence of the size of both finite and infinite sets. Learning this concept leads to insights into the nature of mathematics and logic, as well as surprising and sweeping conclusions about the structure of mathematical theories and the reality they contain.

Comments