Posts

Well-Ordered Sets and Induction

The purpose of this post is to provide a more sophisticated perspective on the principle of (strong) mathematical induction: Let \(P(n)\) be a statement about the natural number \(n\) such that \(P(1)\) holds, and such that \(P(1)\land P(2) \land ... \land P(n) \implies P(n+1)\). Then \(P(n)\) holds for all natural numbers \(n\). I want to begin by introducing the notion of a well-ordered set and then using this notion to give an equivalent statement of the principle of induction. Definition (Well-Ordered set):  An ordered set \(A\) is called well-ordered if every non-empty subset of \(A\) has a smallest element. The principle of mathematical induction is equivalent to the statement that the natural numbers are well-ordered. Why is this so? Well, to see this we consider the set \(S\) of natural numbers for which the proposition \(P(n)\) doesn't hold. If it is not empty, then let \(k\) be the smallest element. Since \(P(1)\) holds we know that \(k \neq 1\). But if \(P(k)
Post a Comment
Read more

On the Number of Subsets Divisible by \(k\)

In my first post, I want to discuss an elementary combinatorics problem. Somewhat surprisingly, considering complex numbers provides a very slick solution. The problem is as follows: how many subsets of \(n\) elements have size divisible by \(k\)? I first want to consider the case when \(k = 2\). Now we are simply asking how many subsets of \(\{1,...,n\}\) have an even number of elements. If you have never seen this problem before, you may want to take a few minutes to think about it before continuing. The solution involves the idea of "toggling" one of the elements in the set. Given a subset \(S\subset \{1,...,n\}\), consider the subset \(S\oplus \{1\}\), where we add the element \(1\) to \(S\) if \(S\) does not already contain \(1\), and remove it otherwise. It is clear that if \(S\) has an even number of elements, then \(S\oplus \{1\}\) will have an odd number of elements and vice versa. We also easily verify that \((S\oplus \{1\})\oplus\{1\} = S\). Thus, toggling \(1\
Post a Comment
Read more

About the Blog

This blog is about various different topics in mathematics, physics and statistics. The topics can range from very simple and elementary to more complex and sophisticated. However, regardless of the topic's complexity, it is my intention to present the material in the simplest and most intuitive way possible. I hope this will help you learn and enjoy mathematics!
Post a Comment
Read more