Counting Infinity (Tuklas Vol. 14, No. 6 - Jan. 19, 2013)

COUNTING INFINITY

Counting is a very basic skill. It's usually a person's first encounter with mathematics. In fact, some people believe that this is the extent to which math is relevant to their lives. However, it turns out that something as simple as counting can behave very strangely under certain circumstances.

Let's start with the set of natural numbers \(\mathbb{N} = \{1, 2, 3, \ldots\}\). These are the very first numbers taught to us, and we usually learn them within the context of counting. If we want to bring the math into it, the idea of counting can be linked to the cardinality of a set. Remember, cardinality is the number of elements that are in the set. We can use cardinality as a way of determining whether one set is larger than the other. Of course, this would only make sense as long as the sets were finite. What happens with infinite sets? Which is larger, \(\mathbb{N}\) or the set of integers \(\mathbb{Z}\)? What about the set of rational numbers \(\mathbb{Q}\) and the set of all real numbers \(\mathbb{R}\)?

We'll try to answer these questions. \(\mathbb{N}\) has no negative numbers, so it seems that \(\mathbb{Z}\) is "larger". Of course, if we expand to fractions, \(\mathbb{Q}\) will be "bigger". If we include irrational numbers, \(\mathbb{R}\) is the "largest". But then again, all of these sets have an infinite number of elements, so by our current idea of cardinality no one is larger or smaller than the other. Our previous construction thus breaks down. Sadly, it seems our intuition fails us here. 

Let's try to stretch the idea of counting to accomodate this notion of infinity. We now introduce the idea of a countable set. Formally, a set is said to be countable if it shares a one-to-one correspondence with some subset of the set of natural numbers. For example, the set \(\{a,b,c\}\) can be matched to the set \(\{1,2,3\}\) which is a subset of \(\mathbb{N}\). In fact, the easiest matching here corresponds to the idea of counting (in a finite sense). However, the idea of countability also allows us to get an idea of how to determine the cardinalities of infinite sets. Simply put, if a set is countable, then it has the same cardinality as the set of natural numbers.

What we need to do then is establish a mapping from the set we are "counting" to \(\mathbb{N}\) . Here's where strange things start to happen. It turns out that \(\mathbb{Z}\)  and \(\mathbb{Q}\)  are countable. However, the unit interval (0,1) is not. Neither is \(\mathbb{R}\). This amazing result was discovered by Georg Cantor in 1891 using a proof by contradiction and a technique now called Cantor's diagonalization argument.

We'll deviate from Cantor's full proof and prove a smaller case that we can generalize later. Let's show that the unit interval is uncountable by first supposing that it is countable then arriving at a contradiction. Note that we can represent all the elements of the unit interval by the sequence of numbers \[ \begin{align*} x_1 &= 0.d_{11}d_{12}d_{13}\ldots \\ x_2 &= 0.d_{21}d_{22}d_{23}\ldots \\ x_3 &= 0.d_{31}d_{32}d_{33}\ldots \\ \vdots \end{align*} \] where \(d_{ij}\) is a number from 0 to 9. Our mapping from \(\mathbb{N}\) to this set would simply be the matching where \(1 \rightarrow x_1, 2 \rightarrow x_2\) and so on.

We now construct a new number \(y = 0.y_1y_2y_3\ldots\) with the condition that \(y_i \neq d_{ii}, 0, 9\). In effect, each decimal place has a different value from its corresponding pair in the "diagonal" formed by the sequence. The restriction for 0 and 9 means that we want to prevent getting numbers such as \(0.000\ldots = 0\), \(0.999\ldots = 1\) or \(0.4999\ldots = 5\).

Note that \(y\) is inside the interval (0,1), but by the way it was made it's not equal to any of the numbers in our created sequence. Even if we include this number, we can always find a new number that is not inside the sequence because the included number introduces a new diagonal element. Hence, we have a contradiction.

Next, let's show that the unit interval and the set of real numbers have the same cardinality. Consider the unit interval as a line segment placed 1/2 units above the real number line such that 1/2 on the unit interval is directly above 0 on the real number line. If we place a point in the middle of the unit interval, we can trace a semicircle underneath the unit interval. 

Note that we can draw a line segment from any number on the real number line towards the center of the semicircle we made (see below). Each segment intersects the semicircle at exactly one point. Furthermore, each point of intersection is directly below a number in the unit interval. We now have a matching between the numbers in (0,1) and the set of all real numbers, hence they share the same cardinality.

Confused? Don't worry. When Cantor first published his results, many mathematicians were shocked (some outraged) and campaigned against him and his ideas. His results were so counter-intuitive that some of his colleagues flat out rejected them. However, it cannot be denied that his ideas had merit, and in the end they were accepted by the mathematics community. Thanks to Cantor, we can see for ourselves how something as boring as counting can have mind-bending properties.

ABOUT THE AUTHOR:
Jesus Lemuel Martin, Jr. obtained his B.S. in Applied Mathematics major in Computational Science at the Ateneo de Manila University in 2010 and is currently taking his MS in Mathematics at the same university.

OLYMPIAD CORNER

from the Asian Pacific Mathematics Olympiad, 2012

Problem: Let \(P\) be a point in the interior of a triangle \(ABC\), and let \(D, E, F\) be the point of intersection of the line \(AP\) and the side \(BC\) of the triangle, of the line \(BP\) and the side \(CA\), and of the line \(CP\) and the side \(AB\), respectively. Prove that the area of the triangle \(ABC\) must be 6 if the area of each of the triangles \(PFA, PDB\) and \(PEC\) is 1.

Solution: 

Let \([XYZ]\) denote the area of triangle \(XYZ\). Let \(x=[PAB], y = [PBC]\) and \(z=[PCA]\).

Note that \[ \frac{BF}{AF} = \frac{[BPF]}{[APF]}=\frac{[BCF]}{[ACF]}=\frac{[BPF]-[BCF]}{[APF]-[ACF]}=\frac{[PBC]}{[APC]}=\frac{y}{z} \] hence \(y:z=\left(x-1\right):1\), which implies \(\left(z+1\right) x=x+y+z\). Similarly, we get \(\left( x+1\right) y=x+y+z\) and \(\left( y+1\right) z=x+y+z\). Thus, we obtain \[ \left( x+1\right) y=\left( y+1\right) z=\left( z+1\right) x. \]Assume, without loss of generality that \(x\leq y\) and \(x\leq z\). If \(y>z\), then \(\left( y+1\right) z>\left( z+1\right) x\), which is a contradiction. Likewise, if \(y<z\), then we have another contradiction as \((x+1)y<(y+1)z\). Therefore, \(y=z\). And as a result, the equality \(\left(y+1\right)z=\left(z+1\right)x\) would yield \(x=z\).

We now obtain from \(\left( x-1\right) :1=y:z=1:1\) that \(x=y=z=2\). Therefore, we can conclude that the area of the triangle \(ABC\) equals \(x+y+z=6\).

PROBLEMS

16. Show that among all boxes with a given surface area, the cube has the largest volume.
17. Three circles with the same radius pass through a common point. Let \(S\) be the set of points which are interior to at least two of the circles. How should the three circles be placed so that the area of \(S\) is minimized?
18. A line that contains the centroid \(G\) of the triangle \(ABC\) intersects the side \(AB\) at \(P\) and the side \(CA\) at \(Q\). Prove that \[ \frac{PB}{PA}\cdot\frac{QC}{QA} \leq \frac{1}{4}. \]

We welcome readers to submit solutions to the problems posed below for publication consideration. Solutions may be submitted to the PEM facilitators on the deadline date or online via mactolentino@math.admu.edu.ph. Solutions must be preceded by the solver's name, school affiliation and year level. The deadline for submission is 12:00 PM January 26, 2013. 

SOLUTIONS

(for January 12, 2012)

14. There are \(n\) straight lines in a plane, such that every two intersect with each other. Prove that among the angles formed there is at least one angle which is not greater than \(\frac{180^\circ}{n}\). (Romanian Mathematical Olympiad, 2004)
    (Solved by Clyde Wesley Ang [Chang Kai Shek College], Terence Tsai [Chang Kai Shek College] and Farrell Wu [MGC New Life Christian Academy])
    
    
    SOLUTION: 
    From the \(n\) lines we can form \(4\binom{n}{2} = 2n(n-1)\) angles. By translation to a fixed point \(O\) on the plane, the \(2n(n-1)\) angles form \(2n\) angles. If all of the angles formed are greater than \(\frac{180^\circ}{n}\) then the sum is greater than \(2n\cdot\frac{180^\circ}{n} = 360^\circ\) which is impossible, and we are done.
15. In the figure above (omitted), \(ABCDEF\) is a regular hexagon. The midpoint of \(\overline{AB}\) is \(W\) and \(X\) and \(Y\) are intercepts as shown. What is the value of \(\frac{[XYDE]}{[WXF]}\)? (Australian Mathematics Competition, 1995)
    (Solved by Farrell Wu [MGC New Life Christian Academy], partial credit for Clyde Wesley Ang [Chang Kai Shek College] and Terence Tsai [Chang Kai Shek College])
    
    
    SOLUTION: 
    Note that the interior angle of a regular hexagon is \(120^\circ\). Let \(a\) be the length of any side of \(ABCDEF\). We solve for the length \(\overline{AE}\) from \(\Delta AEF\) by applying the Cosine Law to get \[ \overline{AE} = \sqrt{a^2 + a^2 - 2a^2\cos \theta} = \sqrt{3}a. \] The heights of \(WXF\) and \(XYDE\) are thus \(\sqrt{3}a/2\). We now solve for the lengths \(\overline{XY}\) and \(\overline{FX}\). Via similar triangles, \(\overline{XY} = a/2\) hence \[ [XYDE] = \frac{3\sqrt{3}a^2}{8}. \] If we let \(M\) be the intersection of \(\overline{AE}\) and \(\overline{CF}\), \(\overline{FM} = a/2\). Furthermore, since \(\overline{AE}\) is perpendicular to \(\overline{CF}\), \(\overline{MX} = a/2 - \overline{XY}/2\). Hence,  \[ [WXF] = \frac{3\sqrt{3}}{16}a^2 \Leftrightarrow \frac{[XYDE]}{[WXF]} = 2. \]