Graduation Thesis

The **Set** is a Mathematical Entity undefinable precisely: we could say that is a collection of elements of various species. We could imagine \(A\) as the set of English Alphabet letters,or the set of the people living on the Earth, or a collection of songs, etc... . We could represent sets in different ways:

Describing the property of the elements in braces:

\(A=\left\lbrace \right. \)The set of the letters of the English alphabet\(\left\rbrace \right. \)

Saying the elements one-to-one:

\(A=\left\lbrace a,b,c,d, \ldots \right\rbrace \)

The graphic representation by using the Euler-Venn Diagram:

Now if e.g. a letter *a* belongs to the set \(A\) we will write \[a\in A \,\] while if a number e.g. \(1\) does not belong to \(A\) we will write \[1\not\in A.\] The set that does not contain elements is called **Empty Set** and is represented by the symbol \(\varnothing. \)

If we consider two sets \(A\) and \(B\) and one of them, \(B\), is included in the other, \(A\), we say that \(B\) is *subset* of \(A\) and we represents it by writing \[B \subseteq A.\] We define **Power Set** of \(A\), \(\mathcal{P}(A)\), the set of all subsets of \(A\), including \(A\) and \(\varnothing\). E.g.:

\(A=\lbrace a,b \rbrace\)

\(\mathcal{P}(A)=\big\lbrace \varnothing,A,\lbrace a \rbrace, \lbrace b \rbrace \big\rbrace\)

We note that if \(A\) has \(n\) elements, \(\mathcal{P}(A)\) has \(2^{n}\) elements.

It’s possible to define some operators over the sets that are: Union, Intersection,Complement and Cartesian Product.

The

**Union**represented by the symbol \(\cup\) is the operator that given two sets \(A\) and \(B\) returns the set \(A \cup B\) that contains the elements of both \(A\) and \(B\).

E.g.:\( A=\lbrace a,b\rbrace\)

\( B=\lbrace c,d \rbrace \)

\(A \cup B =\lbrace a,b,c,d \rbrace\)The

**Intersection**represented by the symbol \(\cap\) is the operator that given two sets \(A\) and \(B\) returns the set \(A \cap B\) that contains the elements that are in common between \(A\) and \(B\).

E.g.:\( \ \ \ \ \ A=\lbrace a,b\rbrace\)

\(\ \ \ \ \ \ \ \ \ \ \ B=\lbrace a,b,c,d \rbrace \)

\(A \cap B =\lbrace a,b \rbrace\)The

**Complement**represented by the symbol \(\setminus\) is the operator that given two sets \(A\) and \(B\) returns the set \(A \setminus B\) that contains the elements of \(A\) that don’t belong to \(B\).

E.g.:\(\ \ \ \ \ \ \ \ \ \ \ A=\lbrace a,b,c,d \rbrace \)

\( \ \ \ \ \ B=\lbrace a,b\rbrace\)

\(A \setminus B =\lbrace c,d \rbrace\)The

**Cartesian Product**represented by the symbol \(\times\) is the operator that given two sets \(A\) and \(B\) returns the set \(A \times B\) that is the set of the ordered pairs obtainable taking the first element by \(A\) and the second one by \(B\).

\( A=\lbrace a,b\rbrace\)

\( B=\lbrace c,d \rbrace \)

\(A \times B =\lbrace (a,c),(a,d),(b,c),(b,d) \rbrace\)

Starting by the Cartesian Product we will define the Relations.

Let \(A\) and \(B\) be two sets and \(A \times B \) their Cartesian Product, we define **Relation** a subset \(\mathcal{R}\) of \(A \times B \).

E.g.:

\(A=\lbrace0,1,2\rbrace\)

\(B=\lbrace-1,1\rbrace\)

\(A \times B = \lbrace(0,-1),(0,1),(1,-1),(1,1),(2,-1),(2,1) \rbrace\)

we take e.g.: \(\mathcal{R}= \lbrace(0,1),(2,-1) \rbrace\)

and if we look we could say that this is the set of the pairs whose sum is 1 and so:

\(\mathcal{R}= \lbrace (a,b) \in A\times B \mid a+b=1 \rbrace\)

or we could say that \(a\mathcal{R} b \Leftrightarrow a+b=1\).

If we take \(B=A\) then \(A\times A=A^{2}\) and the relation \( \mathcal{R}\) is a binary relation. Some properties of binary relations:

**Reflexive**\[\forall a \in A \ \ \ \ a \mathcal{R} a\]**Symmetric**\[\forall a,b \in A \ \ if \ a \mathcal{R} b \Rightarrow b \mathcal{R} a\]**Antisymmetric**\[\forall a,b \in A \ \ if \ a \mathcal{R} b \ and \ b \mathcal{R} a \Rightarrow a=b\]**Transitive**\[\forall a,b,c \in A \ \ if \ a \ \mathcal{R} b \ and \ b \mathcal{R} c \Rightarrow a \mathcal{R} c\]

and so we could define

**Equivalence Relation** if it is Reflexive,Symmetric and Transitive

**Order Relation** if it is Reflexive, Antisymmetric and Transitive.

In particular, let \(\mathcal{R}\) be an Equivalence Relation over the set \(A\), we could regroup the elements that are related each other in the same class with an unique representative, i.e. \(x\), and this is called *equivalence class of the element \(x\)*, denoted by \([x]\). Finally we call **Quotient Set** :

\(A_{/\mathcal{R}}=\big\lbrace[x] \ \ | \ \ x \in A \big\rbrace\)

The quotient set will play a main role in the construction of the cryptography over particular finite sets.

## Share on Social Media