# Linear algebra (Osnabrück 2024-2025)/Part I/Lecture 1/refcontrol

    Sets
Mathematics in the scientific sense is formulated in the language of sets.
A set is a collection of distinct objects, which are called the elements of the set. By distinct, we mean that it is clear which objects are considered to be equal and which are considered to be different. The containment of an element $x$ to a set $M$ is expressed by
    $x\in M\,,$
the noncontainment by
    $x\notin M\,.$
For every element, exactly one of these possibilities holds.
An important principle for sets is the principle of extensionality, i.e. a set is determined by the elements it contains, beyond that it bears no further information. In particular, two sets coincide if they contain the same elements.
The set which does not contain any element is called the empty set and is denoted by
    $\emptyset .$
A set $N$ is called a subset of a set $M$ if every element from $N$ does also belong to $M$. For this relation we write $N\subseteq M$ (some people write $N\subset M$ for this). One also says that the inclusion $N\subseteq M$ holds. The subset relation $N\subseteq M$ is a statement using for all, as it makes a claim about all elements from $N$. If we want to show $N\subseteq M$, then we have to show for an arbitrary element $x\in N$ that also the containment $x\in M$ holds . In order to show this, we are only allowed to use the property $x\in N$.
Due to the principle of extensionality, we have the following important equality principle for sets, saying that
    $M=N{\text{ if and only if }}N\subseteq M{\text{ and }}M\subseteq N$
holds. In mathematical praxis, this means that the equality of two sets is established by proving the two inclusions (in two independent steps). This has also the cognitive advantage that the reasoning gets a direction; it is always clear which conditions can be used and where to go. This principle is analogous to the principle from propositional logic, that an equivalence between two statements means both implications, and is best shown by proving the two implications.
    Possible descriptions for sets
There are several ways to describe a set. The easiest one is to just list the elements of the set, here the order of the listing is not important. For finite sets this is possible, however, for infinite sets one has to describe a "construction rule“ for the elements.
The most important set given by an infinite listing is the set of natural numbers
    $\mathbb {N} =\{0,1,2,3,\ldots \}\,.$
Here a certain set of numbers is described by a list of starting elements in the hope that this makes it clear which numbers belong to the set. An important point is that $\mathbb {N}$ is not a set of certain digits, but the set of values represented by these digits or sequences of digits. For a natural number there are many possibilities to represent it, the decimal expansion is just one of them.
We discuss now the description of sets by properties. Let $M$ denote a given set. In $M$ there are certain elements which fulfil a certain property $E$ (a predicate) or not. Hence, for the property $E$ we have within $M$ the subset consisting of all the elements from $M$ which fulfil this property. We write for this subset given by $E$
    ${\left\{x\in M\mid E(x)\right\}}={\left\{x\in M\mid x{\text{ fulfils property }}E\right\}}\,.$
This only works for such properties for which the statement $E(x)$ is well-defined for every $x\in M$. If one introduces such a subset then one gives a name to it which often reflects the name of the property, like
    $E={\left\{x\in \mathbb {N} \mid x{\text{ is even}}\right\}}\,,$
    $O={\left\{x\in \mathbb {N} \mid x{\text{ is odd}}\right\}}\,,$
    $S={\left\{x\in \mathbb {N} \mid x{\text{ is a square number}}\right\}}\,$
    ${\mathbb {P} }={\left\{x\in \mathbb {N} \mid x{\text{ is a prime number}}\right\}}\,.$
For the sets occurring in mathematics, a multitude of mathematical properties is relevant and therefore there is a multitude of relevant subsets. But also in the sets of everyday life like the set $C$ of the students in a course, there are many important properties which determine certain subsets, like
    $O={\left\{x\in C\mid x{\text{ lives in Osnabr}}{\ddot {\rm {u}}}{\text{ck}}\right\}}\,,$
    $P={\left\{x\in C\mid x{\text{ studies physics}}\right\}}\,,$
    $D={\left\{x\in C\mid x{\text{ has birthday in December}}\right\}}\,.$
The set $C$ itself is also given by a property, since
    $C={\left\{x\mid x{\text{ is a student in the course}}\right\}}\,.$
The following example of a set is typical for the sets which we will encounter in this course.

## Example Create referencenumber

We consider the set
    $E={\left\{{\begin{pmatrix}x\\y\\z\end{pmatrix}}\in \mathbb {R} ^{3}\mid 5x-y+3z=0\right\}}\,.$
This is the subset inside $\mathbb {R} ^{3}$ containing all those points with coordinates ${\begin{pmatrix}x\\y\\z\end{pmatrix}}$ fulfilling the condition
    $5x-y+3z=0\,.$
This condition has a clear meaning for every point ${\begin{pmatrix}x\\y\\z\end{pmatrix}}$, it can be true or false. Hence, this is a well-defined subset. For example, the points ${\begin{pmatrix}0\\0\\0\end{pmatrix}}$ and ${\begin{pmatrix}2\\-3\\-{\frac {13}{3}}\end{pmatrix}}$ belong to the set, the point ${\begin{pmatrix}2\\4\\0\end{pmatrix}}$ does not belong to the set. If we want to check for a point ${\begin{pmatrix}x\\y\\z\end{pmatrix}}$ whether it belongs to $E$, we just have to check the condition. In this respect, the given description of $E$ is very good. If instead we would like to have a good overview over $E$ as a whole, this description is not so convincing. We claim that $E$ coincides with the set
    $E'={\left\{r{\begin{pmatrix}3\\0\\-5\end{pmatrix}}+s{\begin{pmatrix}0\\3\\1\end{pmatrix}}\mid r,s\in \mathbb {R} \right\}}\,.$
This second description presents the set as the set of all elements which can be built in a certain way, namely as a linear combination of the points ${\begin{pmatrix}3\\0\\-5\end{pmatrix}}$ and ${\begin{pmatrix}0\\3\\1\end{pmatrix}}$ with arbitrary real coefficients. The advantage of this description is that one gets immediately an overview about all its elements. For example, it is clear that it contains infinitely many elements. However, in this description, it is more difficult to decide whether a given element belongs to the set or not.
In order to show that both sets are identical, we have to show $E\subseteq E'$ and $E'\subseteq E$. For the first inclusion, let $P={\begin{pmatrix}x\\y\\z\end{pmatrix}}\in E$. Then
    ${\begin{pmatrix}x\\y\\z\end{pmatrix}}={\frac {x}{3}}{\begin{pmatrix}3\\0\\-5\end{pmatrix}}+{\frac {y}{3}}{\begin{pmatrix}0\\3\\1\end{pmatrix}}\,.$
Here, the equality in the first and in the second component is clear, and the equality in the third component is a reformulation of the starting equation
    $5x-y+3z=0\,.$
Taking $r={\frac {x}{3}}$ and $s={\frac {y}{3}}$, we see that $P\in E'$. Now suppose that $P={\begin{pmatrix}x\\y\\z\end{pmatrix}}\in E'$. This means that there is a representation
    $P={\begin{pmatrix}x\\y\\z\end{pmatrix}}=r{\begin{pmatrix}3\\0\\-5\end{pmatrix}}+s{\begin{pmatrix}0\\3\\1\end{pmatrix}}={\begin{pmatrix}3r\\3s\\-5r+s\end{pmatrix}}\,$
with some real numbers $r,s\in \mathbb {R}$. In order to show that this point belongs to $E$, we have to show that it fulfills the defining equation of $E$. But this is clear because of
    $5x-y+3z=5(3r)-3s+3(-5r+s)=0\,.$
    Set operations
Similar to the connection of statements to get new statements, there are operations to make new sets from old ones. The most important operations are the following.
* Union
    $A\cup B:={\left\{x\mid x\in A{\text{ or }}x\in B\right\}}\,.$
* Intersection
    $A\cap B:={\left\{x\mid x\in A{\text{ and }}x\in B\right\}}\,.$
* Difference set
    $A\setminus B:={\left\{x\mid x\in A{\text{ and }}x\notin B\right\}}\,.$
For these operations to make sense, the sets need to be subsets of a common basic set. This ensures that we are talking about the same elements. Quite often this basic set is not mentioned explicitly and has to be understood from the context. A special case of the difference set is the complement of a subset $A\subseteq G$ in a given base set $G$, also denoted as
    $\complement A:=G\setminus A={\left\{x\in G\mid x\not \in A\right\}}\,.$
If two sets have an empty intersection, meaning $A\cap B=\emptyset$, we also say that they are disjoint.

## Example Create referencenumber

We consider the sets
    $E={\left\{{\begin{pmatrix}x\\y\\z\end{pmatrix}}\in \mathbb {R} ^{3}\mid 5x-y+3z=0\right\}}\,$
(from example *****) and
    $F={\left\{{\begin{pmatrix}x\\y\\z\end{pmatrix}}\in \mathbb {R} ^{3}\mid 4x+2y-7z=0\right\}}\,,$
and we are interested in the intersection
    $G:=E\cap F={\left\{{\begin{pmatrix}x\\y\\z\end{pmatrix}}\in \mathbb {R} ^{3}\mid 5x-y+3z=0{\text{ and }}4x+2y-7z=0\right\}}\,.$
A point lies in this intersection if and only if it fulfills both conditions, that is, both equations (let us call them $I$ and $II$). Does there exist a "simpler“ description of this intersection set? A point, which fulfills both equations, does also fulfill the equation which arises when we add the equations together, or when we multiply the equation with a number $s\in \mathbb {R}$. Such a linear combination of the equations is, for example,
    $4I-5II=-14y+47z=0\,.$
Therefore
    ${\begin{aligned}G&={\left\{{\begin{pmatrix}x\\y\\z\end{pmatrix}}\in \mathbb {R} ^{3}\mid 5x-y+3z=0{\text{ and }}4x+2y-7z=0\right\}}\\&={\left\{{\begin{pmatrix}x\\y\\z\end{pmatrix}}\in \mathbb {R} ^{3}\mid 5x-y+3z=0{\text{ and }}-14y+47z=0\right\}},\end{aligned}}$
since we can reconstruct the original second equation from the new second equation and vice versa. Hence, the conditions are equivalent. The advantage of the second description is that the variable $x$ does not occur in the new second equation, it has been eliminated. Therefore, we can resolve with respect to $y$ and we obtain
    $y={\frac {47}{14}}z\,.$
For $x$, we must have
    $x={\frac {1}{5}}y-{\frac {3}{5}}z={\frac {1}{5}}\cdot {\frac {47}{14}}z-{\frac {3}{5}}z={\frac {47}{70}}z-{\frac {42}{70}}z={\frac {1}{14}}z\,.$
Also, these two resolved equations are together equivalent with the original equations and, therefore, we have
    $G={\left\{{\begin{pmatrix}{\frac {1}{14}}z\\{\frac {47}{14}}z\\z\end{pmatrix}}\mid z\in \mathbb {R} \right\}}\,.$
This description yields a more explicit overview over the set $G$.
    Constructions of sets
Most relevant sets in mathematics arise from some basic sets like finite sets or $\mathbb {N}$ by certain constructions. We define.

## Definition

Suppose that two sets $L$ and $M$ are given. Then the set
    $L\times M={\left\{(x,y)\mid x\in L,\,y\in M\right\}}\,$
is called the product set
The elements of a product set are called pairs and denoted by $(x,y)$. Here the ordering is essential. The product set consists of all pair combinations, where in the first component there is an element of the first set and in the second component there is an element of the second set. Two pairs are equal if and only if they are equal in both components.
It is possible that both sets are equal, like $\mathbb {R} \times \mathbb {R}$, the real plane. Then one has to be careful not to confuse the components. If one of the sets is empty, then so is the product set. If both sets are finite, say the first with $n$ elements and the second with $k$ elements, then the product set has $n\cdot k$ elements. It is also possible to form the product set of more than two sets.

## Example Create referencenumber

Let $F$ be the set of all first names, and $L$ be the set of all last names. Then
    $F\times L$
is the set of all names. The elements of this set are, in pair notation, $({\text{Heinz}},{\text{Miller}})$, $({\text{Petra}},{\text{Miller}})$ and $({\text{Lucy}},{\text{Sonnenschein}})$. From a name, one can deduce easily the first name and the last name by looking at the first or the second component. Even if all first names and all last names do really occur, not every combination of a first name and a last name does occur. For the product set, all possible combinations are allowed.

## Example Create referencenumber

A chess board (meaning the set of squares of a chess board where a chess piece may stand) is the product setMDLD/product set
    $\{a,b,c,d,e,f,g,h\}\times \{1,2,3,4,5,6,7,8\}.$
Every square is a pair, e.g. $(a,1),(d,4),(c,7)$. Because the two component sets are different, one may write instead of pair notation simply $a1,d4,c7$. This notation is the starting point to describe chess positions, and complete chess games.
When two geometric point sets $A$ and $B$ are given, for example as subsets of a plane $E$, then we can consider the product set $A\times B$ as a subset of $E\times E$. By this procedure, we get a new geometric object, which sometimes might be realized in a smaller dimension.

## Example Create referencenumber

Let $S$ denote a circle (the circumference), and let $I$ be a line segment. The circle is a subset of a plane $E$, and the line segment is a subset of a line $G$, so that for the product sets, we have the relation
    $S\times I\subseteq E\times G\,.$
The product set $E\times G$ is the three-dimensional space, and the product set $S\times I$ is the surface of a cylinder.
Another important construction, to get from a set a new set, is the power set.

## Definition

For a given set $M$, the set consisting of all subsets of $M$ is called the power set of $M$. It is denoted by
    ${\mathfrak {P}}\,(M).$
We have thus
    ${\mathfrak {P}}\,(M)={\left\{T\mid T{\text{ is subset of }}M\right\}}\,.$
If $M$ denotes the set of all people in the course, then one can think of a subset as a party (within the course), where some people go to (we identify parties with the attending people). The power set is then the set of all possible parties. If the set has $n$ elements, then the power set contains $2^{n}$ elements.
    Tuples, vectors, matrices
Important product sets are $\mathbb {R} ^{2}=\mathbb {R} \times \mathbb {R}$ and $\mathbb {R} ^{3}=\mathbb {R} \times \mathbb {R} \times \mathbb {R}$. The ordering of the elements is essential. In general, for a set $M$ and some $n\in \mathbb {N}$, we denote the $n$-th fold product set of $M$ with itself as
    $M^{n}=\underbrace {M\times \cdots \times M} _{n{\text{-mal}}}\,.$
The elements have the form
    $\left(x_{1},x_{2},\ldots ,x_{n}\right),$
where all $x_{i}$ are from $M$. Such an ordered finite sequence of $n$ elements is also called an $n$-tuple over $M$. For $n=2$, it is called a pair, for $n=3$ it is called a triple. For
    $x=\left(x_{1},x_{2},\ldots ,x_{n}\right)\,,$
the element $x_{i}$ is called the $i$-th component or the $i$-th entry of the tuple. In this context, the $i$ is called the index of the tuple and $\{1,\ldots ,n\}$ is called the index set of the tuple.
More generally, for every index set $I$, there exist $I$-tuples. In such an $I$-tuple, to every index $i\in I$ some mathematical object is assigned, the tuple is often written as $x_{i}$, $i\in I$ If all $x_{i}$ are from one set $M$, then we call this an $I$-tuple from $M$. For $I=\mathbb {N}$, we call this a sequence in $M$.
A finite index set can always be replaced by a set of the form $\{1,\ldots ,n\}$ (this procedure is called a numbering of the index set), but this is not always useful. If we start with the index set
    $I=\{1,\ldots ,n\}\,$
and if we are interested in a certain subset $J\subseteq I$, then it is natural to stick to the original notation from $I$, instead of introducing a new numbering $\{1,\ldots ,m\}$ for $J$. Quite often there are "natural“ index sets for a certain problem, which represent a part of the structure of the problem (and is easier to remember).
An $n$-tuple over a set $M$ of the form
    $\left(a_{1},\,\ldots ,\,a_{n}\right)$
is also called a row tuple (of length $n$) and an $n$-tuple of the form
    ${\begin{pmatrix}a_{1}\\\vdots \\a_{n}\end{pmatrix}}$
is called a column tuple. These are just two different ways to represent the tuple; but if the tuple represents some structure (like a vector, to which a matrix (see below) shall be applied), then this difference is relevant.
When $I$ and $J$ are two sets and $I\times J$ is their product set, then we can express an $I\times J$-tuple in $M$ as a "table“, which assigns to every pair $(i,j)$ an element $a_{ij}\in M$. In particular, for $I=\{1,\ldots ,m\}$ and $J=\{1,\ldots ,n\}$, we call an $I\times J$-tuple also an $m\times n$-matrix and write this as
    ${\begin{pmatrix}a_{11}&a_{12}&\ldots &a_{1n}\\a_{21}&a_{22}&\ldots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{m1}&a_{m2}&\ldots &a_{mn}\end{pmatrix}}.$
The row tuple
    $\left(a_{i1},\,a_{i2},\,\ldots ,\,a_{in}\right)$
is called the $i$-te row of the matrix and
    ${\begin{pmatrix}a_{1j}\\a_{2j}\\\vdots \\a_{mj}\end{pmatrix}}$
is called the $j$-te column of the matrix.
    Set families
Not only elements, but also sets can be indexed by an index set. This is called a family of sets.

## Definition

Let $I$ be a set and let, for every $i\in I$, a set $M_{i}$ be given. Such a situation is called a family of sets
    $M_{i}{\text{ , }}i\in I.$
$I$
Here, the sets might be independent of each other, but they can also be subsets of a certain base set.

## Definition

Let $M_{i}$, $i\in I$, be a family of subsetsMDLD/family of subsets of one set $G$. Then
    $\bigcap _{i\in I}M_{i}={\left\{x\in G\mid x\in M_{i}{\text{ for all }}i\in I\right\}}\,$
is called the intersection of the sets and
    $\bigcup _{i\in I}M_{i}={\left\{x\in G\mid {\text{ there exists some }}i\in I{\text{ with }}x\in M_{i}\right\}}\,$

## Definition

Let $I$ be a set and let, for every $i\in I$, a set $M_{i}$ be given. Then the set
    $M=\prod _{i\in I}M_{i}=\{(x_{i})_{i\in I}:\,x_{i}\in M_{i}{\text{ for all }}i\in I\}\,$
$M_{i}$
As soon as one of the sets $M_{i}$ is empty, also the product is empty, because then there is no possible value for the $i$-th component. However, if all sets $M_{i}$ are not empty, then also their product is not empty, as for every index $i$ there exists at least one element $x_{i}\in M_{i}$. In a formal-axiomatic introduction of the set theory, one has to postulate that such a choice is possible. This is the content of the axiom of choice.

## Example Create referencenumber

For $n\in \mathbb {N}$, let
    $M_{n}={\left\{x\in \mathbb {N} \mid x\geq n\right\}}\,$
be the set of all natural numbers which are at least as large as $n$. This is a family of subsets of $\mathbb {N}$ indexed by the natural numbers. We have the inclusions
    $M_{n}\subseteq M_{m}{\text{ for }}n\geq m.$
The intersection
    $\bigcap _{n\in \mathbb {N} }M_{n}$
is empty, because there is no natural number which is above every other natural number.

## Example Create referencenumber

For $n\in \mathbb {N} _{+}$, let
    $\mathbb {N} n={\left\{x\in \mathbb {N} _{+}\mid x{\text{ is a multiple of }}n\right\}}\,$
be set of all positive natural numbers which are multiples of $n$. This is a family of subsets of $\mathbb {N}$ indexed by the positive natural numbers. We have the inclusions
    $\mathbb {N} n\subseteq \mathbb {N} m{\text{ for }}m{\text{ divides }}n.$
The intersection
    $\bigcap _{n\in \mathbb {N} _{+}}\mathbb {N} n$
is empty, because no positive natural number is a multiple of every positive natural number ($0$ is such a multiple).

## Example Create referencenumber

Let $x$ be a real number and let $x_{n}$ denote the rational number which consists of the digits of $x$ in the decimal system up to the $n$th digit after the point. We define the intervals
    $M_{n}=\left[x_{n},x_{n}+{\left({\frac {1}{10}}\right)}^{n}\right]\subset \mathbb {R} \,.$
These are intervals of length ${\left({\frac {1}{10}}\right)}^{n}$ and we have
    $\{x\}=\bigcap _{n\in \mathbb {N} }M_{n}\,.$
The family $M_{n}$, $n\in \mathbb {N}$, is a family of nested intervals for $x$.
    Footnotes
* ↑ In the language of predicate logic, an inclusion is the statement $\forall x(x\in N\rightarrow x\in M)$.
* ↑ It is easy to memorize the symbols: the $\cup$ for union looks like u. The intersection is written as $\cap$. The corresponding logical operations or, and have the analogous form $\vee$ and $\wedge$, respectively.
* ↑ This includes also the intersection and the union of sets, but these constructions stay inside a given fixed set. Here, we mean constructions which transcend the given sets.
* ↑ In mathematics, definitions are usually presented as such and get a number so that it is easy to refer to them. The definition contains the description of a situation where only concepts are used which have been defined before. In this situation, a new concept together with a name for it is introduced. This name is printed in a certain font, typically in italic. The new concept can be formulated without the new name, the new name is an abbreviation for the new concept. Quite often, the concepts depend on parameters, like the product set depends on its component sets. The names are often chosen arbitrarily, the meaning of the word within the mathematical context can be understood only via the explicit definition and not via its meaning in everyday life.