Proofs in the Pudding - Spring 2023 Math 300 Class Blog

I Thought a Cardinal Was a Bird: Exploring the Interactions Between Cardinal and Ordinal Numbers

June 3, 2023ssf6454 Leave a Comment

Shaafi Flener

In class, we discussed what cardinality of a set was: a measure of how large or small that set is. But that begins to raise the question, how do we quantify a set that has infinite elements, or, honestly, any set beyond just assigning a number to it based on the number of elements? In this blog post, I will be showing the difference between cardinal and ordinal numbers, and how they might interact.

Cardinal numbers

First, we look at cardinal numbers. These represent the size or quantity of elements in a set. They answer the question, “How many?” We already know that cardinality defines the size of a set, for both finite and infinite sets.. For finite sets, cardinal numbers are standard natural numbers (0, 1, 2, 3, …). The cardinality of a set $A$ is denoted as $|A|$ .

But what about infinite sets? As we showed through Cantor’s Theorem, we know that infinite sets can have different sizes. The smallest infinite set, the set of natural numbers ( $\mathbb{N}$ ), has an infinite cardinality denoted as $\aleph_0$ (aleph-null). Other infinite sets, such as the set of real numbers ( $\mathbb{R}$ ), have a greater cardinality, represented as $\aleph_1$ (aleph-one).

Ordinal numbers

While the idea of a cardinal number is a basic one, the ordinal numbers take the notion of a number a step further.… Read the rest

Matrices: Surjective, Injective, and Bijective Linear Transformations

June 3, 2023itj5091 1 Comment

IceT Thaewanarumitkul

Transformation is another synonym for “function” but its terminology implies the heavy focus on “movement” of geometric components such as lines, curves, and regions. Today, we will explore the properties of linear transformation which is one of the central topics in linear algebra.

Linear transformations

A linear transformation, in the world of matrices, is a transformation satisfying two conditions.

The transformation preserve the properties of lines and curves.
The origin is fixed.

These two conditions seems complicated to imagine geometrically and we will talk about them numerically instead.

Consider the equation $b = Ax$ when $x$ is a vector in $\mathbb{R}^n$ , $A$ is an $m \times n$ matrix, and $b$ is the output vector in $\mathbb{R}^n$ represents a linear transformation from $\mathbb{R}^n$ to $\mathbb{R}^m$ . We also can write the conditions of a linear transformation in terms of function.

Let $T \colon V \to W$ be a linear transformation from $V \in \mathbb{R}^n$ to $W \in \mathbb{R}^m$ . Here, $V$ is called the domain of $T$ and $W$ is called the codomain of $T$ . The range of $T$ , denoted by $\text{range}(T)$ or $\text{Im}(T)$ is the set of all possible outputs, which is a subset of $W$ , defined by

$\text{range}(T)$ = $\{ T(x) \mid x \in V \}$

Since $T$ is a linear transformation, the two conditions of linear transformation still hold and can be described as

$T(kx+ly)$ = $kT(x) + lT(y)$ for all $x, y \in V$ and all $k,l \in \mathbb R$ .
$T(0) = 0$ (The origin).

Looking back to the equation $b = Ax$ , we realize that $b$ is a linear combination of the columns of $A$ ; therefore, $\text{range}(A)$ is the same as the column space of $A$ .… Read the rest

Fuzzy Set Theory: To Be in a Set, or not Be in a Set? Maybe It’s not that Simple…

June 1, 2023jrh7328 1 Comment

John Hileman

When we began this class, we all learned one thing about sets: an element can either be in a set or not. In our proofs, $x \in A$ and $x \not\in A$ was a contradictory statement. However, fuzzy set theory makes that a statement that is entirely possible. Fuzzy set theory, as a philosophical concept, was introduced in the early 1900s by Zadeh and Goguen when they declared that the concept of traditional set theory does not make sense in a real-world application because in real-life, things are not nearly as black or white. In reality, there is a lot more gray area, which is what fuzzy set theory as a whole is trying to conceptualize.

The figure above shows a generalized example to introduce you to the concept of fuzzy set theory. Fuzzy set theory could take an entire course to explain, and there are many definitions and proofs involved. However, as a basic introduction for you all, I will talk about some definitions that strongly relate to our course. This leads us to our first definition, a fuzzy set is one of the form $A^{\sim} = \{(x, \mu_{\sim}(x)) \mid x \in X\}$ where $X$ is a traditional set, and $\mu_{\sim}$ is a fuzzy membership function that maps $X$ to a membership space that has a value between 0 and 1.… Read the rest

The Infiniteness of Words

May 31, 2023mbm9123 2 Comments

Maya Mubayi

Countable, uncountable, and infinite sets can be found everywhere, from pure mathematical cases to sets we find in everyday life. We know that sets of numbers, such as $\mathbb{R}$ , $\mathbb{N}$ , $\mathbb{Z}$ , and many more can be classified as countable, uncountable, and infinite. Similarly, you can think of a tree as an infinite or finite set of branches, or even your own wardrobe as a finite set of pant-shirt-shoe combinations. What about the words in the English language? The number of possible English sentences? The number of possible books? Are those finite sets? Infinite sets? Uncountable sets? I will explore these questions further in this blog.

Why Are the Set of English Words Finite?

First define $E$ as the set of all English words. Since we are dealing with words, we can assume that there is in fact a longest word in the English language. Let the length of this word be $n$ for $n \in \mathbb{N}$ . If $E_{1}$ is the set of all English words of length 1, $E_{2}$ is the set of all English words on length 2, and so on, we know that $E_{1} \cup E_{2} \cup$ … $\cup E_{n} = E$ . Since there are at most 26 options for any letter, for each $E_{i} \subseteq E$ for $i \le n$ . This means that $E$ is composed of a finite union of finite sets.… Read the rest

Saying Hi to Binomials

May 30, 2023tlp5169 1 Comment

Teresa Pan

$\displaystyle \binom{H}{i}$

In class, we talked a bit about factorials. Specifically, we defined it like so:

$0! = 1, \ n! = (n-1)! \cdot n$

Now, let’s talk about binomial coefficients. We can define them using recursion:

$\binom{n}{0} = 1$
$\binom{0}{k} = 0$
$\binom{n+1}{k+1} = \binom{n}{k} + \binom{n}{k+1}$

This gives us Pascal’s triangle, which was actually discovered by an Indian mathematician named Pingala in the 3rd century. Pascal didn’t exist until the 17th century, so who knows what they called this triangle during those 1400 years. Anyways, here are the first few rows of Pascal’s triangle, constructed using the recursion above:

Sums of binomial coefficients

A very interesting property of Pascal’s triangle is that the sum in every rows add to a power of 2. This can be proved using inductive reasoning:

Base case: When $n = 0$ , we have $\binom{0}{0} = 1 = 2^0$ . The base case is true.

Inductive step: Let’s have $n \geq 0$ . Suppose $\sum_{i = 0}^n \binom{n}{i} = 2^n$ . We want to prove $\sum_{i = 0}^{n+1} \binom{n+1}{i} = 2^{n+1}$ .

$\sum_{i = 0}^{n+1} \binom{n+1}{i} = \binom{n+1}{0} + \sum_{i = 1}^{n+1} \binom{n+1}{i}$

$= 1 + \sum_{j = 0}^{n} \binom{n+1}{j+1}$ by reindexing with $j = i - 1$

$= 1 + \sum_{j = 0}^{n} \binom{n}{j} + \binom{n}{j+1}$ by the recursive definition of binomial coefficients

$= 1 + \sum_{j = 0}^{n} \binom{n}{j} + \sum_{j = 0}^{n} \binom{n}{j+1}$

$= 1 + 2^n + \sum_{j = 0}^{n} \binom{n}{j+1}$ by the inductive hypothesis

For $\sum_{j = 0}^{n} \binom{n}{j+1}$ , we reindex again with $k = j + 1$ and obtain

$\sum_{j = 0}^{n} \binom{n}{j+1} = \sum_{k = 1}^{n+1} \binom{n}{k} = \binom{n}{n+1} -\binom{n}{0} + \sum_{k = 0}^{n} \binom{n}{k}$

We assumed $\sum_{k = 0}^{n} \binom{n}{k} = 2^n$ to be true, and that $\binom{n}{n+1} = 0$ , and $\binom{n}{0} = 1$ . Thus, $\sum_{j = 0}^{n} \binom{n}{j+1} = 2^n - 1$ . Finally,

$\sum_{i = 0}^{n+1} \binom{n+1}{i} = 1 + 2^n + 2^n - 1 = 2(2^n) = 2^{n+1}$ ,

which is what we expected. We are done!

How do factorials relate to binomial coefficients?

Of course, learning combinatorics is how a lot of us were introduced to factorials.… Read the rest

Addition and Multiplication on the Rational Numbers

May 30, 2023pcp1316 Leave a Comment

Patrick Chen

We may not realize it, but addition and multiplication on the integers can be seen as functions. For example, we can represent addition on the integers as the function $a: \mathbb{Z}^{2} \rightarrow \mathbb{Z}$ defined by $a(x,y) = x + y$ for all $(x,y) \in \mathbb{Z}^{2}$ . Similarly, we can represent multiplication on the integers as $m: \mathbb{Z}^{2} \rightarrow \mathbb{Z}$ defined by $m(x,y) = xy$ for all $(x,y) \in \mathbb{Z}^{2}$ . Because of this, addition and multiplication just like functions must be well-defined, meaning that the sum of two elements elements and the multiplication of two elements must be unique. In the case of integers by the way they are defined, this is pretty trivial.

However, it becomes less trivial as we move to the rational numbers $\mathbb{Q}$ . This is because every rational number can be represented infinitely many ways. For example, $\frac{1}{2}$ can be represented as $\frac{2}{4}, \frac{3}{6}, \frac{-1}{-2}$ , …. and $\frac{1}{3}$ can be represented as $\frac{2}{6}, \frac{3}{9}, \frac{-1}{-3}$ , …. since they all represent the same value. Because of this, we must ensure that the result from addition and multiplication are well defined, meaning they don’t depend on the way we represent the different values.

In this post, we will define addition and multiplication on the rational numbers and prove that they are well defined.

Recall from Class

As we have seen in lecture, we can build the rational numbers through the equivalence relation $\simeq$ on $\mathbb{Z} \times \mathbb{Z}\backslash\{0\}$ defined by $(a,b) \simeq (c,d)$ if $ad = bc$ .… Read the rest

Can an Infinite Hotel Run Out of Rooms?

May 30, 2023djl9295 2 Comments

David Leshem

What if I told you that I would pay for your trip to a dream destination? You have the location picked out, the activities planned, and the flights booked. Lastly, you need a place to stay. You choose the fanciest hotel in town. Unfortunately, this hotel has a finite number of rooms, and due to some procrastination, they are fully booked. What a shame. Luckily, you hear about an “infinite hotel” that is just a few doors down from where you wanted to stay. The name of this hotel is Hilbert’s Hotel, named after the findings of famous mathematician David Hilbert.

Hilbert’s Hotel

Hilbert’s Hotel has an infinite capacity, and the management promises that it can find space for anyone. Let’s investigate if this is true. Each room is assigned a Natural number starting from 1, 2, 3, and extending to infinity. Imagine the hotel is full. There are an infinite number of people staying in the hotel with an infinite number of rooms. However, they can accommodate you. The manager of the hotel will simply ask the person in room 1 to move to room 2, the person in room 2 to move to room 3, and so on.… Read the rest

Infinite Dust: the Counterintuitive Cantor Set

May 25, 2023Chana 1 Comment

Chana Lyubich

Often, we study smooth, differentiable functions with the assumption that they are an adequate mathematical tool to describe our world. However, they are not always sufficient. A well-known example of this is the coastline paradox, which observes that the length of a coastline is not well-defined: rather, it depends on how the measurement was made. This is because a coastline has fractal properties, and does not resemble a differentiable curve. Indeed, fractals can be used to describe many concrete phenomena in nature, despite often having strange, counterintuitive properties!

One of the first examples of a fractal is the Cantor Set, which was discovered by Georg Cantor in 1883. (Incidentally, Georg Cantor is also the founder of set theory.) While the construction of the Cantor Set is deceptively simple, it results in some seemingly incompatible properties.

We can construct the Cantor Set $K$ as follows:

Let us take the segment $[0, 1]$ and remove the open middle third (that is, we remove the interval $(\frac{1}{3}, \frac{2}{3})$ ). We will label this first gap as $G^0$ and the two remaining segments as $I_{0}^{1}$ and $I_{1}^{1}$ . In this labeling method, the superscript indicates the “level” of the segment and the subscript indicates whether it is the left (0) or right (1) segment.… Read the rest

Logical Operators, So what? Why are they important? What can they do?

May 22, 2023uno 2 Comments

Christopher Minn

Logical operators are all around us. Whether you realize it or not, when you make a decision of eating cereal and milk for breakfast, choosing between pasta or rice for lunch, or choosing not to study for an exam despite your lack of preparation (which is occurring to me as I write this), all of these statements contain a logical operator. the most common operators seen around consist of AND, OR, NOT, and a combination of these three in order to produce other outputs. Eating cereal AND milk, pasta OR rice, and choosing NOT to study all embody these different operators. Now, in math, these operators also play a crucial part in producing some of the foundations that can be used to build a deeper understanding of simple logic. For example, different truth tables that can be constructed from the basics of AND, OR, and NOT operators. However, in math, these operators are actually represented as the following: AND as $\wedge$ , OR as $\vee$ and NOT as $\neg$ . Below, I will include a basic truth table to demonstrate how these operators operate (no pun intended) in math.

As you can (hopefully) see, P and Q represent different variables that can be either true or false, and depending on the logical operator applied, the outputs differ.… Read the rest

Typesetting mathematics

May 12, 2023Shuyi Weng Leave a Comment

This blog post is a short introduction to how to type mathematical expressions using LaTeX commands. On the blogging platform we are using, this is achieved by MathJax. Some documentations can be found here.

If you have a mathematical expression to type, you may start by entering “$latex” (remove quotation marks), writing the corresponding LaTeX commands, and then closing with another “$” (again, no quotation marks). Note that on your regular LaTeX editor (or Overleaf), you only need to enclose mathematical expressions by a pair of dollar signs.

Example: The less-than-or-equal relation on real numbers is given by $R=\{ (x,y) \in \mathbb{R}^2 \mid x \leq y \}$ ($latex R=\{ (x,y) \in \mathbb{R}^2 \mid x \leq y \}$)

Most of the commands are pretty intuitive:

Most stuff: Just type them! For example, $1+2=3$ ($latex 1+2=3$) and $f(x)$ ($latex f(x)$)

Exponents: Use ^{exponent}; remember to enclose the entire exponent in a pair of curly brackets. For example, $e^{-2x}$ (e^{-2x}, but not e^-2x, because the latter will produce $e^-2x$ )

Subscripts: Use _{subscript}. This is very similar to exponents. For example, $A_{0}$ (A_{0}) or $a_{10}$ (a_{10}, but not a_10, because the latter will produce $a_10$ )

Functions: Use \colon instead of “:” and use \to for the arrow.… Read the rest