A brief introduction to the infinite

academics infinite mathematics
By Darko

Set theory is the branch of mathematics that studies the infinite. The discipline was founded by  Georg Cantor in the late 1800s. Cantor is responsible for many of the notions we discuss here. A set, according to Cantor, is a collection of definite, distinguishable objects conceived as a  whole. A set consists of its elements. There is exactly one set with no elements and it is called the empty set. We refer to it thusly: ∅. We can define a set by either listing its elements or  uniquely describing them as a totality.  

The first important set we look at is N, the set of natural numbers.

It is often defined implicitly  via the following hint, so to speak: 

Screen Shot 2023-08-16 at 12.55.52 PM

It is just a hint because it assumes that we somehow understand that these numbers increase  by one and go on forever. We can specify this set with a bit more precision. 

It can also be described more constructively as follows. Starting with a set N_0 = {0}, and for the largest element k ∈ N, let Nn+1 = Nn ∪ {k + 1}.

Finally, let the set:

Screen Shot 2023-08-16 at 1.06.02 PM

So N1 = {0,1}, N2 = {0,1,2}, etc.

All of the sets N0,...,Nn are finite. Their union, the set N, is infinite.

In other words, we get our first infinite set by collecting all of the natural numbers into a single set. Another way to look at it is that N contains all possible sizes of finite sets. The notion of  size is a relatively obvious one for finite sets. The set S = {A, B, C, D} has the size 4. In set theory we call this size cardinality and we say that cardinality of S is 4 or || S || = 4. Cardinality of the empty set is 0. We will call the cardinality of the set N as follows:

Screen Shot 2023-08-16 at 1.11.32 PMA ⊂ B is read A is a subset of B. A ⊂ B if all elements of A are also elements of B.

Here are some interesting subsets of N: 

P = the set of all prime numbers 

O = the set of all odd numbers 

E = the set of all even numbers 

Z = the set of all integers {...,-3,-2,-1,0,1,2,3,...}

Here are two important supersets of N (i.e., N ⊂ Q ⊂ R): 

Q = the set of rational numbers (fractions of the form p/q where p is an integer and q is a  strictly positive integer) 

R = the set of real numbers. This set strictly extends Q.34 

It is clear that P ⊂ O ⊂ N ⊂ Z ⊂ Q ⊂ R.

Two sets have the same Cardinality if they contain the same number of elements.

For the finite  sets we establish this equivalence by  

  1. well-ordering the set A. We choose the first, second, last element,
  2. well-ordering the set B in the same way.
  3. If one can order two sets using the same finite ordinal n, we say that the sets are of the || A || = || B || = n.

 

If two finite sets are equivalent in this sense, then we can pair their elements like this: 

  • The first element of A with the first element of B,
  • The second element of A with the second element of B,
  • ...The last element of A with the last element of B.

This pairing enables us to generalize the notion of set size to infinite sets. Two sets A and B have the same cardinality if there is such a pairing of their respective elements. Each a ∈ A appears in exactly one such pair in the pairing. The same holds for b ∈ B.

If no such pairing exists, the sets are said to have different cardinalities.

If A is a subset of B but no such pairing exists, then B is said to be strictly larger than A, or || B || > || A ||.

Lemma 0.0.1.

Given a set A of finite cardinality n and an infinite set B, the cardinality of B is  strictly larger. 

Lemma 0.0.2.

|| O || = || E ||. 

In words, the set O of odd numbers is equinumerous to the set of even numbers E. The pairing is provided by the following map:

Screen Shot 2023-08-16 at 1.25.12 PM

First note that ∃e ∈ E, o + 1 = e. It is easy to see that the map satisfies the uniqueness  requirements. This of course stands to reason; both sets are about half of infinity. It makes sense that they are about equal. Right?

The pairing looks like this, to be super obvious: (1, 2), (3, 4), (5,6), and so on.  

Lemma 0.0.3 (Or surprise 1).

The sets N and E have the same cardinality. There are exactly as many evens as there are  natural numbers. Think about this for a second. No wonder it was said that Cantor’s was the work of the devil. To prove the result, we define a map F satisfying ∀n ∈ N, F(n) = 2n.

To rigorously prove the lemma, we would need to demonstrate that the function F satisfies:

Screen Shot 2023-08-16 at 1.49.13 PM

The intuition that we developed on finite quantities is starting to betray us here. We want to say  that the set of odd numbers is half as large as the set of all numbers, but the mapping proves  otherwise. It is advisable while hitchhiking in the infinite land, to take one’s intuitions with a  grain of salt.

Lemma 0.0.4.

||Z || = ||N ||

The sets Z of all integers and N of positive integers alone have the same cardinality. Map the negative numbers to odds, positive to evens as above. We are starting to get a sense that in the infinite arithmetic, infinity x 2 is not much different from the infinity x (1/2). 

Lemma 0.0.4.

||O|| = ||E || = ||P|| = ||N || = ||Z ||

Of course, we would need to prove that there are infinitely many primes. At this point one may  be tempted to give up on the notion of the infinite. As a reminder of the centrality of the infinite to mathematics, we briefly remind ourselves of the Euclidean proof of such result.  

One of the earliest results that convinced mathematicians that they may end up needing infinity  of some sort or another, was the proof that there are infinitely many primes. The proof  proceeded by contradiction asserting that there were no more than some finite number of primes and {p1, p2, …, pn} was the complete list.  The proof proceeds to concoct a number P  called the Euclidean number that is defined as 1 + (p1 × . . . × pn) n. More formally, it looks like this:

Screen Shot 2023-08-16 at 1.58.58 PM

The first step into the abyss: ||Q|| = ||N||

The rational numbers and the reals seem very similar, at least on the surface. There seem to be  a lot of them, a whole bunch between any two rational numbers. Primes on the other hand seem to get rather rare as the numbers grow bigger. Because equivalence relationships are  transitive, if ||A|| = ||B|| and ||B||=||C||, then it follows that ||A||=||C||. Thus, if it turned out that  rational numbers are equinumerous with naturals, and primes with naturals, stunningly the rational numbers would be the same in number as the primes. The primes make up just above 0% of all natural numbers and natural numbers are essentially invisible among the rationals, and yet, the number of primes and rationals is the same. Rather shocking! 

Lemma 0.0.5 (Surprise 2).

||Q|| = ||N ||

The sets Q and N have the same cardinality. We will consider positive nonzero integers p, q in  p/q. We claim that once the map between this set and N is established, the extension to all of  Q is straightforward (using the methods outlined above in case of N and Z).  

We construct a matrix of all relevant p/q in Q as follows:

Screen Shot 2023-08-16 at 2.03.51 PM

First, we note that for any given p, q ∈ N, p/q shows up somewhere in our matrix. As the numerator increases along the vertical and the denominator along  the horizontal axis, we follow p steps upwards, then on the line where each  fraction is of the form p/n starting with p/1, we count q steps to the right until we reach p/q.  

Screen Shot 2023-08-16 at 2.05.18 PMScreen Shot 2023-08-16 at 2.05.23 PM

We define a function F that shows there are as many elements in Q as in N starting with 1/1,  F(1/1) = 1.

We notice that each finite k is k - 1 when we look at the size of the following set:

Screen Shot 2023-08-16 at 2.09.03 PM

For k=2, there is one, 1/1, for k = 3,  there are two, 2/1 and 1/2. And so on. See Table 2.

We define the function as follows. For any k in N, we order the set as follows:

Screen Shot 2023-08-16 at 2.10.15 PM

We then let

Screen Shot 2023-08-16 at 2.10.22 PM

See Table 3 for illustration.  

The rigorous proof is needed but one can intuitively see that as the function F diagonally crosses the matrix in Table 1 in each pass, it eventually covers all pairs from Q with unique elements from N. So Q and N are shown to be  equinumerous as promised.  

These relatively easy equivalences raise an important question. Are their any infinite sets that are not simply equinumerous to the natural numbers? Is there more than one kind of infinite?

The second step into the abyss: ||N|| < ||R||

The set R is strictly bigger than N and hence than Q, Z, P, etc. via the  Diagonalization Argument. There is indeed more than one kind of infinite.  

Claim for contradiction: There is a function F : (R) → N that is one-to-one and onto. That means that we can form a countably infinite table that pairs reals and  naturals. For convenience we assume that the reals are from the interval [0,1] and that all tails are extended to infinity. For example, the real number 0.1 is turned into 0.09999999999999… We then have a sequence of reals between 0 and 1 mapped one-to-one onto natural numbers like so:

Screen Shot 2023-08-16 at 2.14.01 PM

The diagonal is used to construct a real number m that could not have been caught by the function F, that is F(m) is undefined, contrary to the assumption that the mapping was one-to-one and onto. 

More on the kinds of infinities  

For set A, sets of all subsets of A, 2A, and our transfinite series, we state the following without proof:

Screen Shot 2023-08-16 at 2.17.34 PM

Theorem 0.1. There is infinitely many infinite cardinals 

Question: We showed using the diagonal argument that there are more elements in R than in N. We also showed that by taking the cardinality of the set of  subsets of natural numbers we can get a cardinal number strictly greater than  that of natural numbers. What we want to know is how much bigger is R than N? In particular, is ||R|| = ||2N||?

As yet another surprise of the infinite realm, Cohen and Gödel have  demonstrated that the standard set theory in its present form does not rule out  either the claim of their equality not the opposite. The present day mathematics  is silent on the exact cardinality of the real numbers and the number sequence  as it extends into the transfinite. We know there is no largest infinite number, but the structure of their sequence still eludes us in a large part. We are only marginally closer to understanding the infinite than we were when Georg Cantor set out to do his seminal work on set theory. If god guided him in his  discoveries, as he claims, he left plenty of important discoveries in the shadows. They have remained so despite some of this tiny planet’s best minds ceaseless efforts. Perhaps god never seriously intended us to understand the infinite.  

Although Cantor was a devout Christian and he saw his work on the infinite as  inspired by his religion, others did not see it that way. The infinite being closely associated with the almighty himself, they claimed that Theorem 0.1. proved that Cantor was a polytheist of the worst kind. Not only did he think that there are  many gods, but he was committed, according to his critics, to there being an infinity of them, though as we saw they were not all equal.  

Comments

topicTopics
academics study skills MCAT medical school admissions SAT college admissions expository writing English strategy MD/PhD admissions writing LSAT GMAT physics GRE chemistry biology math graduate admissions academic advice law school admissions ACT interview prep language learning test anxiety career advice premed MBA admissions personal statements homework help AP exams creative writing MD test prep study schedules computer science Common Application mathematics summer activities history philosophy secondary applications organic chemistry economics supplements research grammar 1L PSAT admissions coaching law psychology statistics & probability dental admissions legal studies ESL CARS PhD admissions SSAT covid-19 logic games reading comprehension calculus engineering USMLE mentorship Spanish parents Latin biochemistry case coaching verbal reasoning AMCAS DAT English literature STEM admissions advice excel medical school political science skills French Linguistics MBA coursework Tutoring Approaches academic integrity astrophysics chinese gap year genetics letters of recommendation mechanical engineering Anki DO Social Advocacy algebra art history artificial intelligence business careers cell biology classics data science dental school diversity statement geometry kinematics linear algebra mental health presentations quantitative reasoning study abroad tech industry technical interviews time management work and activities 2L DMD IB exams ISEE MD/PhD programs Sentence Correction adjusting to college algorithms amino acids analysis essay athletics business skills cold emails finance first generation student functions graphing information sessions international students internships logic networking poetry proofs resume revising science social sciences software engineering trigonometry units writer's block 3L AAMC Academic Interest EMT FlexMed Fourier Series Greek Health Professional Shortage Area Italian JD/MBA admissions Lagrange multipliers London MD vs PhD MMI Montessori National Health Service Corps Pythagorean Theorem Python Shakespeare Step 2 TMDSAS Taylor Series Truss Analysis Zoom acids and bases active learning architecture argumentative writing art art and design schools art portfolios bacteriology bibliographies biomedicine brain teaser campus visits cantonese capacitors capital markets central limit theorem centrifugal force chemical engineering chess chromatography class participation climate change clinical experience community service constitutional law consulting cover letters curriculum dementia demonstrated interest dimensional analysis distance learning econometrics electric engineering electricity and magnetism escape velocity evolution executive function fellowships freewriting genomics harmonics health policy history of medicine history of science hybrid vehicles hydrophobic effect ideal gas law immunology induction infinite institutional actions integrated reasoning intermolecular forces intern investing investment banking lab reports letter of continued interest linear maps mandarin chinese matrices mba medical physics meiosis microeconomics mitosis mnemonics music music theory nervous system