1The language of mathematics and prompting

1.1 The art of prompting

As of August 2024, there is a multitude of chatbots available on the internet. Some of them, like ChatGPT, Claude and Gemini (and Llama 3.1, Mistral, ... the list goes on)
have quite impressive reasoning capabilities. These models are now multimodal i.e., they even accept non-textual input, such as images, sound and video. In principle you can upload a picture of a math exercise and the chatbot will provide a solution. Well, that is, on a good day and for a not too difficult exercise.
The use of chatbots is encouraged throughout this course. In fact, they are even allowed during the exam. It is my hope that you will learn mathematics on a deeper level by communicating with the machine using carefully designed prompts - see the OpenAI guide on prompt engineering.
In some places in the notes, you may see quite specific prompts, such as
💬

Always answer in the context described below.
Context: I am taking a first semester college level course in introductory mathematics and optimization. Emphasis is on precision and small proofs in mathematics. Please give some conrete examples with mathematics involved. 

- Tell me what a good and precise prompt is.
- Show me two examples of good prompts.
- What is a good prompt if I want to know about code written in Sage or python?
- What is a good prompt if I want to know how to enter some specific mathematics in LaTeX?

| ChatGPT | Claude | Copilot | Gemini | HuggingChat | Mistral |
A click on a chatbot link copies the prompt to the clipboard and takes you to the chatbot, where you can paste the prompt and get feedback.
The prompt may also be hidden in a button as below.
LLM
💬

Please solve the equation $x^2 - x - 1 = 0$. Guide me through the steps. Make sure that the underlying logic in your arguments is correct.

| ChatGPT | Claude | Copilot | Gemini | HuggingChat | Mistral |
There is a lot of wisdom baked into those weights! In this first chapter I will show a lot of prompts. In the following chapters less so. Here you are expected to prompt the chatbots on your own.
Be careful! Prompting without any knowledge of the mathematics can be disastrous. I have seen exams written by generative AI spanning many pages with little or no relevant mathematical content. This is known as GIGO or garbage in garbage out. Good prompting comes from an understanding of the mathematics and often resembles concise and beautifully written instructions.
Study the OpenAI guide on prompt engineering.
Then come up with prompts that make a chatbot act like a mathematics tutor for you. Here is a small example that you may extend.
💬

Please act like a friendly tutor and teach me about the derivatives of simple functions. Test my understanding after each concept you explain.

| ChatGPT | Claude | Copilot | Gemini | HuggingChat | Mistral |
Start your journey using the prompt below.
💬

I am doing weekly exercises in mathematics at the college level. Please suggest a very simple template in
LaTeX for hand in of these exercises. Also, show me how to typeset an equation in LaTeX.

There seems to be a web interface to LaTeX called Overleaf. Please tell me how to access this so that I can
enter a weekly exercise.

| ChatGPT | Claude | Copilot | Gemini | HuggingChat | Mistral |
Come up with your own prompt for a question related to software.
Below I ask for feedback from the chatbot on some dubious chunk of mathematics.
💬

Please give feedback on the mathematics contained in the $\LaTeX$ below in triple quotes. Emphasize logic and precision.
"""
$$
x^2 = 1 \implies x = 1
$$
From this it follows that $1 + 1 = 3$.
"""

| ChatGPT | Claude | Copilot | Gemini | HuggingChat | Mistral |
Insert your own mathematics in notation and ask for feedback in a prompt.

1.2 Black box warnings

Modern mathematics is perhaps not like anything you have encountered so far. It calls for a lot of focus and precision, especially when writing down solutions to problems. It is a bit like programming a computer. There is no room for imprecision and half-baked sentences.
This course amounts to ECTS or approximately hours. Suppose that you spend a week studying for the exam, say hours. Lectures, exercise classes, and MatLab amount to hours hours. This leaves around hours for your own study and immersion. Put in other terms, you are supposed to work around hours per week outside classes for this course. With classes, each week calls for hours of work. There is a very close relationship between the amount of hours you log each week and your result at the exam. To state the obvious: numbers don't lie. If you put in the time, you will almost certainly do well. Try to allocate time for IMO in your weekly schedule and please (ab)use all the help that is provided.
💬

I am taking a first semester college level mathematics course spanning 14 weeks and 10 ECTS. One ECTS
amounts to 28 hours. The teaching activities every week amount to 4 hours of lectures,
2 hours of exercise sessions and 3 hours of study cafe. I expect that final exam will take 40 hours
of the 10 ECTS. Please schedule a weekly study plan for me along with a plan for the final exam.

| ChatGPT | Claude | Copilot | Gemini | HuggingChat | Mistral |

1.3 Computer algebra (and python)

Computers are exceptionally fun, but be careful! Nothing really beats a clear thinking human mind. To wit, I asked WolframAlpha to solve a certain optimization problem and it came up with the answer
Prompt a chatbot with
💬

What is 
$$
-\sqrt{\frac{1}{2} (1 - \sqrt{2} + \sqrt{3 - 2\sqrt{2}})}
$$

| ChatGPT | Claude | Copilot | Gemini | HuggingChat | Mistral |
and explain why the output from WolframAlpha is weird. Use prompting to make it explain the mathematics input notation.
Finally use your own mental powers (and feedback from the chatbot) to explain what the proper output should have been.
We will use the computer algebra system Sage in exploring and experimenting with mathematics. This means that you will have to write small commands and code snippets.
Sage is built on top of the very wide spread language python and you can in fact enter Python code One may also enter code in several other languages in the Sage input windows in the interactive notes. First adjust the prompt below according to your needs and get feedback from an LLM.
💬

I am taking a mathematics course that uses the computer algebra system Sage.
The course uses the browser, where I can enter and run small snippets of code in Sage and python.
I have no/some/extensive prior programming experience.
Give me a brief introduction to Sage and explain how it relates to python.
Finish your reply with a small exercise I can do. 
If no/some/extensive is present above in this prompt, remark this and only reply with
Please select your programming experience.

| ChatGPT | Claude | Copilot | Gemini | HuggingChat | Mistral |
Below is an example of a basic graphics command in Sage. Push the Compute button to evaluate.
You can install Sage on your own computer following the instructions on https://www.sagemath.org/.
Did you notice that you can edit and enter new commands in the Sage window? Do the following problems using Sage based on the Sage guided tour.
  1. Consider . Plot the graph of from to . Computing does not make sense. Do you see a way of assigning a natural value to using the graph?
  2. Find an approximate solution with four decimals to the equation .
    This is an example of an equation, that can only be solved numerically. Try first plotting the graph of from to . Then use a suitable function from the Sage guide.
  3. Compute with decimals.
LLM
💬

Give me the sage code to compute pi with 100 decimals. I want a one line command.

| ChatGPT | Claude | Copilot | Gemini | HuggingChat | Mistral |
Compute the sum
What is the elegant answer? Explain!
Bonus question
Generalize your answer/method to computing the sum
for .
We need a precise setup for communicating mathematics. This involves the introduction of propositional logic, predicates and sets. Let me emphasize, that this is an introductory course and not a rigorous introduction to mathematics. As such it is an organic approach, where I hope that you will return and fill out the gaps instead of getting overwhelmed by formal details already from the beginning.
However, the underlying goal is to show that mathematical precision and proofs are similar to constructing correct computer programs. In fact, this whole first chapter may be viewed as the beginning of a computer program, where we state the exact definitions for use in the following chapters. We begin by introducing sets and numbers.

1.4 Numbers

A set is a collection of (mathematical) objects or elements. When defining a set we use the symbols and to denote the beginning and end of its definition. For example, is the set of characters in my first name and are the digits in the postal code for Aarhus C. The ordering in the listing of the elements is unimportant so that
are identical sets. If is a set, we will use the notation to denote that is an element in . For example, e.
Later, we will introduce much more detail about sets. For now, we just need the basic notation for defining them.
Our fundamental mathematical objects in this course are numbers and we introduce them right away.

1.4.1 The natural numbers and the integers

The set of natural numbers is
The set of integers is
These are infinite sets, since they contain infinitely many elements as indicated by the dots
It makes sense to add and multiply two integers and . We will denote their addition or sum as and their multiplication or product as . A fundamental fact is that addition and multiplication are commutative i.e., and .
Please notice right away that expressions like and are complete nonsense for three integers and . We only know how to add and multiply two integers, not three. A wonderful fact comes to our rescue:
You get the same result no matter if you start adding (multiplying) and or and and then adding (multiplying) or . So we may write and as a placeholder for one of the two ways of computing this expression in (1.3) .
As you can see we use the symbol for addition, but no symbol for multiplication. This is the convention in (clean) mathematics as opposed to the coming from computer algebra (except perhaps in Mathematica or Wolfram language, where space is allowed for multiplication). However, when one of the factors is an actual number, we will use , so that for example times is written as and times is written .

1.4.2 The rational numbers

The natural numbers and the integers are well defined by their representations in (1.1) and (1.2) .
A rational number consists of a numerator and a denominator .
If and . Then and are considered equal i.e.,
if and only if .
So there are many different ways of representing a rational number, such as
Here
In fact, a fraction stays the same when its numerator and denominator are multiplied by the same natural number.
I will assume that you know how to add and multiply fractions, and that you do not make mistakes like
In fact, if you temporarily forgot how to add fractions, you can use the wisdom in Definition 1.7 . You can replace by and by and then add the numerators as in
The computation above says that it is straightforward to add pizza slices of the same size (one sixth), but that you need to think a bit when adding one half pizza slice and two pizza slices of size one third. In general,
Click on the right equalities below. Do not use Sage (or any computer)!

1.4.3 The real numbers

A real number is defined by
where and is an infinite sequence of integers (digits) in .
Informally (1.4) represents the real number
given by an infinite set of digits as opposed to a rational number, which is given finitely by an integer (numerator) and a natural number (denominator). The format in (1.4) is the usual (floating point) output from your pocket calculator or computer algebra system. For example,
The decimal expansion of above looks chaotic, but it eventually repeats itself after digits. In fact the decimal expansion of every rational number is periodic i.e., it repeats itself from a certain point.
In the definition (1.4) of a real number, we are forced to make identifications as in the definition of a rational number. I will not go into details here, but just notice that the identification
is forced upon us: if
Then
Therefore we must have .
A real number that is not rational is called irrational. There are many more irrational numbers than rational ones. Famous ones are and . The irrational number is a root in the polynomial with integer coefficients (it is an algebraic number). The numbers and are not even algebraic (they are transcendental).
Explore using prompting the history of numbers in mathematics. Also make a chatbot explain why a rational number must have a periodic decimal expansion.

1.4.4 Arithmetic rules for numbers

Suppose that is one of the sets or . Then for numbers all in we have
If is one of or , then and for every ,
  1. for some number .
Finally if is or and is not ,then
  1. for some number .
The number above is called the inverse of and is usually denoted . The number above is called the negative of and is usually denoted . We will also the symbol (minus) defined as an operation on two numbers as
Argue precisely that for using Proposition 1.12 .
The long list of arithmetic rules above may seem complicated at first, but they are just a formal version of what you already know, such as for example, , if and for . Beware however, that the precision in Proposition 1.12 is necessary when programming a computer.
The rules (ⅳ) and (ⅴ) are called the associative laws for addition and multiplication respectively. The rule (ⅵ) is called the distributive law. It connects multiplication with addition.
We know that zero times any number is zero. Deduce this from the rules in Proposition 1.12 starting with .
Verify that (ⅵ) is true for some specific non-zero numbers. Also convince yourself that WolframAlpha actually accepts space (between numbers and variables) as multiplication.
Suppose that and . It seems that computing involves two multiplications and one addition. Multiplications are expensive operations on a computer. Is there a way of computing with only one multiplication and one addition?
Suppose that . Use the distributive law to show that
We now move on to the (formal) language involved in reasoning about mathematics in general.

1.5 Propositional logic

A proposition is a (mathematical) statement that is true () or false (). This could be a boolean expression in a computer program, like .
Sage
Later we will see propositions with variables in them like . These are called predicates.
Propositions can be combined into new (compound) propositions. Take for example the propositions
Then ( and ) is a perfectly good new proposition reading it rains and it is cloudy. The same goes for (if then ), which reads if it rains then it is cloudy. The proposition (if then ) reads if it is cloudy then it rains. This proposition is (clearly) false.
We need some notation to describe these compound propositions:
The compound propositions are either true() or false () depending on and . The dependencies are displayed in the truth tables below.
The tables for the compound propositions and also are not too hard to grasp. The table for raises a few more questions. Why is true? I will not go into this at this point (see Example 1.31 ), but just point out that there are many explanations available online and, perhaps more importantly, refer you to Exercise 1.19 .
Suppose that we are presented with four cards
with a (natural) number on the front and the color blue or red on the back. In (1.5) , the first and third cards are shown with their fronts facing up and the second and fourth cards are shown with their backs facing up.
A claim (proposition) is made that if a card has an even number on the front, then it must have the color blue on the back.
Your task is to verify this for the cards above. Of course you can do this by turning all four cards, but is there a way of checking this by turning less than four cards?
What if we add the claim, that if a card has the color blue on the back, then it must have an even number on the front?
Find two propositions and so that the claim reads .
A prosecutor says to the defendant: "If you committed this crime you did not act alone". Explain why the defendant should not answer "no, that is not true" here.
Explain why Python/Sage thinks that the value Thanks to Gerth Brodal for pointing this out to me of
is False! Notice that you are dividing one by zero in the last "integer" above.

1.5.1 Propositional logic as a formal language

The entities and above may have real world interpretations like it rains or it is cloudy, but we will view them as variables that can be assigned the values true or false. Independent of this assignment we define a proposition as follows.
A proposition in the variables is an expression involving the symbols that can be generated using the rules below
  1. The variables are (atomic) propositions.
  2. If is a proposition, then is a proposition.
  3. If and are propositions, then , and are propositions.
The expression is a proposition. Let us see how it is generated using the rules in Definition 1.22 .
  1. First, is a proposition using (ⅰ) .
  2. Then is a proposition by using (ⅱ) with , since we know by (1) that is a proposition.
  3. Since is a proposition by (ⅰ) , it follows that is a proposition using (ⅲ) with and , since we know by (2) that is a proposition.
  4. Finally, since is a proposition by (ⅰ) it follows by (ⅲ) with and that
    is a proposition, since we know by (3) that is a proposition.
According the generating rules in Definition 1.22 , which of the following expressions are propositions in the variables .

1.5.2 Truth tables and equivalent propositions

Given a proposition, it makes sense to substitute values ( or ) for the variables and evaluate it using the rules in Definition 1.18 , since the parentheses leave no ambiguity as to how the evaluation must take place. For a given proposition in the variables , there are ways of assignments to the set of variables. Each of these assignments results in the value true or false after evaluation. This is conveniently recorded in the truth table of the proposition as illustrated in the example below, where so that the truth table has rows.
The truth tables corresponding to the propositions and are given below.
For example, if and , then
and
The two propositions in Example 1.25 have identical truth tables. In general, if two propositions and have identical truth tables we call them equivalent and write
In Example 1.25 we saw that
The definition below is very important too keep in mind.
The notation is used frequently. It means that both and are true i.e.,

1.5.3 Using Sage to compute truth tables

Sage may be used to compute truth tables for propositions using the propositional calculus in Sage. Below is an example. Be sure to check how to enter and .
Construct by hand the truth table for the proposition .
Convince yourself either using Sage or by writing out truth tables that

1.5.4 Variables, predicates and quantification

A predicate is a proposition depending on one or more variables.
Variables are fundamental in computer programs. In the predicate , appears as a variable. Depending on what you substitute for , the resulting proposition could be true or false or even meaningless. As an example, the latter case appears if is replaced by the character 'a'. This is what computer scientists call a type error. You cannot compare a character with a digit.
If , then is true, whereas is false.
is a predicate in two variables and . Here is true, whereas is false.

For every and there exists

Suppose that we have a predicate , such that is a proposition for , where is some set. Then we define the proposition
to be true if there exists , such that is true. We let
be the proposition defined by
In other words, (1.7) says that is true for every , since there does not exist making false. Le me be absolutely clear. To show that is false, it is enough to find just a single so that is false.
Here is a statement about real numbers
This statement reads: no matter which real number you pick, if , then . We definitely want this to be true. Being true means that (1.8) must hold for all numbers , also , which reads
The above statement is an example of a false implies true statement, which we want to be true.
In general terms, in proving the statement that holds for every in some set , we are really only interested in for which is true, since is our assumption. We still need to be true for for which is false. This is assured by the truth table for , since and are both true.
The following is an excerpt from the infamous Beredskabsprøve Datalogi.
Which of the following are true?

1.5.5 Proofs and inference rules

A proof begins with an assumption and proceeds with a sequence of logical steps called inference rules leading to a conclusion .
You have been taught how to solve equations in steps leading to a solution. Each step turns out to be an inference rule and the conclusion is the solution. Let us see how for the simple equation . Formally we want to prove
The first inference rule is i.e., we are allowed to add the same number to both sides of an equality. This implies
To be very precise we now use Proposition 1.12 (ⅳ) as an inference rule i.e.,
Then we use Proposition 1.12 (ⅷ) to conclude
and then finally, we get by Proposition 1.12 (ⅶ) that
So to solve the equation , we are actually using four (!) inference rules along the way.

1.5.6 The use of implication () and bi-implication ()

As you have seen, and are applied to link propositions in a logical argument. For example,
However, for we cannot link the two propositions by , simply because is false (for ).
Prove that
for every (see Definition 1.69 with for the precise definition of ). Write out every inference rule!
You need to be very precise here. What does mean precisely if ? In Definition 1.69 you will see that it means that . From this you need to deduce
for every
Try out
💬

Is 
$$
x \geq 0 \iff x^2 \geq 0
$$
a true statement? Give me 3 carefully crafted exercises
training me in distuishing $\implies$ and $\iff$.
Only use basic mathematics involving
numbers and arithmetic operations.
After each exercise stop, ask for the
answer and give valueable feedback and guidance.

| ChatGPT | Claude | Copilot | Gemini | HuggingChat | Mistral |
and go through the exercises given to you.

1.5.7 More on mathematical proofs

Most professional mathematicians rarely think about the precise definition of a proof and would probably feel uncomfortable defining a proof precisely. During many years of training they have assimilated knowledge by experience. Therefore many proofs seem born out of witchcraft containing several magical devices.
However, many proofs appearing in respected mathematical journals, submitted by respected mathematicians, have turned out to contain errors. Recent developments in automated proof systems like Coq and LEAN show promise in checking proofs like for example the famous four color theorem. These automated proof systems build on dependent type theory, which we will not go into.
Informally a proof of a proposition , consists in arguing that an implication is true by first assuming . Usually this is done not only through one implication , but through a series of intermediate implications
where the last proposition is . If is true, this will constitute a proof that is true. Just like in (1.14) , there is an imprecision here. Can you tell what it is?
An integer is called even if it is divisible by . So the even integers are
An integer is called odd if it is not even. So the odd integers are
Consider the proposition:
where i.e., the square of an odd integer is odd. This seems true for a first selection of examples: .
What does it mean exactly for a number to be odd? This means that it is not divisible by or that there exists another integer , such that . So
Therefore we need to show that
Notice that I had to change into in the second proposition above. The two variables are not the same: is associated with and is associated with .
Let us assume that . Now we need to argue that for some . You stare at this for a while and notice that we should use the assumption in computing :
Thus, using our assumption we may conclude that if , then
where . This completes the proof.
The beauty here is that we have verified for all odd natural numbers that their square is odd. Not just a finite selection like .
In many ways a proof is like a detailed argument in a court case, except that the rules of mathematics are universal. You need the absolute truth in the court of mathematics (or science).
Consider the proposition . Prove that
Use that , where is defined in Example 1.35 .

1.5.8 Proof by contradiction

A proposition is either true or false. This seemingly obvious statement goes by the name of the law of excluded middle and dates back to the writings of Aristotle. The law of excluded middle is key in the example below, where you are left with the feeling that you have been deprived of a fair and genuine proof.
An irrational number is a (real) number that is not rational. It is a startling fact that such numbers exist, but they do! The square root of two is an example. We will prove that there exists two irrational numbers , such that is rational.
Consider the proposition given by
Either is true or false. If is true we are done putting . If not, then must be false and is irrational. But then
and we are done putting and .
So which one is it? Is
rational or irrational? This is really advanced mathematics based on the Gelfond-Schneider theorem.
The law of excluded middle can be turned into a powerful proof technique called proof by contradiction.
Suppose we wish to establish that is true. Then we turn things upside down by assuming that is false i.e., that is true. If we then by logical deduction can show that
for some proposition , which is demonstrably false, then cannot be true (since true false is false). Therefore must be false and must be true by the law of the excluded middle. This technique is used all the time!
Let us use proof by contradiction to show that the proposition ( is an irrational number) is true. Assuming that is false, we must have that is true. But is the proposition (that is a rational number)
Here , where is the proposition
since we can assume that is not a common divisor of and by Definition 1.7 . However,
The last implication above follows from Exercise 1.36 . If is even, then for some . Therefore and
so that is also even. We have proved that implies the proposition given by
Since we are assuming that is true, we must have that is false. However we have shown that is true. But is a false. Therefore we must have that is false and therefore that is false. But then according to the law of the excluded middle, we must have that is true.
Consider the first prime numbers
Check that
are prime numbers by using the Sage window below (factor gives the prime factorization of a natural number).
Is it true in general that
is a prime number?
Assume that we know that every natural number must be divisible by a prime number. Prove that there are infinitely many prime numbers using proof by contradiction.
Show how the assumption that there are only finitely many prime numbers say
leads to a contradiction by using that the natural number
must be divisible by a prime number.

1.6 More on sets

Propositions are important, but are confined by the binary values of true and false. We would like to work mathematically with objects like integers, floating point numbers, neural networks, computer programs and so on.

1.6.1 Objects and equality

One of the cornerstones of modern mathematics is deciding when two objects are the same i.e., given two objects and , deciding whether the proposition is true of false. Oftentimes an algorithm for evaluating is needed.
You may laugh here, but this is not always that easy. Even though objects appear different they are the same as in, for example the propositions
The first proposition above is an identity of fractions (rational numbers). The second is an identity, which calls for knowledge of the sine function and real numbers. Each of these identities calls for some rather advanced mathematics. The first proposition is true in a very precise way, since .
Use the Sage window above to reason about equality in the quiz below. In each case describe the objects i.e., are they numbers, symbols, etc.? Also, please check your computations by hand with the old fashioned paper and pencil, especially .
Click on the right equalities below.
You know that . Use Sage to find a similar identities for and .
Go back and look at (the beginning of) Exercise 1.40 .
For two objects and we will use the notation for the proposition .
We have already defined a set (informally) as a collection of distinct objects or elements. We introduce some more set theory here. A set is also an object as described in section 1.6.1 and it makes sense to ask when two sets are equal.
Two sets and are equal i.e., if they contain the same elements.
An example of a set could be the set of natural numbers between and . Notice again that we use the symbol "" to start the listing of elements in a set and the symbol "" to denote the end of the listing. Notice also that (by our definition of equality between sets), the order of the elements in the listing does not matter i.e.,
We are also not allowing duplicates like for example in the listing (such a thing is called a multiset).
An example of a set not involving numbers could be the set of letters
used in this sentence. The number of elements in a set is called the cardinality of the set. We will denote it by .
To convince someone beyond a doubt (we will talk about this formally later in this chapter) that two sets and are equal, one needs to argue that if is an element of , then is an element of and the other way round, if is an element of , then is an element of . If this is true, then and must contain the same elements.
Give a precise reason as to why the two sets and are not equal. Is it possible for a set with elements to be equal to a set with elements?
Sets may be explored using (only) python. This is illustrated in the snippet below.
Come up with three lines of Sage code that verifies . Try it out.

The empty set

There is a unique set containing no or zero elements. This set is called the empty set and is denoted i.e.,
For some reason (perhaps a good one) python does not accept as input for the empty set. Why is this? Evaluate the python snippet below and explain.

1.6.2 The symbols and

The symbol is ubiquitous in set theory (and mathematics). If is a set, then
is a proposition. It is true if is an element of or belongs to . The notation
is defined by the proposition . Also, as a bit of short hand notation, we will write
Belongs to () is straightforward in python.
, but
. This exercise actually has
possible correct solutions if is in the second empty box and in the fourth empty box.

1.6.3 Subsets

If and are sets, then At times, the symbol is used instead of . In our context these two symbols mean the same. However, the notation means that and . For example, and . means that every element of is an element of . So is a placeholder for the proposition
In this case we say that is a subset of . We also use the notation to indicate that and . In this case we say that is a strict subset of .
List the subsets of . How many are there?
It turns out that the empty set is a subset of any set.
Explain why this is so using the definition of .
LLM
💬

Explain precisely in terms of propositions and logic why the empty set is a subset of any given set.

| ChatGPT | Claude | Copilot | Gemini | HuggingChat | Mistral |
Below Sage (not python) will list all subsets of the set . Before pressing the Compute button, try to write them down on your own.
List all the subsets of a set with five elements. In general, how many subsets does a set with elements have?
The set
is not a subset of
, simply because
does not belong to . This exercise actually has
possible correct solutions.
The empty set has
elements. A set with
elements has
subsets. In general a set with elements has
subsets.

1.6.4 Set-builder notation

If is a set and a predicate for , then we build the subset
of such that is true.
Suppose that and
Then
Python
This notation has found its way to several programming languages like list comprehension in python.
Suppose that are predicates with a variable taking values in , then we often use the notation (using instead of )
In the exercises below we have sloppily used the ordering before it is formally defined. We apologize to the reader and refer to Section 1.7 .
List the elements in the following subsets.
Consider the predicate
Write down the elements in
Is
an infinite set?
Explore the fascinating world of prime numbers and learn about twin primes.
You have previously encountered systems of linear equations like
The solutions to (1.12) can be identified with a subset of . Define this subset precisely i.e., write the subset as
where is a predicate in the variables .
Suppose that and
Then write down precisely what is i.e., find suitable predicates in the variable , such that and
Consider the subset of pictured in the drawing below
Express as
where are predicates in the variables .
Hint
A predicate in the variables could be something like
Express as
where
and and are suitable predicates in the variables .

1.6.5 Intersections, unions and the symbols and

Suppose that we have two sets and . Then the intersection is the set consisting of the elements in both and i.e.,
This is illustrated in the socalled Venn diagram below.
The union is the set consisting of the elements in or i.e.,
This is illustrated in the Venn diagram below.
Lastly, the difference (between and ) consists of the elements in not contained in i.e.,
This is illustrated in the Venn diagram below.
Python
You should experiment using the python window below to get a feeling for these three operations.
Suppose that , and . What is ?
Let , and . Verify by hand (no computer) that
  1. .
  2. .
  3. .
  4. .
Given two sets and , is it true that and ?
What about ?
Suppose that and are two finite sets. Is it true that
What about
Seriously, both formulas are wrong. Can you come up with the correct version of the formula for ?
Use your correct formula to find a formula for
viewing as the first set and as the second set. Here you need the formula
Why is this formula true? Finally, explain why
Hint
If you are attacking the last part of this exercise using Exercise UNDEFINED: logictt , you may find it useful to notice that two sets are equal i.e, if and only if
Also,
There is one more operation called the symmetric difference between two sets and . It is denoted . Experiment in the python window below to find out exactly what it does. Is it true that ?
The following is an excerpt from the infamous Beredskabsprøve Datalogi.
Let and denote sets. Which of the following are true?
For some sets and we can have

1.6.6 Pairs, triples and tuples

Oftentimes we want to consider more than one variable as input to a predicate. It is convenient to group the variables into one object consisting of the variables. This is done using tuples.
Given two sets and , we combine two elements and into a pair , which is an element of the Cartesian product
of and . This is a new set built from and .
If and , then
Consider two pairs and each from in . When is ?
Python
The Cartesian product can be computed in python as shown below.
There is no need to restrict ourselves to pairs. We might as well consider triples i.e., the set of all , where , and are sets, or for that matter general tuples
of any length , where . Based on the above example with tuples we have,
You may check this using the python snippet below.
For a given set and we define the -fold cartesian product of as
Formally is the set of pairs , where . Is there a natural way of drawing elements in ?
Let and be two sets. Is ?
Let be any set. What is ?
Let and be four sets. Is
Is
See Exercise 1.68 .
Use python to solve Exercise 1.67 by playing with (and extending) the code below.

1.7 Ordering numbers

Let us be a little rigorous and introduce the (usual) ordering on our numbers with addition and multiplication using almost full blown mathematical formalities. The natural order on the natural numbers is
For the numbers and it is less obvious how to define an order. Mathematical simplicity comes to the rescue here. It is enough to define what (the) positive numbers are! We want (the) positive numbers to satisfy the conditions below.
A subset of positive numbers in a set of numbers must satisfy
  1. For every one and only one of the following conditions must hold
  2. If , then and .
For a set of positive numbers in , we define
and
We will write if and if .
Notice that we only use arithmetic operations to define orders on numbers in Definition 1.69 . This is also how computers compare numbers algorithmically. Also if , putting makes all of the conditions in Definition 1.69 hold. If you are given an integer, it is , positive or negative. This is the content of (ⅰ) in Definition 1.69 . Also given two natural numbers, their product and sum are also natural numbers. This is the content of (ⅱ) in Definition 1.69 .
Suppose that , where is a set of numbers and given by a subset of positive numbers as in Definition 1.69 . Prove that

1.7.1 Ordering

As we saw in Remark 1.70 , the natural order on is defined by , so that if for . This completely agrees with our preconception that
To be precise, writing is nonsense, since is only defined for two integers.
How is one supposed to interpret for example? Go ahead and formulate (1.14) correctly comparing only two integers at a time. How does Python/Sage interpret ? Find out using the Sage snippet below.
What about ? What about ?
Assume that and that . Then drag and drop the elements from the left to the right below to explain that .
By assumption .
This means that
This means that
To show that , we need to show that .
But . Therefore,
But . Therefore,
, since

1.7.2 Ordering

We define the positive rational numbers as
One can check that satisfies the conditions in Definition 1.69 . So formally we get
For ,
We must check when
This happens precisely when the numerator or . Therefore the condition in the proposition is satsified.
Use proof by contradiction (see section 1.5.8 ) to show precisely that there does not exist a smallest positive rational number.
Suppose that .
  1. Is it true in general that
  2. Is it true in some cases?
  3. Suppose that . Prove that
  4. What happens to the rational number
    when grows and becomes very big?
Using Definition 1.74 , you can check that , since
An easy, but surprising, way of finding a rational number strictly between these two is adding their numerators and denominators:
We wil try to explain the first inequality in mathematical general terms going through a rather formal proof consisting of five steps. These steps are given in the quiz below. Your task is to drag from the left and drop them to the right in an order, so that the proof makes sense.
After that you are supposed, on your own, to write down a precise proof of the second inequality.
Order the arguments below so that they constitute a coherent explanation of the statement that if
then
By definition this means that .
We are assuming that .
For integers we know that the rule holds. Therefore
we need to show that .
Since and is a consequence of , we are done if we know this is true.
However, this is a consequence of our assumption .
To show that we need to argue that .
we need to show that .
Similarly to the quiz above, assume that
Write down a precise argument showing that
On Twitter, Raman Gupta posted the note below
\begin{excluderag}
\end{excluderag}
For a natural number ,
For example, and . What is the answer for the question in the note?
Experiment a bit with Sage: define a function , which computes
Then look at
The exercise below shows that our trick for finding rational numbers in between two given rational numbers can be made into a machine for generating all positive rational numbers!
Can you spot the system in the fractions in the diagram below?
Once you see the system, extend the diagram with the next level downwards. Is every positive fraction present in this diagram if one keeps adding levels?
Suppose that
and . Then for
we have and . If is a positive fraction, such that
show that

1.7.3 Ordering

For the real numbers we define the positive numbers as
Even though we have not precisely defined addition and multiplication of the real numbers, we claim that this definition of satisfies the conditions of Definition 1.69 .
One may prove that for every , there exists , such that . This is the archimedean property of the real numbers.
Given two distinct real numbers . Prove that there exists a rational number , such that
One other crucial property is the completeness of . It says that a non-empty subset with an upper bound i.e., , always has a smallest upper bound. The rational numbers do not share this property, since for example
does not have a smallest upper bound inside .

1.8 Proof by induction

A precocious Gauss See the article Gauss's Day of Reckoning for some history of this anecdote. proved the formula
at the age of seven displaying remarkable ingenuity for his age. Lesser mortals usually use induction to prove this formula. Gauss was asked along with his classmates to compute the sum of all natural numbers . Using his formula he quickly came up with the correct answer . His classmates had to work for the entire lesson.
Suppose that the formula in (1.15) is viewed as a proposition . To prove the formula we need to prove it for all natural numbers (you can easily see that and are true) i.e., we need to prove
An induction proof is a way of proving this statement by showing two things:
These two statements ensure that . Therefore must be true, since we assumed true from the beginning. Similarly ensures that is true and so on. In fact we have proved for every using this technique. One can prove this using proof by contradiction and that every non-empty subset of has a first element. In general if is a subset of set with an order , then is called a first element if
A crucial rule (or axiom) is that every non-empty subset of has a first element! Notice that this is false for .
Suppose that are infinitely many propositions given by . Then
is true if
  1. is true.
  2. is true.
Suppose by contradiction that there exists , such that is false. Then the subset
is non-empty. Therefore it has a first element . Here , since is assumed to be true. So we know that is true and that is true. But the latter implication is a contradiction, since true implies false is false.
Let us see how an induction proof plays out in the above example with the statement that
Clearly is true. We need to prove , so we assume that holds i.e., that (1.16) is true. Then we may add to both sides of (1.16) to get
Here the right hand side can be rewritten as
which is exactly what we want. This is the conjectured formula for the sum of the numbers . Therefore we have proved that and the induction proof is complete.
For a real number , the extremely useful formula
holds. Let us prove this formula by induction. For this amounts to the identity
which is true since . We let denote the identity in (1.17) . We have seen that is true. The induction step consists in proving . We can prove this by adding to the right hand side in (1.17) :
Real life application
In order to pay for a house you borrow DKK at an interest of per year. You want to pay off your debt over years by paying a fixed amount each year. How much is the fixed yearly amount you need to pay?
Let us analyze the setup: suppose that the fixed yearly amount is . We will find an equation giving us in terms of and . Put .
After one year you owe
After two years you owe
After three years you owe
In general after years you owe
Since we want to be debt free after years, the yearly payment will have to satisfy
By the formula (1.17) , we get
Here can be isolated giving the formula
With the current (August 2024) interest rate around four percent, you pay a fixed monthly amount of around 4770 DKK (down from 5420 DKK in 2023, when the interest rate was five percent) for borrowing one million DKK over years.
Verify the computation (induction step) in (1.18) i.e., explain the operations used to go from the left to the right of the two equalities.
Locate the mistake in the following fake induction proof of the curious fact that for every .
Let be the proposition . Then is true.
We wish to prove that assuming that are true:
This shows that and therefore that for every .
Prove by induction that the sum of the first odd numbers is given by the formula
i.e., for we have
Prove by induction that
Prove using the idea of induction that
for .
The last exercise related to induction concerns the famous pigeonhole principle. The statement itself looks innocent, well almost ridiculous, but it is very powerful. Even the go-to website mathoverflow for research mathematicians has a quite nice thread about this.
Prove the following by induction on : if items are put into containers and , then at least one container must contain more than one item.

1.9 The concept of a function

A function is a crucial concept in mathematics. In Sage (actually python here) a simple function can be programmed like
The code above seems to take a number and returns the number plus one. This (f) is in fact a function taking as input a number and returning as output the number plus one. Notice that we do not even know which numbers we are talking about here. In mathematics we need to have a more precise notion of a function.
The above python function could more formally be denoted as with if we are dealing with the integers, but we cannot tell from the code.
Well, to be fair ...
To be completely fair, it is possible from Python 3.5 to add type annotations to functions, so that we could write

def f(n: int) -> int: return(n+1)

in the Python code to state that the function should take values in the integers and return integers.
The precise mathematical definition of a function in terms of sets is the following. A function is a subset , such that . In words it states that a function is a subset of , containing pairs having only one second coordinate for every first coordinate.
The everyday working definition of a function is more intuitive: a machine taking input from some set and giving output in some set . The uniqueness of the output is encoded in the mathematical definition of a function.
Mathematically a function takes values from a set and returns values in a set . In details, it is denoted and the value associated with is denoted . Here is called the domain of and is called the codomain of . Less, formally is called the input set and the output set for .
Please notice that a function is a very, very general concept. It is not just something that you draw as a graph on a piece of paper. Of course, you can draw a function like :
Generally, a function is given by a machine, formula or algorithm that computes for every . Nothing more, nothing less. It really has nothing to do with a graph (even though graphs can sometimes be useful for visualizing certain functions like ).
Good examples of functions can be found in the cryptographic hash functions. They are examples of complicated functions , where is infinite and finite. Here could be data like plain text files and could be a bit number. This is the setup for the widely used sha-256 cryptographic hash function. The whole point of a cryptographic hash function is that it must be humanly impossible to compute with given A pair with is called a collision . In fact, sha-256 is used in the Bitcoin block chain. The precise definition of sha-256 can be found in FIPS PUB 180-4 approved by the Secretary of Commerce.
Other interesting functions output a bounded size digital footprint (checksum) of a file (like md5). This is very useful for checking data integrity of downloads over the internet. The md5 hash is a bit number.
Instead of listing or bits for the hash value one uses hexadecimal notation with digits in 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 , a, b, c, d, e, f. A pair of hexadecimal digits then represents a byte or bits. Output from sha-256 and md5 consist of and hexadecimal digits respectively. You are welcome to experiment with these two hash functions in the Sage window below.
What is the sha-256 hash of your name? Change a few letters and recompute. Do you see any system? What about the md5 hash function? Can you find two different strings with the same md5 hash using your computer?
I have not answered the last question myself, but I am told that it is possible to find a collision for md5 using a garden variety home computer. Browsing the internet, it seems that the two strings and given in hexadecimal notation This notation represents a sequence of bytes given by pairs of hexadecimal digits by

d131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f89 
55ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5b 
d8823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cda0 
e99f33420f577ee8ce54b67080a80d1ec69821bcb6a8839396f9652b6ff72a70

and

d131dd02c5e6eec4693d9a0698aff95c2fcab50712467eab4004583eb8fb7f89 
55ad340609f4b30283e4888325f1415a085125e8f7cdc99fd91dbd7280373c5b 
d8823e3156348f5bae6dacd436c919c6dd53e23487da03fd02396306d248cda0 
e99f33420f577ee8ce54b67080280d1ec69821bcb6a8839396f965ab6ff72a70 

give a collision for md5. Verify that and that they give the same md5 hash. If you find a collision for sha-256 you will become world famous.

1.9.1 When are two functions the same?

Suppose that . This way of defining a function is a bit sploppy. The domain and codomain is not defined. The correct way of defining a function also includes defining its domain and codomain as in Definition 1.90 . Two functions are the same when they have the same domain and codomain and for every .
The functions and given by and are not the same! Their domains are different.

1.9.2 Notations for defining a function

If is a function and is a finite set, then you can define using a simple table. This is best illustrated using an example. Suppose that and
Then is expressed in table form as
Very often the bracket (or Tuborg in Danish) notation is used. It is similar to if-then-else statements in programming:
defines the function that outputs if the input and if . In python we may express this as
What is and for the function defined in (1.19) . Draw the graph of . Come up with a function , where it does not make sense to draw a graph.

1.9.3 Composition of functions

Given two functions and , where , we define a new function by
This notion calls for some reflection. We have a total of four sets in this definition: and and, not to forget, the condition that . If this last condition was not satisfied it would be meaningless to apply the function to . I hope the diagram below helps the understanding.
The concept of a function is powerful and underlies functional programming in computer science: every computation can be realized as applying a composition of functions to an argument. This is exemplified in the computer language Haskell.
Suppose that
and that and are given by the tables
Compute the table for . Show that is not injective. Adjust the table for so that becomes bijective.
Consider and given by
What is as a function from to in terms of ?

1.9.4 Functions from and into products

Suppose that
as in (1.13) . Then the function given by
is called the projection on the -th coordinate.
If is a function, then
where .
Suppose that and . Then
Now suppose that and that is given by
Then

1.9.5 Injective and surjective functions

We now define three very important notions related to functions.
Let be a function. Then is called
  1. injective, if for every .
  2. surjective, if for every , there exists , such that .
  3. bijective, if it is both injective and surjective.
Is a cryptographic hash-function as defined in Example 1.92 injective?
Suppose that
and that the function is defined by the table
Is injective? Is it surjective? Is it possible to adjust the table so that becomes injective? Is it possible to adjust the table so that becomes surjective?
Consider the function given by
where . Is injective? Is surjective? Suggest how to change and so that becomes bijective.
Consider the function given by
Show that is bijective.
Write down precisely how the truth table for may be expressed in terms of a function . What are the sets and in this case?

1.9.6 The inverse function

If is bijective, then we may define a function , so that for every and for every . This function is denoted .
How do we define for ? Well, since is surjective, we may find so that . Now, we simply define
We cannot have in with , since is injective. We only have one choice for in (1.20) . Therefore (1.20) really is a good and sound definition.
Let , where be given by the table
Then is given by the table
What if the definition of in Example 1.107 is changed to
Does make sense here?
What is the inverse function of given by ? What is the inverse function of , where and ?

1.9.7 The preimage

Consider a function
where and are sets. If , then the preimage of under is defined by
Definition 1.110 is short and sweet. Here is a first example of the preimage.
Consider the function , where and given by
For , as illustrated below.
What is when and ?
Consider the function given by
and let . What is true about ?

1.9.8 Neural networks

Having defined functions and composition of functions, we can deflate the term (deep) neural network, which is often clouded in magic and mystery.
A neural network is a special case of a function
where and . Neural networks are often compositions of many intermediate functions called (hidden) layers.
Recall from Definition 1.99 that a function such as (1.21) can be written
where are functions . Check out Example 1.100 .
In a neural network the functions are viewed as neurons To be precise, the functions should be viewed as synapses . Depending on their input they either fire or do not fire a signal. Classically this is modelled by the perceptron, which is a function of the form
for fixed numbers (called weights) and a number (called the threshold). If the weighted sum is above the threshold, the neuron fires (returns the value ). If not it does not fire (returns the value ).
Consider the three perceptrons , where
and
Let . Then is a composite function of two functions and . Write down these functions.
Hint
Have a closer look at (1.22) in order to understand how functions from to are expressed. Notice that our notation is a bit inconsistent when it comes to types. For example, the function should really be denoted instead of , since it takes input from . This is remedied in the (hopefully easy to understand) python code below.
LLM
💬

Explain the python code below to me.

def p1(v):
    (x, y) = v
    if -x-y > -3/2:
        return 1
    else:
        return 0

def p2(v):
    (x, y) = v
    if x + y > 1/2:
        return 1
    else:
        return 0

def p3(v):
    (x, y) = v
    if x+y > 3/2:
        return 1
    else:
        return 0

def h(v):
    return (p1(v), p2(v))

def g(v):
    return p3(v)

def f(v):
    return g(h(v))

| ChatGPT | Claude | Copilot | Gemini | HuggingChat | Mistral |
Compute and .
Relate the perceptrons and to the illustration below. What do you think the red and blue line illustrate? What does it mean that a dot is solid compared to hollow? What is special about points between the red and blue lines? Try to relate and to the illustration.
\begin{excluderag}
(Illustration courtesy of William Heyman Krill). \end{excluderag}
Give weights and a threshold for a perceptron that computes the logical and function i.e, must satisfy
Do the same for the logical or function .
The output of one neuron can be used as input for other neurons in a potentially extremely complicated network:
The diagram above represents a neural network, which is a function . This function is actually a composition (represented by the hidden layers , , and the output layer):
All of the nodes above, except the ones in the input layer, represent perceptrons.
Is it possible to find a perceptron , such that
What if you are allowed to use a neural network composed as (one hidden layer)
?
Mathematically there is no reason to use special functions such as perceptrons in each node. One also uses a (smooth) version of the perceptron employing the sigmoid function. With the notation above, this function is given as
However, around 2011 it was observed that the perceptron activation function (ReLU) as defined in (1.23) led to better training of deep neural networks.