Università Roma Tre

Elements of set theory. Maps between sets: invective, surjective, bijective maps.
Elements of propositional logic, truth tables. Equivalence and order relations.
Combinatorics. Binomial coefficients and binomial theorem. Permutations. The Integers: divisibility, GCD and Euclidean algorithm, Bézout identity, linear congruences.
Baiscs of algebraic structures: permutation groups, abstract groups, polynomials and finite fields.
Elements of graph theory.Lattices and Boolean algebras

Giulia Maria Piacentini Cattaneo
Matematica discreta e applicazioni
Zanichelli 2008

Basics of set theory. Union, intersection, Cartesian product,
difference, complement. Set of parts of a finite whole, and its
cardinality.

Elements of logic: propositional calculus. Negation operations,
conjunction, disjunction, XOR, logical implication, double implication.
Truth tables. Logical equivalence. Tautologies and contradictions. hints
on predicates. Universal and existential quantifier.

Applications between sets. Domain, co-domain, image, counter-image.
Injective, surjective, bijective applications. Reverse application.
Operating product between applications. Identity. The set of applications
between two finite sets and its cardinality. Permutations.

Relations. Reflexive, symmetric, antisymmetric, transitive property:
order and equivalence relation. Examples of relationships. Partially together
ordered. Equivalence relations, equivalence classes, set
quotient.

Integers: divisibility and its properties. Division with the remainder. Maximum
common divider. Euclid's algorithm. Identity of Bézout, algorithm
extended Euclid's. Diophantine equations. Application of the algorithm
Euclid looking for integer solutions for the equation ax + by = c. Numbers
first. Fundamental theorem of arithmetic and Euclid's theorem.

Consistency form no. The set Z/nZ of the remainder classes modulo n. Sum and
multiplication in Z/nZ. Linear congruences. Condition for resolvability.
Description of the solutions of linear congruences. Congruence systems
and the Chinese remainder theorem. Invertible elements in Z/nZ. Euler's φ function.
Fermat's little theorem, Euler-Fermat theorem.

Combinatorics: Arrangements and combinations without repetitions, coefficients
binomials. Properties of binomial coefficients, Development of the binomial.
Arrangements and combinations with repetitions, Tartaglia triangle.

Partially ordered sets, Hasse diagrams. maximum and minimum,
maximal and minimal elements, higher and lower, upper and lower.
lattices. Properties of inf and sup in a lattice. Algebraic lattices. lattices
limited, complementary, distributive. Boolean algebras.

Piacentini Cattaneo, Matematica discreta. Zanichelli.
Delizia-Longobardi-Maj-Nicotera, Matematica Discreta, McGraw Hill.
Procesi-Rota, Elementi di algebra e matematica discreta. Accademica.

1. Linear equations and numbers
Systems of linear equations. Represent linear systems with matrix equations. Equivalent systems. Natural, integers, rational, real numbers and their properties. Pills of Graph Theory: subsets and set subtraction.

2. Matrixes and sets
Matrix with real coefficients. Square, triangular, diagonal matrixes. Transposed and symmetric matrix. Pills of Graph Theory: union and intersection.

3. Vector spaces and matrices
Matrix addition and scalar product and their properties.

4. Matrix product
Matrix product and its mathematical properties: associative and distributive. Example of how matrix product does not satisfy the commutative and simplification properties. Matrices and linear systems

5. Determinants
Formal definition of determinant and its properties. Transposed and triangular matrix determinants. Binet’s theorem.

6. Inverse of a matrix
Identity matrix. Inverse of a matrix and its properties. Cramer’s theorem.

7. Matrix rank
Definition and properties. Minor of a matrix.

8. System of linear equations.
Definition. Rouché-Capelli’s theorem. Rouché-Capelli’s method to solve a linear system.

9. Gaussian elimination and how to apply the Gaussian elimination
Elementary operation. Determinant and rank computations.

10. Geometric vectors
Vectors in 2 dimensions. Sum and scalar product of vectors. Vectors in 3 dimensions. Linear combination. Linear dependence and independence of vectors.

11. Vector spaces and Linear subspaces
Definition, examples and properties.

12. How to generate linear subspaces
Linear combination and generators.

13. Linear dependence and independence

14. Basis of a linear subspace
Basis. Dimensions. Solution set of an homogeneous system and its dimensions.

15. Vector subspaces sum and intersection
Grassmann formula.

16. Affine space
Lines in planes and space. Affine subspace.

17. Homomorphisms
Homomorphism between vector spaces. Represent an homomorphism as a matrix.

18. Image of a matrix
Properties of an homomorphism image and how to compute it. Surjective homomorphism.

19. Kernel of a matrix
Properties of an homomorphism kernel and how to compute it. Injectivity homomorphism.

20. Endomorphisms
Matrix representation of the endomorphisms. Change of basis.

21. Eigenvalues and Eigenvectors
Definition and properties. Eigenspaces. Characteristic polynomial. Diagonalizable matrix.

22. Diagonalizing a matrix
Rules and examples.

G. Accascina e V. Monti,
"Geometria"