I recently posted an exploratory piece on why programmers who are genuinely interested in improving their mathematical skills can quickly lose stamina or be deterred. My argument was essentially that they don’t focus enough on mastering the basic methods of proof before attempting to read research papers that assume such knowledge. Also, there are a number of confusing (but in the end helpful) idiosyncrasies in mathematical culture that are often unexplained. Together these can cause enough confusion to stymie even the most dedicated reader. I have certainly experienced it enough to call the feeling familiar.
Now I’m certainly not trying to assert that all programmers need to learn mathematics to improve their craft, nor that learning mathematics will be helpful to any given programmer. All I claim is that someone who wants to understand why theorems are true, or how to tweak mathematical work to suit their own needs, cannot succeed without a thorough understanding of how these results are developed in the first place. Function definitions and variable declarations may form the scaffolding of a C program while the heart of the program may only be contained in a few critical lines of code. In the same way, the heart of a proof is usually quite small and the rest is scaffolding. One surely cannot understand or tweak a program without understanding the scaffolding, and the same goes for mathematical proofs.
And so we begin this series focusing on methods of proof, and we begin in this post with the simplest such methods. I call them the “basic four,” and they are:
- Proof by direct implication
- Proof by contradiction
- Proof by contrapositive, and
- Proof by induction.
This post will focus on the first one, while introducing some basic notation we will use in the future posts. Mastering these proof techniques does take some practice, and it helps to have some basic mathematical content with which to practice on. We will choose the content of set theory because it’s the easiest field in terms of definitions, and its syntax is the most widely used in all but the most pure areas of mathematics. Part of the point of this primer is to spend time demystifying notation as well, so we will cover the material at a leisurely (for an experienced mathematician: aggravatingly slow) pace.
Recalling the Basic Definitions of Sets
Before one can begin to prove theorems about a mathematical object, one must have a thorough understanding of what the object is. In higher mathematics these objects can become prohibitively complicated and abstract, but for our purposes they are quite familiar.
A set is just a collection of things. Obviously there is a more mathematically rigorous formalization of what a set is, but for the purposes of learning to do proofs this is unnecessarily verbose and not constructive. For finite sets in particular and many kinds of infinite sets, absolutely nothing problematic can happen. Somehow, paradoxes only occur in really large sets. We will never need such monstrosities in our theoretical investigations or their applications. So in this post we’ll just work with finite sets and infinite sets of integers so as to better focus on the syntactical scaffolding of a proof.
There are many ways to define sets. One of the easiest is simply to list its elements:
$ \displaystyle X = \left \{ 1,4,9,16,25 \right \}$
The bracket notation simply means the stuff inside is a set. This particular set contains some square numbers. The order here is irrelevant, and sets are not allowed to have repetition. The programmer may think of this as a hash set, a Python set, or simply a list in which duplication is forbidden. The time it takes to apply operations to sets is of no concern for us, so any perspective is valid and multiple perspectives are encouraged for a deeper understanding. There are other ways to describe sets which were the inspiration for list comprehensions in many programming languages. For instance, one way to use the notation is
$ \displaystyle X = \left \{ n^2 : n = 1, \dots, 5 \right \}$
Speaking out loud as I write this, I would say, “Let X be the set of n-squared as n goes from 1 to 5.” This would be a slightly more compact way of writing the set above containing the first five squares. The colon there simply separates the expression to be evaluated at each step from the iteration part. The corresponding list comprehension in Python would be
[n*n for n in range(1,6)]
Cousin to the names from programming, this mathematical notation is called “set-builder notation.” Interestingly enough, mathematicians tend not to use strict set-builder notation. Except when the most stringent of formalities if required, they use words over these iterative expressions. This is part of how flexible mathematics allows us to define things. We might not even know an iterative method for computing numbers, so we could say something like:
$ \displaystyle \left \{ n : n \textup{ is prime } \right \}$
or
$ \displaystyle X = \left \{ n : n \textup{ is a square and } n \leq 1000 \right \}$
There is one bit of non-rigorousness already here! Can you spot it?
The trick is that we don’t have a definition of what it means to be a square. In particular, the observant reader would note that all positive numbers are “squares” if we allow for real numbers, and if we allow for complex numbers we get the negative numbers, too! This is a groan-inducing “gotcha,” but it expresses how important context is in mathematical proof. Depending on the context, this set could be finite or infinite. Now let’s say you encounter such a statement in a real work of mathematics, and there is no obvious clarification? You consider the two possible alternatives: either the set they’re defining is all numbers, or they actually mean a specific set of integers which are squares. The active reader must infer that the former is pointless (why describe all numbers in this stupid way), so the author must mean the latter. Of course, it is not always so obvious what the author intends to convey, but if all one has available is the printed word, this extra step of analyzing the author’s own constructions is necessary.
And so let’s formalize this just a little more.
$ \displaystyle X = \left \{ n : n \textup{ is the square of a positive integer and } n \leq 1000 \right \}$
If we don’t know how to express a condition, we can always just state it in words. The reader should practice at unpacking set-builder expressions in the same way that one can unpack triply-nested Python list comprehensions, but don’t let it become a hindrance to expressing an idea. It’s just that set-builder notation is often easier to parse than words in proofs which construct sets in nit-picky ways. It’s even common for someone presenting a proof to spend a good two minutes or more describing the contents of a tricky set-builder expression before continuing with a proof (the other day I was describing a technical construction to a colleague and we spent the better half of fifteen minutes interpreting and critiquing it).
One interesting bit of notation dictates membership of something inside a set. This is the “set membership” operator, denoted by the $ \in$ symbol (it comes from an odd way of writing a lower-case epsilon; for a short historical deviation, see this stackexchange question I asked on this topic). A programmer would probably feel most comfortable thinking of it as an expression evaluating to true or false, as in the Python code
7 in [1,3,4,5,8,9]
Which evaluates to False. The semantics are identical in mathematics, only the notation doubles as a test and as an assertion of membership. That is, we could translate the above Python expression into mathematical notation:
Let $ X = \left \{ 1,3,4,5,8,9 \right \}$. Then $ 7 \not{\in} X$.
The slash through the $ \in$ represents the test’s negation. We could have also said, “Then it is not the case that $ 7 \in X$.”
Or we could declare that $ X$ must satisfy the property that $ 7 \in X$ (assuming nothing else we know about $ X$ would stop that from happening):
Let $ X$ be any set such that $ 7 \in X$.
Here we are defining this object $ X$ to be as general as possible while still having 7 as a member (perhaps we want to prove something special about all sets which contain 7, although I can’t imagine what that might be).
The last definition we want to make before we start doing proofs is that of the notation for some common sets. The set of natural numbers is
$ \mathbb{N} = \left \{ 1, 2, 3, \dots \right \}$,
and the set of integers is likewise
$ \mathbb{Z} = \left \{ \dots, -2,-1,0,1,2, \dots \right \}$.
The blackboard-bold N stands for “natural” and the blackboard-bold Z stands for “Zahlen,” the German word for “numbers.” (Zero is not a natural number, and if you don’t like it you can go become a logician.)
Subsets, and Direct Implication
The first thing mathematicians want to do when they encounter a new mathematical object is to come up with useful ways to relate them to each other. One such way is by one set “containing” another. Of course, the sense that we mean “contain” requires specification. For on one hand, we could be saying that $ X$, a set, contains as a member another set $ Y$ (nothing stops sets from being elements of other sets). But this is not what we mean. Instead, we want to say that $ X$ contains every element that $ Y$ does. This calls for a new definition:
Definition: A set $ Y$ is a subset of a set $ X$ if every element of $ Y$ is also an element of $ X$. We denote the fact that $ Y$ is a subset of $ X$ with the “subset symbol” $ Y \subset X$.
We often say, “$ Y$ contains $ X$” to mean $ X \subset Y$, or alternatively that, “$ X$ is contained in $ Y$.”
Just as a quick example, the set $ \left \{ 5,8,12 \right \} \subset \left \{ 1, \dots, 20 \right \}$ because the latter contains 5, 8, and 12 as well as all of its other contents.
This new relationship gives us a bit to play with. For the question now becomes: how can we prove that one set is a subset of another set? Of course if they are finite then we can just check every single element by hand, but as programmers we know better than to waste our time with manual verification. The technique becomes more obvious when we start to play with some examples.
Let me define two sets with set-builder notation as follows:
$ \displaystyle X = \left \{ n^2 : n \in \mathbb{N} \right \}$
$ \displaystyle Y = \left \{ n^4 : n \in \mathbb{N} \right \}$
Take a moment to be sure you understand what the members of these sets are before continuing.
The salient question is, “Is $ Y \subset X$? And if so how can we prove it?” This is where direct implication comes in. What we’re asking is whether it’s true that no matter which element you pick from $ Y$, it will be a member of $ X$. In the most formal language, we are trying to prove the implication that for any number $ y$, if $ y \in Y$ then $ y \in X$.
This is a logical statement of the form $ p \to q$ (read “p implies q”). We will see three ways to prove a statement like this in our methods of proof series, but the most direct way to do it is called direct implication. In particular, we assume that $ p$ is true, and using only logical steps, reach the fact that $ q$ is true. That is, we go directly from “p” to “q.” This method of proof is so common that there is usually no mention of it in a proof before one applies it! It is, in a sense, the “obvious” way to go about proving something.
And so let’s prove the subset question above has an affirmative answer. To do this, we can start by fixing an arbitrary element $ y \in Y$. By “arbitrary” we just mean that whatever follows in the proof will be true if you replace $ y$ by any concrete element of $ Y$. Since there are infinitely many of them, this is really the only way we can proceed.
Now comes the tricky part. This is quite a simple problem, and the reader has probably already figured out the solution, but in general there is no way to proceed from here without creativity. Once one has figured out the scaffolding, one needs to make the “leap” from something which is obviously the “p” to something which is obviously the “q.” This can take the form of playing with the problem until an idea sparks, or it can result in applying a number of previously proved facts.
For this problem, we can achieve the leap by expanding the definitions of what it means to be in each of these sets, and apply a lick of algebra. We know that $ y \in Y$ is a fourth-power of a number. That is, it is $ y = n^4$ for some natural number $ n$. By our knowledge of algebra,
$ n^4 = n \cdot n \cdot n \cdot n = (n \cdot n)^2$
And so $ y$ is indeed the square of a number (it is the square of $ n^2$), and hence $ y \in X$. This concludes the proof that $ Y \subset X$.
Let’s do one more direct implication proof about subsets, and have it be a tad more abstract. That is, we won’t know anything concrete about the members of the sets we’re working with.
Proposition: Let $ X, Y, Z$ be arbitrary sets. If $ X \subset Y$ and $ Y \subset Z$, then $ X \subset Z$.
Before we continue, rewrite the thing we’re trying to prove as a $ p \to q$ type statement. Then we’ll start by assuming the “p” is true and try to conclude the “q.” In fact, this statement can be really expanded into one of the form
$ ((a \to b) \textup{ and } (b \to c)) \to (a \to c)$
In doing this we’re making a serious notational mess of a truly simple statement, bordering on an act of violence. On the other hand, it helps to be able to write things out in complete detail when one doesn’t understand one part of it. The active reader will determine exactly what the propositions $ a, b, c$ represent in the above implication, and this will make the following proof routine to follow.
Another important point to make is that if the proposition is still unclear at this point (or it is unclear how to proceed), then the best line of attack is to write down lots and lots of examples. This is the kind of thing that almost always goes unsaid in any mathematical proof, because one simply assumes that if the reader does not understand what is being asked then they will work with examples until they understand.
For instance, we can come up with a very simple example with finite sets:
$ X = \left \{ 1, 5, 9 \right \}$
$ Y = \left \{ 1, 2, 5, 7, 9 \right \}$
$ Z = \left \{ 1,2,3,4,5,6,7,8,9 \right \}$
In this special case the statement of the theorem is obvious: the conditions hold as expected, and the result holds as well: $ X \subset Z$. We can also do it with some infinite sets:
$ X = \left \{ 4,8,12,16, \dots \right \}$
$ Y = \left \{ 2, 4, 6, 8, 10, \dots \right \}$
$ Z = \left \{ 1, 2, 3, 4, 5, \dots \right \}$
Indeed, there is a very simple picture proof hiding under the surface here! It is just:
From this picture it should be obvious: if $ X$ is contained in $ Y$ and $ Y$ contained in $ Z$ then $ X$ is obviously contained in $ Z$. With all of this intuitive knowledge under our belt, we can proceed to the formal proof of the statement.
Proof. Suppose that $ x$ is an arbitrary element of $ X$. We want to prove that $ x \in Z$. Applying the first fact that $ X \subset Y$, we know that every element of $ X$ is an element of $ Y$, so $ x \in Y$. Further, by the fact that $ Y \subset Z$, it follows that $ x \in Z$, as desired. $ \square$
This was a bit more formal and a bit more condensed than our last proof, but the syntactical structure was the same. We wanted to prove a $ p \to q$ fact, and we started by assuming the “p” part and deriving the “q” part. All in a day’s work!
Here are some more examples of statements that you can prove by direct implication:
- Let $ A, B, C$ be sets. Show that if $ A \subset B$ and $ B \subset C$ and $ C \subset A$, then $ A = B = C$ (where by equality of sets we mean they have precisely the same elements; as a side note, can you define equality in terms of set containment?).
- The union of two sets $ A, B$ is the set $ A \cup B$ defined by $ \left \{ x : x \in A \textup{ or } x \in B \right \}$. Prove $ A \subset A \cup B$.
- The intersection of two sets $ A, B$ is the set $ A \cap B$ defined by $ \left \{ x : x \in A \textup{ and } x \in B \right \}$. Prove $ A \cap B \subset A$.
- Let $ A,B,C$ be sets, and suppose that $ A \subset B$. Prove that $ A \cap C \subset B \cap C$ and $ A \cup C \subset B \cup C$.
Here are two more exercises from number theory that might require a bit more inspiration:
- Prove that every odd integer is a difference of two square integers.
- Prove that if $ a,b$ are integers then $ a^2 + b^2 \geq 2ab$.
As usual, the first step should be writing down examples, and then attempting a proof.
Proofs by direct implication are very often straightforward, but as a reader we must be cognizant of when it’s being applied. As is often the case in mathematics, the precise method of proof goes unstated except in pedagogy.
Just to get a taste of where else proof by direct implication can show up, we will prove something about functions (in a programming language).
Definition: Let $ f$ be a function in a programming language. We call $ f$ injective if different inputs to $ f$ produce different outputs (and every input produces some output). For the sake of this post, we assume the method of comparing things for equality is fixed across all objects in the language (say, via Java’s object comparison method equals(), or Python’s overloadable == operator).
Proposition: If $ f, g$ are injective functions which can be composed (all outputs of $ f$ are valid inputs to $ g$), then the composition $ gf$ defined by $ gf(x) = g(f(x))$ is injective.
Proof. Let $ x,y$ be two different inputs to $ f$. They are also inputs to $ gf$. Then the values $ f(x), f(y)$ are different, and they are also inputs to $ g$. So $ g(f(x))$ and $ g(f(y))$ are different, proving $ gf$ is injective. $ \square$
Next Time, and a Reference
Next time we’ll investigate the next simplest way to prove statements of the form $ p \to q$: the proof by contrapositive implication. This will involve a slight digression into the general meaning of $ p \to q$. After that we’ll cover contradiction, and then proofs by induction.
Of course, this series is woefully incomplete by the nature of blogs. For those who are interested in proof techniques for the sake of transitioning to advanced mathematics, I recommend Paul Halmos’s Naive Set Theory. For those interested in getting a better idea of the beautiful nature of proofs (that is, mathematics done for the sake of finding clever and beautiful arguments) and want a more casual read, I recommend Paul Lockhart’s Measurement. Both are valuable and well-written texts.
Until next time!
One of the things that seems to be always unstated and I misinterpreted for a long time is the formal meaning of ellipsis. In N = {1, 2, 3, …}, the question is whether +infinity is considered to belong to this set of not. I thought yes, but have learned no {Thanks to Colin Wright on HN}. I wonder if this is obvious somehow or it is an tacit assumption.
While this may be outside the scope of this article, a question I have is how far one needs to go in showing the steps of the proof? In other words, when do the individual steps of the proof become obvious or accepted truths so as to make the supplied proof to be considered to be complete? In the particular example, it is implicitly assumed that if n is a natural number, then so is n^2, or else the stated proof is not complete.
A somewhat more involved question. Aren’t the four proof techniques mentioned ultimately the same? For example, if given a proof by contradiction, could one not just create a direct implication proof via simple transformations on the proof by contradiction? Unless I am wrong already, I think this does also apply to proofs by induction if one could accept induction as a proof method at all (and not an axiom by itself).
The ellipsis is is actually the subject of many jokes in mathematics, since it is supposed to mean “the pattern which obviously follows.” It’s not always clear. The important thing to know about infinity is that it’s not actually a number in standard number sets. In fact, it’s a bit involved to come up with a place where infinity makes sense, and in most instances I can think of (outside of large cardinal logic) it will break things you want to keep, like the field axioms for arithmetic. In particular on this blog, I doubt we will ever need to formally talk about what it means for infinity to be an object, and we will only use infinity as a notation for something like “unboundedness” in saying the limit goes to infinity. (the formal definition of what it means for
does not involve infinity!)
If you want to go deeper you can quite easily prove statements like n^2 being natural whenever n is natural. For the sake of learning proof techniques it’s not necessary, but if you’re studying the fundamentals of logic then you’d start from an axiomatic system in which you assume, for instance, that 1 and 0 are natural numbers and that 0+1 = 1 and 1+1 is natural, and then you can prove that multiplication works via iterated addition. Of course, it requires an inductive argument to prove it in general 🙂
You write down as much as you need to for a logical step to become obvious. It is obvious to me that the square of a natural number is natural, and once you spend some time with sets it should become completely natural that set containment is transitive (as we proved here). The more mathematics you do, the more comfortable you become with seeing proofs before you write them down, and the easier it is to say, “the statement is trivial, because I can see how the proof would go and if I needed to I could write down all the details.” This is part of the reason why advanced mathematics can be hard to read, because mathematicians are very good at filling in details when they need to. Authors capitalize on this to make their prose more concise. As a proof writer, you have to write to your intended audience; as a reader, you have to fill in the details until things become obvious.
You’re right that direct implication, contrapositive, and contradiction are the same, but it is certainly clear when approaching a problem that some methods are more natural to use than others. Consider the statement: “It is impossible to do X.” The most natural way to go about proving this is by contradiction, for otherwise you have no existing object to work with. There are of course proofs of impossibility that don’t start by contradiction (a famous one is the proof of the insolubility of the quintic), but these usually take quite a bit more work and machinery. Similarly, if you see a statement “If x doesn’t have property P then y doesn’t have property Q,” it can be easier syntactically to do contrapositive, because then you work with a property that y does have instead of one that it doesn’t. The most important part is recognizing which technique is being used so you don’t get lost before the proof even starts.
If I read you correctly, you are saying that lim(x->a) f(x) = infinity is just a semantic shortcut to saying the LHS is unbounded and nothing else (ignoring for now the whole discussion of Cantor’s work and beyond). Is there some book that defines these things formally -> ellipsis, infinity, induction, etc. in a strictly non-cyclic fashion?
I was a bit unclear how I would formally prove n squared to be a natural number (even though it is obvious to me too) but your comment supplies the answer — start from Peano’s axioms. The formal proof too is obvious now.
What I gather from your comment is that to figure which step in a stated proof is considered as obvious and which needs to be stated explicitly requires working with real mathematicians due to the culture aspect to it. (It’s like trying to figure what SDK’s and libraries are available for which tasks merely by reading a book on programming language.)
Any real analysis text will define limits in the way I described. You are unlikely to see infinity referred to as an element of a set unless you’re reading about large cardinals or non-Euclidean geometries (and even then, the point at “infinity” is usually called an ideal point instead).
+infinity is not a “Number” therefore it cannot be in a set of “Numbers”
This all depends on how you define a number 🙂
Indeed, as Jeremy said, it is a matter of definitions. I cannot imagine the “type” of +infinity to be anything else but a number so that expressions like “infinity + 1”, “1^infinity” etc. make sense. I know sometimes infinity is referred to as “Not a number” or “undefined” but I think it is not appropriate terminology since again, “infinity + 1” would make no sense then.
One may reason that +infinity does not belong to N since it cannot be ascertained to be a natural number. Yet, I have no hard time imagining an unbounded natural number.
I can point to lots of places in which infinity has different types, but usually the idea that it represents a number (again, depending on how you define number) is not well-defined. For instance, you can’t just “add” infinity in any reasonable way to a ring of real numbers. But without going into how rings work, I can’t explain it too much more.
“… how far one needs to go in showing the steps of the proof?”
I think this is a very important question that is often overlooked
until far too late in math education. I know it certainly tripped me
up as a student. For me, enlightenment was achieved in a course on
non-Euclidean geometery based on
http://www.amazon.com/Euclidean-Non-Euclidean-Geometries-Development-History/dp/0716799480
For centuries there were attempts to prove the 5th postulate. The
(in)correctness of these proofs always depended on subtle steps that
would somehow sneak in unstated assumptions. The upshot is that to be
completely formal, each step in a proof can only be the direct
application of stated axioms or previous formally proven
theorems. Most of the time “proof” means informal proof, though, and
how far one needs to go spelling out the details is a matter of taste
and judgement. So you tend to treat things like “the square of an
integer is itself an integer” as a given because the proof is assumed
to be previously accepted by the reader.
For the specific example of N = {1, 2, 3, …}, below is a (proposed) formal definition of (the first) infinity and also N itself, without using ellipsis.
N = {n: [n = 1] or [(n-1) belongs to N]} // No ellipsis anymore.
Now we formally define infinity as size of N, which I believe would be correct definition of (the first) infinity.
Can someone now prove that infinity itself does not belong to N? If something above is not correct, like the definition of this infinity or N, need to supply correct definitions instead and then show that infinity does not belong to N.
Below is a proof that shows infinity, as defined above, does belong to this set:
Let Ni = {1, 2, 3, … i}. Clearly i belongs to Ni. Also size(Ni) = i, which implies size(Ni) belongs to Ni.
Now apply the limit i -> infinity. Under this limit, Ni = N (unless someone could formally define ellipsis that leads to Ni != N.) And we still have size(Ni) belong to Ni, which means infinity belongs to N.
Limits, however, are notoriously counterintuitive without appropriate hypotheses. I think the right way to think about it is in terms of bijections. Say for instance, that
is the set of all cardinalities of finite sets. Here the cardinality of a set 
being 
is determined by the existence of a bijective function 
. Then this automatically precludes infinity from being a natural number, since there is no bijection from a finite set to an infinite set.
Given any finite set X, there exists a bijection X -> {1, 2, …, m} where m is a finite number. Without loss of generality, we may define N as the set of all cardinalities of such sets {1, 2, …, m} where m is finite number. I follow that you may then say that infinity does not belong to N. Can you however then prove that the cardinality of N itself is not finite?
Certainly, but I would prefer to do it by contradiction (which I haven’t covered yet on this blog). Suppose to the contrary that the cardinality of
were finite. Let 
be a bijection enforcing that hypothesis, and let x be the maximal value of 
. Since 
is a bijection there is a unique inverse and the inverse is also a bijection, so x is uniquely determined in this way. But by the definition of the natural numbers, there is an element of 
which corresponds to x+1 (simply take the set of numbers from 1 to x+1; this is a finite set). But this contradicts the fact that x was maximal: f was a bijection and in particular a surjection, so it assumes all values of 
including x+1 > x.
I’m sure there are some logical holes that could be expanded upon here (esp about function inverses), but the idea should be pretty clear.
Thanks. While I do not fully understand this proof, this gives me enough pointers to read more. Specifically, I need to figure what is meant by maximal value of f-inverse.
If you know how to define the inverse of a function
, then the maximal value of the inverse 
is just the maximal element of the set 
(here we are assuming we can compare elements of the sets involved; for our purposes they are sets of natural numbers, so that’s okay). If you are comfortable with the idea of the maximal value of a function 
as being the maximal element of the set 
, then this is the same thing just replacing 
by 
.
But then by the same token, can I not prove that infinity is a member of N:
Suppose infinity does not belong to N. Then there is a maximal number belonging to N. Then there is that plus one.
Wait, what? There is no maximal natural number. Adding the stipulation that infinity is not a natural number doesn’t change that. So the claim “there is a maximal number belonging to N” is just plain false.
>> So the claim “there is a maximal number belonging to N” is just plain false.
That’s actually what I was trying to say. Nevertheless, I need to do more reading on the subject to grasp it better. Am currently stuck at how can N be a set of all finite natural numbers, have cardinality of infinity itself while not having infinity belong to the set. Below is a quote from Wikipedia article “Cardinal number” in relation to ordinal numbers:
For finite sets and sequences it is easy to see that these two notions coincide, since for every number describing a position in a sequence we can construct a set which has exactly the right size, e.g. 3 describes the position of ‘c’ in the sequence , and we can construct the set {a,b,c} which has 3 elements. However when dealing with infinite sets it is essential to distinguish between the two — the two notions are in fact different for infinite sets.
This gives me the important clues. Thanks so much for leading me to this.
This is referring not to the question of whether infinity is a natural number, but to whether it is possible to have more than one kind of infinity. That is, have two sets both of infinite size, but somehow have them not have equal size to each other. I think your question is more basic than that, so just don’t get lost in all the infinite cardinal stuff while you’re working on your question.
Just a typo: either the set their defining is all numbers
their should be they’re.
(feel free to keep or delete this comment)
Small typo: Your definition of Z is … -2, -1, 0, 1, 2. (missing the ending ellipses).
Just as a side note, your python example is off by one:
In [1]: range(5)
Out[1]: [0, 1, 2, 3, 4]
where it should be
In [3]: [n*n for n in range(1,6)]
Out[3]: [1, 4, 9, 16, 25]
or
In [4]: [(n+1)**2 for n in range(5)]
Out[4]: [1, 4, 9, 16, 25]
I know, for the sake of argument your example is right, but these small things just annoy me 🙂
Have not read this yet but I’m so pleased about this series I have to comment right now.
I’m working through a 450 page discrete math textbook on my own as a self-taught programmer who left maths behind in high school. Your last post was great. One effect of saying what you did about math self-study is to encourage people like me. Sometimes when struggling with a concept on my own I can’t help but think “am I cut out for this”. Reading someone simply stating “maths is hard and math self-study is very hard” really spurs me on.
Thanks for the article. I want to bring up the aspect of vacuous statements, as I find them a bit tricky to understand.
In the case of proofs with sets that have no definition for set membership, this translates to the possibility of working with an empty set. My intuition tells me that such proofs should be split into two cases, which consider the possibilities of the sets being empty/nonempty. However, I find the idea of making claims about empty sets being subsets of other sets a bit unnatural. Is my intuition correct?
So, almost every statement is true about empty sets. So if you want to know if the empty set is a subset of another set, the answer is always “yes.” It is unnatural, but most working mathematicians ignore these trivial cases. They’re simply not interesting.
Hi, Teacher j2kun, please correct my tries on the given practices:
1.
a in B and b in C, implies a in C.
a in C and c in A implies C, A are the same set.(is there a logic jump here? because it feel natural to just say it this way)
b in C and c in A implies b in A.
b in A and a in B implies A, B are the same set.
A, C are the same set and A, B are the same set.
A, B, C are the same set.
2.
x in A U B, by definition, x in A or x in B or x in both A and B.
a in A while x in A(whatever x from A U B are in A) implies x = a.
A therefore is a subset of A U B.
Looks good to me. There is no logical jump between saying
and 
implies 
. One can take this as the definition of set-equality, and it is logically equivalent to saying the two sets contain the same elements.
In the second one, I think you meant: a in A implies a in A or a in B, which is the definition of a in A union B?
Thanks for this series. It nicely supplements my current introductory course to Discrete Math, which is not always so intuitive to a novice like me. One quibble. You really ought to mention null sets. Otherwise, it becomes impossible to prove the exercise: “Let A,B,C be sets, and suppose that A \subset B. Prove that A \cap C \subset B \cap C” (dunno if the cut-n-paste will render correctly the comments, but you get the idea).
I feel quite strongly that the fact that “the null set is a subset of any set” is an element of that tricky set X = {x | x is something not-at-all-obvious to a beginner}.
Yes, I didn’t quite find a nice place to talk about vacuous implications. I think I may do another post in this series on that topic alone, if only to discuss why people rarely care about those kinds of cases.
Loved this article, thanks to you I now know that doubling an integer produces an even number therefore 2k+1 always produces an odd number and have also re-learned how to properly expand (a+b)^2 which I learned many years ago.
I have never been a smart man, but shouldn’t your statement, “We often say, “Y contains X” to mean X \subset Y, or alternatively that, “X is contained in Y.”” be written just the opposite: “We often say, “X contains Y” to mean Y \subset X, or alternatively that, “Y is contained in X.”” ?
Nope. The
symbol means the thing on the left of the symbol is contained in the thing on the right of the symbol.
Yello, j2kun. I am a person who loves maths, and would love to understand advanced mathematics and such. But I have no idea where to start, with which field, which book? As such, could you please tell me or at least give me a few pointers as how and where you can start learning advanced mathematics?
What is advanced to you? If you have not mastered linear algebra I would say start there. “Linear Algebra Done Right” will give you a solid foundation for the formalisms and proofs and theory, and these videos will give you strong intuition: https://www.youtube.com/playlist?list=PLZHQObOWTQDPD3MizzM2xVFitgF8hE_ab
Ah thanks dude :thumbsup:. I wouldn’t say that I’ve mastered linear algebra, having merely read a single book about it. So that will probably help quite a bit. Say, after that series, what would recommend doing next?
Depends on your interests. After linear algebra you can do Fourier analysis if you like applied math, algebraic geometry if you like pure math, computer science and machine learning if you like algorithms…