Raising the bar

Review of "Abstract Mathematics" by M. Anthony, 2011

This is the guide for courses MT2116, 2790116.

If you search the internet for "abstract mathematics," you will find that abstract mathematics as a subject does not exist in isolation. It is a method applied everywhere in advanced mathematical fields, such as abstract algebra (the study of algebraic structures like groups and rings), category theory, and model theory.

The purpose of this course is to teach students abstract thinking. This is a noble intent, but the material chosen for the course is far from the best. The best choice, in my understanding, would be to combine the abstract mode of thinking with material that would be useful in today's applications. In math departments, the usual sequence is to study analytical geometry, mathematical analysis, and linear algebra, then generalize upon these subjects by moving to functional analysis (FA). FA methods are key to several subjects with wide applications today: probability and statistics, differential equations, optimization, and abstract algebra.

Elon Musk specifically encourages studying physics (with math). The mathematical concepts essential for AI work include:

• Linear Algebra: Essential for handling data structures like vectors and matrices, fundamental to AI algorithms.

• Calculus: Vital for understanding how machine learning algorithms work, particularly optimization techniques.

• Probability and Statistics: Necessary for data analysis, interpretation, and making informed decisions within AI models.

Unfortunately, the guide under review does not stand up to this task. It does require abstract thinking (the axiomatic approach, in particular). But the level is so low that I constantly have the feeling that I am wasting my time.

A few examples will help understand my point.

The De Morgan laws hold for an infinite family of sets while the logic is the same as for two sets . However, the guide misses an opportunity to connect basic set operations (unions and intersections in section 2.9.3) to more general cases or to emphasize their logical equivalence with negation, conjunction, and disjunction (section 2.3.2). This omission keeps the discussion superficial and fails to build toward infinite extensions that could prepare students for analysis or topology.

Requiring students to study natural numbers using the axiomatic approach (section 3.7) is crazy. Nobody does this. Instead, it would be much more useful to provide axioms of real numbers because then the transition to complex numbers, linear spaces or groups would be easier.

The mathematical induction principle is used at an elementary level too often. On the other hand, the more general transfinite induction principle is never introduced. For instance, the guide proves basic properties like the transitivity of the order on natural numbers (Theorem P3 in section 3.7) using axioms, but sticks to standard induction without hinting at broader ordinal-based generalizations that could tie into set theory.

The statement that for any natural $latex n$, the number $latex n^2 + n$ is even is easily proved using $latex n = 2k$ for even $latex n$ and $latex n = 2k + 1$ for odd $latex n$. The proof of this fact using induction (see the example in section 3.4.2) is a good example of how a bad proof can obscure the result, prioritizing mechanical application of a method over intuitive parity arguments.

For the sum of successive natural numbers, there is a visual proof by Gauss. It is much more useful than the proof of Example 3.1 (in section 3.5), which relies on algebraic manipulation via induction without any geometric insight,  missing a chance to engage visual learners.

This list can be continued. Gödel's incompleteness theorems imply that the development of mathematics is infinite. A single, complete, and consistent axiomatic system that would be a foundation for all of mathematics does not exist. New axioms have to be added to answer new arising questions. The development of mathematics is endless not only in depth but also in breadth. In particular, there exists a practically infinite set of statements of the same level. This is what the guide and the exams do: they keep the student at the same low level, without increasing the depth.

Geometry and geometric intuition are an important element of mathematical discovery. Too often the guide misses the opportunity to appeal to geometric intuition. One example is the notion of a function and its inverse (section 4.4). For people used to abstract thinking, the definitions in the guide are sufficient. For everybody else, geometry would help. The guide presents inverses purely algebraically, with examples like $latex f(x) = 3x + 1$ or a bijection from integers to non-negative integers, but without graphical representations (e.g., reflecting over $latex y = x$) that could make the concept more accessible.

It is the teacher's duty to awaken students' intuition where it does not work. In my class, it did not work with the equivalence relation (chapter 5). I suggested an alternative approach using circles of friends that made things simple for all students. My approach is better because it is based on sets (of friends), which makes everything more geometric and relies on everyday experience. The guide's examples, like even sum for natural numbers (Example 5.2) or matrix powers (Example 5.3), are dry and lack relatable analogies, treating equivalence classes formally without building intuition through partitions or real-world groupings. Level sets, isoquants and indifference curves all generate equivalence classes.

After reading the section "4.5 Counting as a bijection," a reader might ask: why would I need bijections for comparing the numbers of elements of two sets, if I can just count the  numbers of their elements? The answer is that bijections are used to compare infinite sets, for which counting does not work, and this should be said at the outset. Using the term "cardinality" for finite sets (introduced in section 4.5) is one of the ways to obscure the concept, as it overcomplicates simple counting before motivating its power for infinities (section 4.7).

The proof of the Pigeonhole Principle by induction (Theorem 4.2 in section 4.6.1) is a good way to muddle the water where an instructive and much shorter proof by contradiction is possible. The guide opts for induction to show that an injection from $latex N_n$ to $latex N_m$ implies $latex n\le m$, which is unnecessarily verbose and misses the elegant contradiction approach that highlights the principle's essence.

Theorem 4.7 (in section 4.6.2) is one of many examples of statements that have no use in practice. It states that in any set of five or more points in the plane with integer coordinates,  there are two whose midpoint also has integer coordinates $latex -$ an application of pigeonhole, but one that feels contrived and irrelevant to broader applications, like combinatorics in computer science. When a professional needs such a statement, they can come up with the proof on their own, and there is no need to have it in a textbook.

Another instance of poor teaching is in the introduction of the triangle inequality (section 9.2), which is presented as a basic property of real numbers without any geometric motivation. This inequality ($latex |x+y|\leq |x|+|y| $) has a clear interpretation in vector geometry or distances, but the guide treats it algebraically, missing a chance to connect to intuitive spatial reasoning that could aid understanding of supremum and infimum (section 9.3).

The formal construction of complex numbers (section 8.5.2) as pairs of reals with operations is abstract and is good as a shortcut. While it mirrors the integer and rational constructions earlier, it delays the geometric interpretations like the complex plane until section 8.5.5, and even then without emphasizing rotations or applications in physics.

This semester is about to finish, and the remainder of the course next semester will be taught by another teacher. I covered Chapters 1-7, and my criticism applies to the most part of this material (analysis and algebra parts in the second half of the course are more useful, although I have reservations about the presentation of the material). I pity those who must use this guide and advise avoiding taking this course by all means possible.

Division of one integer by another, with remainder

There are different approaches to explaining this topic. To see the difference, first try to read Theorems 6.1 and 6.2 in Abstract mathematics (M. Anthony, MT2116), then compare to the following approach.

Statement. For any integers $latex a$ and $latex b$ with $latex b>0$, there are unique integers $latex q$ and $latex r$ such that

(1) $latex a=bq+r$ and $latex 0\leq r<b$.

Proof. We want to cover the real line with half-open intervals of length $latex b.$ For $latex n\in Z$ put $latex x_{n}=bn$ and define intervals $latex \Delta _{n}=[bn,b\left(n+1)\right) .$ These intervals obviously are disjoint and cover all real numbers. Let $latex \Delta _{q}$ be the interval that contains $latex a.$ The number $latex a$ is the left end of the interval, $latex bq,$ plus some integer number $latex r.$ Since $latex bq\leq a=bq+r<bq+b,$ we have $latex 0\leq r<b$. Obviously, both $latex q$ and $latex r$ are unique.

The Euclidean algorithm

In Section 6.6 this algorithm is given without a proof. The proof is not  very complex and can be found here.  There you can also find a different version of the algorithm that converges faster, a statement that it is the best possible and an interesting visialization of the algorithm using tiles. Here we suggest a different visualization that is easier to use for practical calculations.

The main property of the algorithm written in the form

(2) $latex gcd(a,b)=gcd(b,r)$

($latex gcd$ stands for Greatest Common Divisor) is not good for visualizing. To better reflect its iterative nature, we can write (1) as $latex a_{1}=a_{2}q+a_{3}$ and then (2) becomes

(3) $latex gcd(a_{1},a_{2})=gcd(a_{2},a_{3}).$

Expanding the first three equations, we see that the calculations can be arranged as in the next table. After each division, we place the numbers $latex a_{k},a_{k+1}$ in the next row below their positions in the previous row and then fill out the rest of the formula with the quotient and remainder.

$latex \Large \left.\begin{array}{lllllllll}
a_{1} & = & a_{2}q_{1} & + & a_{3} & & & &\\
& & a_{2} & = & a_{3}q_{2} & + & a_{4} & &\\
& & & & a_{3} & = & a_{4}q_{3} & + & a_{5}\\
& & & & & & ... & ... & ...\end{array}\right.$

Equivalence relation explained

Many students struggle understanding an equivalence relation. The problem with it is that it is a mental concept that heavily relies on the axiomatic approach. It is the teacher's task to give a more visual and tangible (closely related to real-life experience) definition. The definition should be preceded or accompanied by an explanation that awakes the students' intuition.

For any person $latex p,$ denote $latex Fr\left( p\right) $ the circle (set) of that person's friends. We assume that for each $latex p,$ the circle of friends $latex Fr\left( p\right) $ is unique (in reality, depending on the situation, the circle of friends may change, inluding childhood friends, colleagues, neighbors etc.).

Definition 1. The mapping $latex p\rightarrow Fr\left( p\right) $ satisfies the following conditions.

a) We assume, by definition, that any person is a friend of him/herself. Then, obviously, $latex p\in Fr\left( p\right) .$

b) When $latex p$ considers $latex q$ a friend, $latex q$ does not necessarily consider $latex p$ a friend. We exclude such a situation and consider friendship to be a mutual feeling. Then $latex q\in Fr\left( p\right) $ implies $latex p\in Fr\left( q\right) .$

c) We assume that the adage "a friend of my friend is my friend" is true (in reality, my friends often have their own friends whom I do not consider my friends). In terms of our friendship sets this means that $latex q\in Fr\left(p\right) $ and $latex r\in Fr\left( q\right) $ implies $latex r\in Fr\left( p\right) .$

Remark. In fact, it is sufficient to assume that for each $latex p,$ the circle of friends $latex Fr\left( p\right) $ exists, and then by c) we will have its uniqueness. The mapping $latex p\rightarrow Fr\left( p\right) $ is not a function, because $latex Fr\left( p\right) $ can consist of more than one person. Such a mapping is called a correspondence.

Statement. 1) The circles of friends $latex Fr\left( p\right) $ cover all people. 2) Any two circles $latex Fr\left( p\right) ,$ $latex Fr\left( q\right) $ either coincide, $latex Fr\left( p\right) =$ $latex Fr\left( q\right) $ or do not intersect, $latex Fr\left( p\right) \cap Fr\left( q\right) =\varnothing $ (the situations $latex Fr\left( p\right) \backslash Fr\left( q\right) \neq \varnothing $ and $latex Fr\left( q\right) \backslash Fr\left( q\right) \neq \varnothing $ are impossible).

Proof. 1) is obvious because $latex p\in Fr\left( p\right) .$ 2) If $latex Fr\left(p\right) =$ $latex Fr\left( q\right) ,$ there is nothing to prove. Let $latex Fr\left(p\right) \neq Fr\left( q\right) .$ If $latex Fr\left( p\right) \cap Fr\left(q\right) =\varnothing ,$ then again there is nothing to prove. Suppose

(1) $latex Fr\left( p\right) \cap Fr\left( q\right) \neq \varnothing $ for some $latex p,q.$

Take any $latex r\in Fr\left( p\right) \cap Fr\left( q\right) $ ($latex r$ is a friend of both $latex p$ and $latex q).$ Then by Property 2 the inclusion $latex r\in Fr\left(q\right) $ can be reversed: $latex q\in Fr\left( r\right) .$ We get $latex r\in Fr\left(p\right) ,$ $latex q\in Fr\left( r\right) $ ($latex r$ is a friend of $latex p$ and $latex q$ is a friend of $latex r)$ and by Property 3 $latex q\in Fr\left( p\right) $ for any $latex q$ satisfying (1), which implies $latex Fr\left( q\right) \subset Fr(p)$. Similarly, $latex Fr\left( p\right) \subset Fr(q).$ Thus, we have the coincidence $latex Fr\left(p\right) =$ $latex Fr\left( q\right) .$

Now we can define the relation $latex \sim$ on the set of all people by saying that $latex p\sim q$ if $latex q\in Fr\left( p\right) .$ With this notation, assumptions a)-c) easily translate to the axioms:

Definition 2. The relation $latex \sim$ we just defined is an equivalence relation properties, that is, it satisfies the axioms:

Axiom 1. Reflexivity. For any $latex p,$ we have $latex p\sim p$ (follows from a)).

Axiom 2. Symmetry. $latex q\sim p$ implies $latex p\sim q$ (follows from b)).

Axiom 3. Transitivity. $latex q\sim p$ and $latex r\sim q$ implies $latex r\sim p$ (follows from c)).

On the picture: level sets define an equivalence relation: all points belonging to the same level set are declared to be equivalent to each other.

Level set

De Morgan's laws explained

Source: onlinemathlearning.com

Simple form: $latex \overline{A\cap B}=\bar{A}\cup \bar{B},$ (1) $latex \overline{A\cup B}=\bar{A}\cap \bar{B}.$ (2)

Note that the usage of the complement assumes that there is a universal set $latex U$ of which $latex A,B$ are subsets, so that $latex \bar{A}=U\backslash A.$

These laws can be applied for help with logical reasoning. For example, let $latex A$ be the set of girls, $latex B$ be the set of blondes. For simplicity, assume that $latex \bar{A}$ is the set of boys and $latex \bar{B}$ is the set of brunettes. Then $latex A\cap B$ means "blonde girls" and the left side of equation (1) means NOT "blonde girls". It is not good to have a negated statement, so instead we can have a statement in positive terms from the right side of equation (1): this is the set of boys (any hair color) or brunettes (any sex) or brunette boys.

General form. Let $latex \left\{ A_{i}:i\in I\right\} $ be any family of sets (can be infinite). Then

$latex \overline{\cap _{i}A_{i}}=\cup _{i}\bar{A}_{i},$ (1')

$latex \overline{\cup _{i}A_{i}}=\cap _{i}\bar{A}_{i}.$ (2')

Proof. To see the essence behind formal arguments, verbalize the definitions for yourself. Verbalizations should be concise (easy to grasp) and precise.
For example:

$latex A\cap B$ means the set of common elements of $latex A$ and $latex B.$ Hence, $latex \overline{A\cap B}$ means those elements that are not in at least one of them.

$latex A\cup B$ is the set of elements that belong to at least one of $latex A$ or $latex B.$ Hence, $latex \overline{A\cup B}$ is the set of elements that are not in any of $latex A$ or  $latex B.$

Equation (1') is proved as follows. Denote $latex X=$ $latex \overline{\cap _{i}A_{i}}$ the left side and $latex Y=\cup _{i}\bar{A}_{i}$ the right side. If we show that $latex X\subseteq Y$ and $latex X\supseteq Y$ at the same time, then it will follow that $latex X=Y$. This is shown element by element.

Suppose $latex x\in X.$ Then $latex x$ does not belong to $latex \cap _{i}A_{i}.$ That is, it is not a common element of $latex A_{i}.$ Hence there exists $latex A_{i}$ which does not contain $latex x$ and therefore $latex x\in \bar{A}_{i}.$ It follows that $latex x\in Y.$ Since $latex x\in X$ is arbitrary, we have $latex X\subseteq Y.$

Conversely, let $latex y\in Y.$ Then $latex y$ belongs to at least one of $latex \bar{A}_{i}.$ This means $latex x$ does not belong to $latex A_{i}.$ So it cannot be an element common to all $latex A_{i.}.$ Hence, it belongs to $latex \overline{\cap _{i}A_{i}}=X.$ Again, since $latex y$ was an arbitrary element of $latex Y,$ we have $latex X\supseteq Y.$

Boxes-and-balls principle

This is my response to Section 4.6 "The pigeonhole principle" of the study guide "Abstract mathematics" by M. Anthony (MT2116, 2790116), 2011.

For the name, I prefer "Boxes-and-balls principle".

Statement. There are some boxes and balls. The balls are randomly thrown into boxes. 1) If the number of balls $latex m$ is larger than the number of boxes $latex n$, then at least one of the boxes should contain more than one ball. 2) If we know that all balls have been put into boxes and no box contains more than one ball, then it must be that $latex m\leq n.$

Proof by contradiction. 1) Assume that no box contains more than one ball. Let us number the boxes: $latex B_{1},...,B_{n}.$ Let us count the number of balls in each box: $latex m_{1}\leq 1$ in box $latex B_{1},\ ...,$ $latex m_{n}\leq 1$ in box $latex B_{n}. $ Obviously, then the total number of balls does not exceed $latex n:  m=m_{1}+...+m_{n}\leq n.$ This contradicts the statement condition that $latex m>n$ and the contradiction proves that our assumption was wrong.

2) If we assume that $latex m>n,$ then by part 1) at least one box should contain more than one ball, contradicting the condition in part 2).

Compare this proof to the cumbersome proof using induction in the guide on pp. 62-63.

There are typos in the proof of Theorem 4.6, so I provide the correct and slightly reformulated version.

Theorem 4.6. In a room there are $latex n\geq 2$ people. Then there are at least two people with the same number of friends.

Proof. Let $latex P$ be the set of people in the room and let $latex f(p)$ denote the number of friends of person $latex p\in P.$ For the purposes of this proof, we assume that no person is considered a friend of him/herself. (The opposite definition, that every person is his/her own friend, is handled with a small change in the argument). From this definition it follows that $latex 0\leq f\left(p\right) \leq n-1$ for any $latex p.$ Now consider two cases:

1) If some $latex p_{1}$ has every person in the room as a friend, then $latex f\left(p_{1}\right) =n-1$ and there are no people who don't have any friends, so that $latex f\left( p\right) >0$ for any other person.

2) Suppose that some $latex p_{2}$ does not have any friends, that is, $latex f\left(p_{2}\right) =0$. Then for any other person $latex p,$ the number of friends cannot be larger than $latex n-2$ (because $latex p_{2}$ and self are excluded).

Thus, the situations a) exists $latex p_{1}$ such that $latex f\left( p_{1}\right) =n-1$ and b) exists $latex p_{2}$ such that $latex f\left( p_{2}\right) =0$ cannot occur at the same time. Now let us group people by the number of friends they have: we write $latex p\in P_{k}$ if $latex f\left( p\right) =k.$ As we just established, the conditions $latex k=0$ and $latex k=n-1$ are mutually exclusive. Hence, the number of possible values of $latex k$ is necessarily a subset of either $latex \left\{1,...,n-1\right\} $ or $latex \left\{ 0,1,...,n-2\right\} .$ Treating the sets $latex P_{k}$ as boxes (their number is $latex n-1$) and the people as balls, by the boxes-and-balls principle at least two people should be in the same box and have an equal number of friends.