Model: Krelle/e5-small-v2-imo-pairs
Author: Krelle
Pipeline: sentence-similarity
Library: sentence-transformers
Tags: sentence-transformers, safetensors, bert, sentence-similarity, feature-extraction, dense, generated_from_trainer, dataset_size:2778, loss:MultipleNegativesRankingLoss, arxiv:1908.10084, arxiv:1705.00652, base_model:intfloat/e5-small-v2, base_model:finetune:intfloat/e5-small-v2, model-index, text-embeddings-inference, endpoints_compatible, region:us
Base models (finetune): id: intfloat/e5-small-v2
Card metadata: tags: sentence-transformers, sentence-similarity, feature-extraction, dense, generated_from_trainer, dataset_size:2778, loss:MultipleNegativesRankingLoss
base_model: intfloat/e5-small-v2
widget: source_sentence: In the induction example for the sum $1+2+\dots+n$, why do we add $n+1$ to both sides of (1.16)?
sentences: Subsection 1.6.3: Subsets



If $A$ and $B$ are sets, then <footnote>$A\subseteq B$->At times, the symbol $\subset$ is used instead of $\subseteq$. In our context these two symbols mean the same. However, the notation $A\subsetneq B$ means that $A\subseteq B$ and
  $A\neq B$. For example,
  $\{1, 2, 3\} \subseteq \{1, 2, 3\}$ and
  $\{1, 2, 3\} \subset \{1, 2, 3\}$.</footnote> means that
every element of $A$ is an element of $B$. So $A\subseteq B$ is a placeholder for the proposition
$$
\forall x\in A : x\in B
$$

In this case we say
that *$A$ is a subset of $B$*. We also use the notation $A\subsetneq B$ to
indicate that $A\subseteq B$ and $A\neq B$. In this case we say that
$A$ is a *strict* subset of $B$.


Exercise 1.47:

List the subsets of $\{1, 2\}$. How many are there?

/Exercise


Exercise 1.48:

It turns out that the empty set $\emptyset$ is a subset of any set.



Explain why this is so using the definition of $\subseteq$.

\begin{prompting}
Explain precisely in terms of propositions and logic why the empty set is a subset of any given set.
\end{prompting}

/Exercise


Exercise 1.49:

Below Sage (not python) will list all subsets of the set $\{1, 2, 3\}$. 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 $n$ elements have?

/Exercise


Quizexercise 1.50:

\begin{paragraphquiz}
  \question
  The set \box is not a subset of $A=$\box, simply because \box does not belong to $A$.
  This exercise actually has \box possible correct solutions.

\answer
  $\{1, 2, 3\}$
  \answer
  $\{-1, 1, 2, 3, 4\}$
  \answer
  $\{-1, 0, 1, 2, 4\}$
  \answer
  $3$
  \answer
  $-1$
  \answer
  $5$
  \answer
  $6$
  \answer
  $0$
  \case{(is 1347)}{T}   Correct!
  \case{(is 2157)}{T}   Correct!
  \case{(is 2347)}{T}   Correct!
  \case{(is 3287)}{T}   Correct!
  \case{(is 3157)}{T}   Correct!
  \case{(is 3187)}{T}   Correct!
  \default
  Nope. Try again!
\end{paragraphquiz}

/Quizexercise


Quizexercise 1.51:

\begin{paragraphquiz}
  \question
  The empty set has \box elements. A set with \box elements has \box subsets. In general a set with
  $n$ elements has \box subsets.
  \answer
  $1$
  \answer
  $0$
  \answer
  $5$
  \answer
  $25$
  \answer
  $32$
  \answer
  $n^2$
  \answer
  $2^n$
  \case{(is 2357)}{T}
  Correct!
  \default
  Nope. Try again!
\end{paragraphquiz}

/Quizexercise, Section 1.8: Proof by induction



A <footnote>precocious Gauss->See the article Gauss's Day of Reckoning: https://www.americanscientist.org/article/gausss-day-of-reckoning for some history of this anecdote.</footnote>  proved the formula
$$
1 + 2 + \cdots + n = \frac{n(n+1)}{2}
\tag{1.15}$$
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
$1, 2, \dots, 100$. Using his formula he quickly came up with the correct
answer $5050$. His classmates had to work for the entire lesson. 

Suppose that the formula in (1.15) is viewed as a
proposition $p(n)$. To prove the formula we need to prove it for all
natural numbers (you can easily see that $p(1)$ and $p(2)$ are true) i.e.,
we need to prove
$$
\forall n\in \mathbb{N}: p(n).
$$
An induction proof is a way of proving this statement by showing two things:
\begin{enumerate}\item (i)
  $p(1)$
\item (ii)
  $\forall n\in \mathbb{N}: p(n)\implies p(n+1)$
\end{enumerate}
These two statements ensure that $p(1) \implies p(2)$. Therefore
$p(2)$ must be true, since we assumed $p(1)$ true from the
beginning. Similarly $p(2)\implies p(3)$ ensures that $p(3)$
is true and so on. In fact we have proved $p(n)$ for every $n\in \mathbb{N}$
using this technique. One can prove this using proof by
contradiction and that every non-empty subset
of $\mathbb{N}$ has a first element. In general if $S$ is a subset of set with an order $\leq$, then
$s\in S$ is called a first element if
$$
\forall x\in S: s \leq x.
$$
A crucial rule (or axiom) is that every non-empty subset of $\mathbb{N}$ has
 a first element! Notice that this is false for $\mathbb{Z}$.


Theorem 1.82:

  Suppose that $p(n)$ are infinitely many propositions given by $n\in \mathbb{N}$. Then
  $$
  \forall n\in \mathbb{N}: p(n)
  $$
  is true if
\begin{enumerate}\item (i)
  $p(1)$ is true.
\item (ii)
  $\left(\forall n\in \mathbb{N}: p(n)\implies p(n+1)\right)$ is true.
\end{enumerate}

/Theorem

\begin{proof}
Suppose by contradiction that there exists $n\in \mathbb{N}$, such that
$p(n)$ is false. Then the subset
$$
S = \{n\in \mathbb{N} \mid \neg p(n)\}\subseteq \mathbb{N}
$$
is non-empty. Therefore it has a first element $n_0\in S$. 
Here $n_0 > 1$, since $p(1)$ is assumed to be true. So we
know that $p(n_0-1)$ is true and that
$p(n_0-1)\implies p(n_0)$ is true. But the latter
implication is a contradiction, since true implies
false is false.
\end{proof}



Let us see how an induction proof plays out in the above example
with the statement $p(n)$ that
$$
1 + 2 + \cdots + n = \frac{n(n+1)}{2}.
\tag{1.16}$$
Clearly $p(1)$ is true. We need to prove $p(n)\implies p(n+1)$, so
we assume that $p(n)$ holds i.e., that (1.16) is true.
Then we may add $n+1$ to both sides of (1.16) to get
$$
1 + 2 + \cdots + n + (n+1) = \frac{n(n+1)}{2} + (n+1).
$$
Here the right hand side can be rewritten as
$$
\frac{n(n+1) + 2(n+1)}{2} = \frac{(n+1)(n+2)}{2},
$$
which is exactly what we want. This is the conjectured formula for
the sum of the numbers $1, 2, \dots, n, n+1$. Therefore
we have proved that $p(n)\implies p(n+1)$ and the induction
proof is complete.


Example 1.83:

  For a real number $r\neq 1$, the extremely useful formula
  $$
  1 + r + \cdots + r^n = \frac{1 - r^{n+1}}{1-r}
  \tag{1.17}$$
  holds. Let us prove this formula by induction. For $n=1$ this amounts to the identity
  $$
  1 + r = \frac{1-r^2}{1-r},
  $$
  which is true since $1-r^2 = (1+r)(1-r)$. We let $p(n)$ denote
  the identity in (1.17). We have seen that $p(1)$ is true. The induction step
  consists in proving $p(n)\implies p(n+1)$. We can prove this
  by adding $r^{n+1}$ to the right hand side in (1.17):
  $$
  \frac{1 - r^{n+1}}{1-r} + r^{n+1} = \frac{1 - r^{n+1} + (1-r) r^{n+1}}{1-r} = \frac{1 - r^{n+2}}{1-r}.
  \tag{1.18}$$
Real life application:
    In order to pay for a house you borrow $P$ DKK at an interest of
    $r$ per year. You want to pay off your debt over $N$ 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 $Y$. We will find an equation giving us $Y$ in terms of
    $P, N$ and $r$. Put $q = 1+ r$.

After one year you owe
    $$
    q P - Y.
    $$
    After two years you owe
    $$
    q(q P - Y) - Y.
    $$
    After three years you owe
    $$
    q ( q ( q P - Y) - Y) - Y.
    $$
    In general after $n$ years you owe
    $$
    q^n P - Y (1 + q + \cdots + q^{n-1}).
    $$
    Since we want to be debt free after $N$ years, the yearly payment will have to satisfy
    $$
    q^N P = Y ( 1 + q + \cdots + q^{N-1}).
    $$
    By the formula (1.17), we get
    $$
    q^N P = Y \frac{1-q^N}{1-q}.
    $$
    Here $Y$ can be isolated giving the formula
    $$
    Y = \frac{r P}{1 - \left(\frac{1}{1+r}\right)^N}.
    $$ 
    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 $30$ years.
    
  

/Example, Subsection 1.9.5: Injective and surjective functions



We now define three very important notions related to functions.


Definition 1.101:

  Let $f: S\rightarrow T$ be a function. Then $f$ is called
  \begin{enumerate}\item (i)
    *injective*, if $f(x) = f(y) \implies x = y$ for every $x, y\in S$.
  \item (ii)
    *surjective*, if for every $y\in T$, there exists $x\in S$, such that $f(x) = y$.
  \item (iii)
    *bijective*, if it is both injective and surjective.
  \end{enumerate}

/Definition


Exercise 1.102:

Is a cryptographic hash-function as defined in Example (1.92) injective?

/Exercise


Exercise 1.103:

Suppose that
$$
S = \{1, 2, 3\}\qquad\text{and}\qquad T = \{1, 2, 3, 4\}
$$
and that the function $f: S\rightarrow T$ is defined by the table
$$
\def\arraystretch{1.5}
\begin{array}{c|ccccccc}
x & 1 & 2 & 3\\ \hline
f(x) & 1 & 2 & 4
\end{array}
$$
Is $f$ injective? Is it surjective? Is it possible to adjust the table so that
$f$ becomes injective?
Is it possible to adjust the table so that
$f$ becomes surjective?

/Exercise


Exercise 1.104:

Consider the function $f:S \rightarrow T$ given by
$$
f(x) = x^2,
$$
where $S = T = \mathbb{R}$.
Is $f$ injective? Is $f$ surjective? Suggest how to change $S$ and $T$ so that $f:S\rightarrow T$ becomes
bijective.

/Exercise


Exercise 1.105:

Consider the function $f:\mathbb{Z} \rightarrow \mathbb{Z}$ given by
$$
f(x) = x + 1
$$
Show that $f$ is bijective.

/Exercise


Exercise 1.106:

Write down precisely how the truth table for $p\implies q$ may
be expressed in terms of a function $f: S\rightarrow T$. What are the sets $S$ and $T$ in this case?

/Exercise

Subsection 1.9.6: The inverse function



If $f:S\rightarrow T$ is bijective, then we may define a function $g: T\rightarrow S$, so
that $(f\circ g)(y) = y$ for every $y\in T$ and $(g\circ f)(x)$ for every $x\in S$. This
function is denoted $f^{-1}$.

How do we define $f^{-1}(y)$ for $y\in T$? Well, since $f$ is surjective, we may find
$x\in S$ so that $y = f(x)$. Now, we simply define
$$
f^{-1}(y) = x.
\tag{1.20}$$
We cannot have $x_1 \neq x_2$ in $S$ with $f(x_1) = f(x_2) = y$, since $f$ is injective. We only have one choice for
$x$ in (1.20). Therefore (1.20) really is a good and sound definition.


Example 1.107:

Let $f: S\rightarrow S$, where $S = \{1, 2, 3\}$ be given by
the table
$$
\def\arraystretch{1.5}
\begin{array}{c|ccccccc}
x & 1 & 2 & 3\\ \hline
f(x) & 3 & 1 & 2
\end{array}.
$$
Then $f^{-1}$is given by the table
$$
\def\arraystretch{1.5}
\begin{array}{c|ccccccc}
x & 1 & 2 & 3\\ \hline
f^{-1}(x) & 2 & 3 & 1
\end{array}.
$$

/Example


Exercise 1.108:

What if the definition of $f$ in Example (1.107) is changed to
$$
\def\arraystretch{1.5}
\begin{array}{c|ccccccc}
x & 1 & 2 & 3\\ \hline
f(x) & 3 & 2 & 2
\end{array}.
$$
Does $f^{-1}$ make sense here?

/Exercise


Exercise 1.109:

What is the inverse function of $f:\mathbb{Z}\rightarrow \mathbb{Z}$ given by $f(x) = x + 1$?
What is the inverse function of $g: S \rightarrow S$, where $g(x) = \sqrt{x}$ and
$S = \{x\in \mathbb{R}\mid x\geq 0\}$?

/Exercise, source_sentence: Why do we need truth tables for these logical connectives—can’t we just rely on intuition?
sentences: Section 1.5: Propositional logic



A proposition is a (mathematical) statement that is
true ($t$) or false ($f$). This could be a boolean
expression in a computer program, like $1 < 2$.

Sage:



Later we will see propositions with
variables in them like $x < 2$. These are called predicates.

Propositions can be combined into
new (compound) propositions. Take for example the propositions

$$\begin{aligned}
&p: \text{it rains}\\
&q: \text{it is cloudy}.
\end{aligned}$$

Then ($p$ and $q$) is a perfectly good
  new proposition reading *it rains and it is cloudy*. The same goes for (if $p$ then $q$), which reads
  *if it rains then it is cloudy*. The proposition (if $q$ then $p$) reads *if it is cloudy then
    it rains*. This proposition is (clearly) false.

We need some notation to describe these compound propositions:

$$
\begin{array}{ll}
p \land q\qquad\qquad & \qquad\qquad p \text{ and } q\\
\\
p \lor q\qquad\qquad & \qquad\qquad p \text{ or } q\\
\\
p\implies q\qquad\qquad & \qquad\qquad \text{if } p \text{ then } q\\
\\
\neg p\qquad\qquad & \qquad\qquad \text{not } p
\end{array}
$$

The compound propositions are either true($t$) or false ($f$) depending on
$p$ and $q$. The dependencies are displayed in the *truth tables* below.


Definition 1.18:

$$
\def\arraystretch{1.2}
      \begin{array}{c|c|c}
        p & q  & p\land q  \\
        \hline 
        t & t  & t    \\
        t & f & f\\
        f & t & f\\
        f & f & f
      \end{array}\qquad
      \begin{array}{c|c|c}
        p & q  & p\lor q  \\
        \hline
        t & t  & t    \\
        t & f & t\\
        f & t & t\\
        f & f & f
      \end{array}
      \qquad
      \begin{array}{c|c|c}
        p & q  & p\implies q  \\
        \hline
        t & t  & t    \\
        t & f & f\\
        f & t & t\\
        f & f & t
      \end{array}\qquad
      \begin{array}{c|c}
        p & \neg p \\
        \hline
        t & f\\
        f & t
      \end{array}
  $$

/Definition

The tables for the compound propositions $p\land q, p\lor q$ and also
$\neg p$ are not too hard to grasp. The table for $p\implies q$ 
raises a few more questions. Why is $f\implies t$ 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., Subsection 1.7.2: Ordering $\mathbb{Q}$



We define the positive rational numbers as
$$
\mathbb{Q}_+ = \left\{\frac{m}{n} \in \mathbb{Q} \middle| m > 0\right\} = \left\{1, \frac{1}{2}, \frac{1}{3}, \frac{2}{3}, \frac{1}{4}, \frac{3}{4}, \dots \right\}.
$$
One can check that $\mathbb{Q}_+$ satisfies the conditions in
Definition (1.69). So formally we
get


Proposition 1.74:

For $\cfrac{a}{b},\,\,\, \cfrac{c}{d}\in \mathbb{Q}$,
$$
\frac{a}{b}\, < \frac{c}{d}\qquad \iff\qquad a d < b c\qquad (\text{in }\mathbb{Z}).
$$

/Proposition
\begin{proof}
We must check when
$$
\frac{c}{d} - \frac{a}{b} = \frac{b c - a d}{b d} \in \mathbb{Q}_+.
$$
This happens precisely when the numerator $b c - a d\in \mathbb{N}$ or $b c - a d > 0$. Therefore
the condition in the proposition is satsified.
\end{proof}, Exercise 1.36:

Consider the proposition $q(n) = n \text{ is even}$. Prove that
$$
\forall n\in \mathbb{Z}: q(n^2)\implies q(n).
$$

\begin{hint}
Use that $q(n) = \neg p(n)$, where $p(n)$ is defined in Example (1.35).
\end{hint}

/Exercise, source_sentence: In Exercise 1.72, how should we correctly rewrite the chain $0 < 1 < 2$ so that each comparison involves only two integers?
sentences: Subsection 1.7.1: Ordering $\mathbb{Z}$



As we saw in Remark (1.70), the natural order on $\mathbb{Z}$ is
defined by $\mathbb{Z}_+ = \mathbb{N}$, so that $x < y$ if $y-x\in \mathbb{N}$ for $x, y\in \mathbb{Z}$.
This completely agrees with our preconception that
$$
\cdots < -3 < -2 < -1 < 0 < 1 < 2 < \cdots
\tag{1.14}$$

To be precise, writing $\cdots < -3 < -2 < -1 < 0 < 1 < 2 < \cdots$ is nonsense, since $<$ is only defined for two integers.


Exercise 1.72:

  How is one supposed to interpret $0 < 1 < 2$ for example? Go ahead and formulate (1.14) correctly comparing only two integers at a time.
  How does Python/Sage interpret $-3 < -2 < -1< 0 < 1 < 2$? Find out using the Sage snippet below.



What about $1 < 5 > 3 < 4$? What about $0 < 1 > 2$?

/Exercise


Quizexercise 1.73:

\begin{orderquiz}
  \question
  Assume that $x, y, z\in \mathbb{Z}$ and that $x \leq y$. Then drag and drop the
  elements from the left to the right below to explain that
  $x + z \leq y + z$.
  \answer   By assumption $x\leq y$.
  \answer   This means that $z - x + y\in \mathbb{N}$
  \answer   This means that $y - x\in \mathbb{N}$
  \answer   To show that $x + z \leq y + z$, we need to show that
  $(y + z) - (x + z) \in \mathbb{N}$.
  \answer   But $(y + z) - (x + z) = y + z - x + z$. Therefore,
  \answer   But $(y + z) - (x + z) = y + z - x - z = y - x$. Therefore,
  \answer   $(y + z) - (x + z)\in \mathbb{N}$, since
  \answer   $y - x \in \mathbb{N}$
  \expected{6}

\case{(is 134678)}{T}
  Spot on, my friend.

\case{(is 467813)}{T}
  This is right!

\case{(is 413678)}{T}
  This is right!

\default
  Wrong order. Check the definition of $\leq$ in UNDEFINED: ordZ once more!
\end{orderquiz}

/Quizexercise, Exercise 1.75:

Use proof by contradiction (see section (1.5.8))
to show precisely that there does not
exist a smallest positive rational number.

/Exercise, Section 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 $f: \mathbb{Z}\rightarrow \mathbb{Z}$ with
$f(n) = n+1$ 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
<code>def f(n: int) -&gt; int: return(n+1)
</code>


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 $f: S\rightarrow T$ is a subset
$f\subseteq S\times T$, such that
$(s, t_1)\in f \land (s, t_2)\in f \implies t_1 = t_2$. In words it states that a
function $f: S\rightarrow T$ is a subset $f$ of $S\times T$, 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
$S$ and giving output in some set $T$. The uniqueness of the output
is encoded in the mathematical definition of a function.


Definition 1.90:

Mathematically a function $f$ takes values from a set $S$ and returns values in a set $T$. In details,
it is denoted $f: S\rightarrow T$ and the value associated with $s\in S$ is denoted $f(s)\in T$.
Here $S$ is called *the domain* of $f$ and $T$ is called *the codomain* of $f$. Less,
formally $S$ is called the input set and $T$ the output set for $f$.

/Definition


Remark 1.91:

  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
  $f:\mathbb{R}\rightarrow \mathbb{R}$ like $f(x) = x^2$:
  
  Generally, a function $f: S\rightarrow T$ is given by a machine, formula or algorithm that
  computes $f(x)\in T$ for every $x\in S$. 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 $f(x) = x^2$).

/Remark


Example 1.92:

  Good examples of functions can be found in the cryptographic hash functions: https://en.wikipedia.org/wiki/Cryptographic_hash_function. They are examples of complicated functions $f:S \rightarrow T$, where
  $S$ is infinite and $T$ finite. Here $S$ could be data like plain text files and $T$ could be
  a $256$ 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
  <footnote>compute $y$ with $f(y) = f(x)$ given $f(x)$->A pair $x\neq y$ with $f(x) = f(y)$ is called a collision</footnote>. 
  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: http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf approved by the Secretary of Commerce.

Other interesting functions output a bounded size digital footprint (checksum) of a file (like md5: https://en.wikipedia.org/wiki/MD5). This is very useful
for checking data integrity of downloads over the internet. The md5 hash is a $128$ bit number.

Instead of listing $256$ or $128$ 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 $8$ bits. Output from sha-256 and md5 consist of $64$ and $32$ hexadecimal
digits respectively. You are welcome to experiment with these two hash functions in the
Sage window below.




/Example


Exercise 1.93:

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?

\begin{hint}
  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 $s_1$ and $s_2$ given in <footnote>hexadecimal notation->This notation represents a sequence of bytes given by pairs of hexadecimal digits</footnote> by
<code>d131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f89 
55ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5b 
d8823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cda0 
e99f33420f577ee8ce54b67080a80d1ec69821bcb6a8839396f9652b6ff72a70
</code>


and
<code>d131dd02c5e6eec4693d9a0698aff95c2fcab50712467eab4004583eb8fb7f89 
55ad340609f4b30283e4888325f1415a085125e8f7cdc99fd91dbd7280373c5b 
d8823e3156348f5bae6dacd436c919c6dd53e23487da03fd02396306d248cda0 
e99f33420f577ee8ce54b67080280d1ec69821bcb6a8839396f965ab6ff72a70 
</code>


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

\begin{hint}

\end{hint}
\end{hint}

/Exercise, source_sentence: Why does the textbook emphasize that the ordering in the listing of elements is unimportant?
sentences: Exercise 1.14:

We know that zero times any number is zero. Deduce this from the rules in
Proposition (1.12) starting with $0 + 0 = 0$.

/Exercise, 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, $\{\text{N, i, e, l, s}\}$
is the set of characters in my first name and $\{8, 0\}$ are the digits in the postal code
for Aarhus C. The ordering in the listing of the elements is unimportant so that
$$\begin{aligned}
\{\text{N, i, e, l, s}\} &= \{\text{l, e, i, s, N}\}\\
\{8, 0\} &= \{0, 8\}
\end{aligned}$$
are identical sets. If $S$ is a set, we will use the notation $x\in S$ to denote
that $x$ is an element in $S$. For example, e$\in \{\text{N, i, e, l, s}\}$., Exercise 1.84:

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.

/Exercise


Exercise 1.85:

Locate the mistake in the following fake induction proof of the curious fact that
$2^n = 2$ 
for every $n\in \mathbb{N}$.

Let $p(n)$ be
the proposition $2^n = 2$. Then $p(1)$ is true.

We wish to prove that $p(n) \implies p(n+1)$ assuming that $p(1), \dots, p(n)$ are true:
$$\begin{aligned}
  2^{n+1} &= 2^n \cdot 2\\
          &= 2^n \cdot \frac{2^n}{2^{n-1}}\\
          &= 2 \cdot \frac{2}{2}\,\,\text{(by }p(n)\text{ and }p(n-1)\text{)}\\
          &= 2.
\end{aligned}$$
This shows that $p(n) \implies p(n+1)$ and therefore that $2^n = 2$ for every
$n\in \mathbb{N}\setminus\{0\}$.

/Exercise


Exercise 1.86:

Prove by induction that the sum of the first $n$ odd numbers is
given by the formula
$$
1 + 3 + \cdots + (2 n - 1) = n^2,
$$
i.e., for $n=5$ we have
$$
1 + 3 + 5 + 7 + 9 = 25.
$$

/Exercise


Exercise 1.87:

Prove by induction that
$$
1^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{n(n+1)(2n + 1)}{6}.
$$

/Exercise


Exercise 1.88:

Prove using the idea of induction that
$$
2^n < n!
$$
for $n\geq 4$.


/Exercise

The last exercise related to induction concerns the famous pigeonhole principle: https://en.wikipedia.org/wiki/Pigeonhole_principle. The statement itself looks innocent, well almost ridiculous, but it is very powerful: https://mindyourdecisions.com/blog/2008/11/25/16-fun-applications-of-the-pigeonhole-principle/. Even the go-to website 
mathoverflow: https://mathoverflow.net/ for research mathematicians has 
a quite nice thread: https://mathoverflow.net/questions/4279/interesting-applications-of-the-pigeonhole-principle 
about this.


Exercise 1.89:

Prove the following by induction on $m$: if $n$ items are put into $m$ containers and 
$n > m$, then at least one container must contain more than one item.

/Exercise, source_sentence: In Exercise 1.41 we are asked to find identities for \((a+b)^3\) and \((a+b)^4\). What are the correct expanded forms, and how do they relate to the binomial theorem?
sentences: Chapter 1 on the language of mathematics is an introduction to the fundamental mathematics used in the notes.
Without understanding the basic concepts in it, you do not have the background to understand
the rest of the notes. Important highlights from the chapter are

- Introduction to prompting. This is your ticket to using large language models effectively
- How to use computer algebra (Sage). Sage can be very helpful in understanding the mathematics
- Introduction of the numbers we use. Here the natural numbers, integers, rationals and real numbers are defined. Also the arithmetic rules for using them are given
- Logic is the framework for reasoning in mathematics. Study this! First comes propositional logic. This is basic logic involving true and false statements with and, or etc as seen in truth tables. Then comes predicate logic, where variables are used. Here you must learn the meaning of "for every" and "there exists"
- Proofs are described. Proof by contradiction is a must here! Do not skip it
- The language of sets. Learn the operations on sets. Especially focus on the set builder notation and products of sets
- Ordering of numbers. This is the formal definition of comparing numbers
- Proof by induction. How to prove infinitely many propositions involving the natural numbers with one hack
- The concept of a function. This is extremely important. Notice that a function is defined not by a rule. Also, in its definition enters crucially where it is defined
- Functions from and into products
- The preimage. This will become very important working with continuous functions, Exercise 1.84:

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.

/Exercise


Exercise 1.85:

Locate the mistake in the following fake induction proof of the curious fact that
$2^n = 2$ 
for every $n\in \mathbb{N}$.

Let $p(n)$ be
the proposition $2^n = 2$. Then $p(1)$ is true.

We wish to prove that $p(n) \implies p(n+1)$ assuming that $p(1), \dots, p(n)$ are true:
$$\begin{aligned}
  2^{n+1} &= 2^n \cdot 2\\
          &= 2^n \cdot \frac{2^n}{2^{n-1}}\\
          &= 2 \cdot \frac{2}{2}\,\,\text{(by }p(n)\text{ and }p(n-1)\text{)}\\
          &= 2.
\end{aligned}$$
This shows that $p(n) \implies p(n+1)$ and therefore that $2^n = 2$ for every
$n\in \mathbb{N}\setminus\{0\}$.

/Exercise


Exercise 1.86:

Prove by induction that the sum of the first $n$ odd numbers is
given by the formula
$$
1 + 3 + \cdots + (2 n - 1) = n^2,
$$
i.e., for $n=5$ we have
$$
1 + 3 + 5 + 7 + 9 = 25.
$$

/Exercise


Exercise 1.87:

Prove by induction that
$$
1^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{n(n+1)(2n + 1)}{6}.
$$

/Exercise


Exercise 1.88:

Prove using the idea of induction that
$$
2^n < n!
$$
for $n\geq 4$.


/Exercise

The last exercise related to induction concerns the famous pigeonhole principle: https://en.wikipedia.org/wiki/Pigeonhole_principle. The statement itself looks innocent, well almost ridiculous, but it is very powerful: https://mindyourdecisions.com/blog/2008/11/25/16-fun-applications-of-the-pigeonhole-principle/. Even the go-to website 
mathoverflow: https://mathoverflow.net/ for research mathematicians has 
a quite nice thread: https://mathoverflow.net/questions/4279/interesting-applications-of-the-pigeonhole-principle 
about this.


Exercise 1.89:

Prove the following by induction on $m$: if $n$ items are put into $m$ containers and 
$n > m$, then at least one container must contain more than one item.

/Exercise, Section 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.

Subsection 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 $A$ and $B$, deciding whether
the proposition $A=B$ is true of false. Oftentimes
an algorithm for evaluating $A=B$ 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
$$
\frac{105}{189} = \frac{35}{63}\qquad\text{and}\qquad \sin\left(\frac{\pi}{2}\right) = 1.
$$
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 $105\cdot 63 = 189 \cdot 35$.


Exercise 1.40:




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 $(a+b)(a-b)$.

\begin{quiz}
\question
Click on the right equalities below.
\answer{T}
$$a + b - 2 b = a - b$$
\answer{F}
$$(a+b)^2 = a^2 + b^2$$
\answer{T}
$$(a + b)(a - b) = a^2 - b^2$$
\answer{T}
$$(a + b)^2 = a^2 + 2 a b +  b^2$$
\answer{F}
$$(a+b)^3 = a^3 + 2 a^2 b + 2 a b^2 + b^3$$
\answer{F}
$$\frac{3}{8} = \frac{5}{13}$$ 
\answer{F}
$$
\pi = \frac{22}{7}
$$
\answer{T}
$$
\cos^2(\pi) + \sin^2(\pi) = 1
$$
\end{quiz}

/Exercise


Exercise 1.41:

You know that $(a+ b)^2 = a^2 + 2 a b + b^2$. Use Sage to find a similar identities
for $(a + b)^3$ and $(a + b)^4$.

\begin{hint}
  Go back and look at (the beginning of) Exercise (1.40).
\end{hint}

/Exercise

For two objects $A$ and $B$ we will use the notation $A \neq B$ for the proposition $\neg (A = B)$.

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.


Definition 1.42:

Two sets $A$ and $B$ are equal i.e., $A = B$ if they contain the same elements.

/Definition

An example of a set could be 
the set $\{1,2,3\}$ of natural numbers between $0$ and $4$. 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.,
$$
\{1, 2, 3\} = \{2, 3, 1\}.
$$
We are also not allowing duplicates like for
example in the listing $\{1, 2, 2, 3, 3, 3\}$ (such a thing is called a multiset: https://en.m.wikipedia.org/wiki/Multiset).

An example of a set not involving numbers could be the set of letters 
$$
S=\{A, n, e, x, a, m, p, l, c, o, u, d, b, t, h, s, r, i\}
$$ 
used in this sentence. The number of elements in a set $S$ is called the *cardinality* of the set.
We will denote it by $|S|$.

To convince someone beyond a doubt (we will talk about this formally later in this chapter) that two sets $A$ and $B$ are equal, one needs to argue that if $x$ is an element of $A$, then $x$ is an element of $B$ and the other way round, if $y$ is an element of $B$, then $y$ is an element of $A$. If this is true, then
$A$ and $B$ must contain the same elements.


Exercise 1.43:

Give a precise reason as to why the two sets $\{1, 2, 3\}$ and $\{1, 2, 4\}$ are not equal.
Is it possible for a set with $5$ elements to be equal to a set with $7$ elements?

/Exercise  

Sets may be explored using (only) python. This is illustrated in the snippet below. 

<a href="#a314f450-54ad-4acd-bbf0-475e00ac5949" class ="btn btn-default Sagebutton" data-toggle="collapse"></a><div id=a314f450-54ad-4acd-bbf0-475e00ac5949 class = "collapse Sage envbuttons"><div class=sagepython><script type="text/x-sage">
X = {1, 2, 3}
Y = {2, 3, 1}
print("X=Y is ", X==Y)

S = {'A','n','e','x','a','m','p','l','c','o','u','d','b','t','h','s','r','i'}
print("S = ", S) 
print("The number of elements in S is |S|=", len(S))
</script></div></div>



Exercise 1.44:

Come up with three lines of Sage code that verifies $\{1, 2, 3\} \neq \{1, 2, 4\}$. Try it out.

/Exercise
pipeline_tag: sentence-similarity
library_name: sentence-transformers
metrics: cosine_accuracy@1, cosine_accuracy@3, cosine_accuracy@5, cosine_accuracy@10, cosine_precision@1, cosine_precision@3, cosine_precision@5, cosine_precision@10, cosine_recall@1, cosine_recall@3, cosine_recall@5, cosine_recall@10, cosine_ndcg@3, cosine_ndcg@5, cosine_ndcg@10, cosine_mrr@3, cosine_mrr@5, cosine_mrr@10, cosine_map@100
model-index: name: SentenceTransformer based on intfloat/e5-small-v2
results: task: type: information-retrieval
name: Information Retrieval
dataset: name: Unknown
type: unknown
metrics: type: cosine_accuracy@1
value: 0.6908315565031983
name: Cosine Accuracy@1
verified: no, type: cosine_accuracy@3
value: 0.8347547974413646
name: Cosine Accuracy@3
verified: no, type: cosine_accuracy@5
value: 0.8880597014925373
name: Cosine Accuracy@5
verified: no, type: cosine_accuracy@10
value: 0.9253731343283582
name: Cosine Accuracy@10
verified: no, type: cosine_precision@1
value: 0.6908315565031983
name: Cosine Precision@1
verified: no, type: cosine_precision@3
value: 0.27825159914712155
name: Cosine Precision@3
verified: no, type: cosine_precision@5
value: 0.17761194029850746
name: Cosine Precision@5
verified: no, type: cosine_precision@10
value: 0.09253731343283582
name: Cosine Precision@10
verified: no, type: cosine_recall@1
value: 0.6908315565031983
name: Cosine Recall@1
verified: no, type: cosine_recall@3
value: 0.8347547974413646
name: Cosine Recall@3
verified: no, type: cosine_recall@5
value: 0.8880597014925373
name: Cosine Recall@5
verified: no, type: cosine_recall@10
value: 0.9253731343283582
name: Cosine Recall@10
verified: no, type: cosine_ndcg@3
value: 0.7763328209983278
name: Cosine Ndcg@3
verified: no, type: cosine_ndcg@5
value: 0.7980285423533605
name: Cosine Ndcg@5
verified: no, type: cosine_ndcg@10
value: 0.8099677414320194
name: Cosine Ndcg@10
verified: no, type: cosine_mrr@3
value: 0.7560412224591327
name: Cosine Mrr@3
verified: no, type: cosine_mrr@5
value: 0.7679282160625444
name: Cosine Mrr@5
verified: no, type: cosine_mrr@10
value: 0.7727815006599654
name: Cosine Mrr@10
verified: no, type: cosine_map@100
value: 0.7764057538430271
name: Cosine Map@100
verified: no, type: cosine_accuracy@1
value: 0.6663078579117331
name: Cosine Accuracy@1
verified: no, type: cosine_accuracy@3
value: 0.8116254036598493
name: Cosine Accuracy@3
verified: no, type: cosine_accuracy@5
value: 0.8697524219590959
name: Cosine Accuracy@5
verified: no, type: cosine_accuracy@10
value: 0.9117330462863293
name: Cosine Accuracy@10
verified: no, type: cosine_precision@1
value: 0.6663078579117331
name: Cosine Precision@1
verified: no, type: cosine_precision@3
value: 0.27054180121994975
name: Cosine Precision@3
verified: no, type: cosine_precision@5
value: 0.17395048439181915
name: Cosine Precision@5
verified: no, type: cosine_precision@10
value: 0.09117330462863295
name: Cosine Precision@10
verified: no, type: cosine_recall@1
value: 0.6663078579117331
name: Cosine Recall@1
verified: no, type: cosine_recall@3
value: 0.8116254036598493
name: Cosine Recall@3
verified: no, type: cosine_recall@5
value: 0.8697524219590959
name: Cosine Recall@5
verified: no, type: cosine_recall@10
value: 0.9117330462863293
name: Cosine Recall@10
verified: no, type: cosine_ndcg@3
value: 0.7519327635399075
name: Cosine Ndcg@3
verified: no, type: cosine_ndcg@5
value: 0.7761647660928707
name: Cosine Ndcg@5
verified: no, type: cosine_ndcg@10
value: 0.7896982949533798
name: Cosine Ndcg@10
verified: no, type: cosine_mrr@3
value: 0.7312522425547185
name: Cosine Mrr@3
verified: no, type: cosine_mrr@5
value: 0.7448690348044498
name: Cosine Mrr@5
verified: no, type: cosine_mrr@10
value: 0.7504190373673694
name: Cosine Mrr@10
verified: no, type: cosine_map@100
value: 0.7541642286378775
name: Cosine Map@100
verified: no
Likes: 0 | All-time downloads: 602
Created: 2025-11-10 00:22:56