Syllabus of USMT102202

Prerequisites

(i) Set Theory: Set, subset, union and intersection of two sets, empty set, universal set, complement of a set, De Morgan’s laws, cartesian product of two sets.
(ii) Relations, functions,
(iii) First Principle of finite induction,
(iv) Permutations and combinations, [math]^nC_r[/math], [math]^nP_r[/math]
(v) Complex numbers: Addition and multiplication of complex numbers, modulus, amplitude and conjugate of a complex number.

Unit 1: Integers and divisibility

(a) (i) Statements of well-ordering property of non-negative integers.
(ii) Principle of finite induction (first and second) as a consequence of well-ordering property.
(iii)Binomial Theorem for non-negative exponents, Pascal Triangle. Recursive definitions.
(b) Divisibility in integers, division algorithm, greatest common divisor (g.c.d.) and least common multiple (l.c.m.) of two integers, basic properties of g.c.d. such as existence and uniqueness of g.c.d. of integers a and b and that the g.c.d. can be expressed as ma + nb for some m, n [math]\in\mathbb{Z}[/math], Euclidean algorithm.
(c) Primes, Euclid’s lemma, Fundamental Theorem of Arithmetic.

Unit 2: Functions and Counting Principles

(a) (i) Review of functions, domain, codomain and range of a function, composite functions,
(ii) Direct image f(A) and inverse image f -1(B) of a function f. (iii) Injective, surjective, bijective functions. Composite of injective, surjective. bijective functions are injective, surjective and bijective respectively.
(iv) Invertible functions and finding their inverse. Bijective functions are invertible and conversely.
(v) Examples of functions including constant, identity, projection, inclusion. (b) Binary operation as a function, properties, examples.
(c) (i) There is no injection from to if n > m, = {1,2,.... n}.
(ii) Pigeon Hole Principle and its applications,
(iii) Finite and infinite sets, cardinality of a finite set.
(iv) The number of subsets of a finite set having n elements is 2n.

Unit 3: Integers and Congruences

(a) (i) The set of primes is infinite.
(ii)The set of primes of the type 4n - 1 (or 4n +1 or 6n - 1) is infinite.
(b) Congruences: Definition, and elementary properties.
(c) Euler- function, invert ible elements modulo n
(d) (i) Euler’s Theorem (without proof),
(ii) Fermat’s Little Theorem,
(iii) Wilson’s Theorem,
(iv) Applications: Solution of linear congruences.

Unit 4: Principles of Counting and Equivalence Relations

(a) (i) Addition and multiplication Principles. (ii) Counting sets of pairs.
(b) Cartesian product of n sets.
(c) Partition of a set, S(n, k), the Sterling numbers of second kind defined in terms of partitions. Properties of S(n, k).
(d) (i) Equivalence relation. Equivalence classes. Properties. Examples including the relation modulo n on .
(ii) An equivalence relation induces partition of a set and a partition of a set defines an equivalence relation.
(e) (i) Equivalent sets, countable, uncountable sets.
(ii) Examples of countable sets including (the set of positive rational numbers),
(iii) Examples of uncountable sets including (0. 1), , (a , b).
(iv) A set is not equivalent to its power set.

Unit 5: Principles of Counting and permutations

(a) Distribution of objects, multinomial numbers, combinatorial interpretations, multinomial theorem.
(b) Inclusion and Exclusion (Sieve) Principle.
(c) (i) Number of funcions from a finite set X to a finite set Y.
(ii) Number of injective functions from a finite set X to a finite set Y. where |X | |Y|.
(iii) Number of surjective functions from a finite set X to a finite set Y, where |X | |Y|.
(d) Permutaions:
(i) Permutations on n symbols. The set Sn and the number of permutations in Sn is n !.
(ii) Composition of two permutations, as a binary operation in Sn composition of permutations is non-commutative if n 3.
(iii) Cycles and transpositions, representation of a permutation as product of disjoint cycles. Listing permutations in S3, S4, etc.
(iv) Sign of a permutation, sign of transposition is -1, multiplicative property of sign, odd and evein permutations, number of even permutations in Sn is .
(v) Partition of a positive integer, its relation to decomposition of a permutation as product of disjoint cycles, conjugate of a permutation.
(e) (i) Derangements on n symbols, dn, the number of derangements of {1, 2,...,n}.
(ii) Arithmetic applications including Euler -function.
(f) Recurrence relations: formulation and solutions. Solving homogeneous linear recurrence relations.

Unit 6: Polynomials

(i)The set F[X] of polynomials in one variable over F, where F = . Addition, Multiplication of two polynomials, degree of a polynomial, basic properties.
(ii) Division algorithm in F[X] (without proof) and g.c.d. of two polynomials, and its basic properties (without proof), Euclidean algorithm (without proof), applications.
(iii) Roots of a polynomial, multiplicity of a root, Factor theorem. A polynomial of degree n over F has at. most n roots. Necessary condition for . A to be a root, of polynomial in
(iv) Statement of Fundamental Theorem of Algebra and its elementary consequences.
(v) Complex number z is a root of a polynomial over if and only if its conjugatge is a root of .
(vi) Polynomials in can be expressed as a product of linear and quadratic polyno­mials in .
(vii) Statement of De Moivre’s Theorem, nth roots of unity, Primitive nUl roots of unity, nth roots of a complex number .

z