Discrete mathematics

Discrete mathematicsis the study ofmathematical structuresthat can be considered "discrete" (in a way analogous todiscrete variables,having abijectionwith the set ofnatural numbers) rather than "continuous" (analogously tocontinuous functions). Objects studied in discrete mathematics includeintegers,graphs,andstatementsinlogic.^[1]^[2]^[3]By contrast, discrete mathematics excludes topics in "continuous mathematics" such asreal numbers,calculusorEuclidean geometry.Discrete objects can often beenumeratedbyintegers;more formally, discrete mathematics has been characterized as the branch of mathematics dealing withcountable sets^[4](finite sets or sets with the samecardinalityas the natural numbers). However, there is no exact definition of the term "discrete mathematics".^[5]

The set of objects studied in discrete mathematics can be finite or infinite. The termfinite mathematicsis sometimes applied to parts of the field of discrete mathematics that deals with finite sets, particularly those areas relevant to business.

Research in discrete mathematics increased in the latter half of the twentieth century partly due to the development ofdigital computerswhich operate in "discrete" steps and store data in "discrete" bits. Concepts and notations from discrete mathematics are useful in studying and describing objects and problems in branches ofcomputer science,such ascomputer algorithms,programming languages,cryptography,automated theorem proving,andsoftware development.Conversely, computer implementations are significant in applying ideas from discrete mathematics to real-world problems.

Although the main objects of study in discrete mathematics are discrete objects,analyticmethods from "continuous" mathematics are often employed as well.

In university curricula, discrete mathematics appeared in the 1980s, initially as a computer science support course; its contents were somewhat haphazard at the time. The curriculum has thereafter developed in conjunction with efforts byACMandMAAinto a course that is basically intended to developmathematical maturityin first-year students; therefore, it is nowadays a prerequisite for mathematics majors in some universities as well.^[6]^[7]Some high-school-level discrete mathematics textbooks have appeared as well.^[8]At this level, discrete mathematics is sometimes seen as a preparatory course, likeprecalculusin this respect.^[9]

TheFulkerson Prizeis awarded for outstanding papers in discrete mathematics.

Topics in discrete mathematics[edit]

Theoretical computer science[edit]

Computational geometryapplies computeralgorithmsto representations ofgeometricalobjects.

Theoretical computer science includes areas of discrete mathematics relevant to computing. It draws heavily ongraph theoryandmathematical logic.Included within theoretical computer science is the study of algorithms and data structures.Computabilitystudies what can be computed in principle, and has close ties to logic, while complexity studies the time, space, and other resources taken by computations.Automata theoryandformal languagetheory are closely related to computability.Petri netsandprocess algebrasare used to model computer systems, and methods from discrete mathematics are used in analyzingVLSIelectronic circuits.Computational geometryapplies algorithms to geometrical problems and representations ofgeometricalobjects, whilecomputer image analysisapplies them to representations of images. Theoretical computer science also includes the study of various continuous computational topics.

Information theory[edit]

TheASCIIcodes for the word "Wikipedia", given here inbinary,provide a way of representing the word ininformation theory,as well as for information-processingalgorithms.

Information theory involves the quantification ofinformation.Closely related iscoding theorywhich is used to design efficient and reliable data transmission and storage methods. Information theory also includes continuous topics such as:analog signals,analog coding,analog encryption.

Logic[edit]

Logic is the study of the principles of valid reasoning andinference,as well as ofconsistency,soundness,andcompleteness.For example, in most systems of logic (but not inintuitionistic logic)Peirce's law(((P→Q)→P)→P) is a theorem. For classical logic, it can be easily verified with atruth table.The study ofmathematical proofis particularly important in logic, and has accumulated toautomated theorem provingandformal verificationof software.

Logical formulasare discrete structures, as areproofs,which form finitetrees^[10]or, more generally,directed acyclic graphstructures^[11]^[12](with eachinference stepcombining one or morepremisebranches to give a single conclusion). Thetruth valuesof logical formulas usually form a finite set, generally restricted to two values:trueandfalse,but logic can also be continuous-valued, e.g.,fuzzy logic.Concepts such as infinite proof trees or infinite derivation trees have also been studied,^[13]e.g.infinitary logic.

Set theory[edit]

Set theory is the branch of mathematics that studiessets,which are collections of objects, such as {blue, white, red} or the (infinite) set of allprime numbers.Partially ordered setsand sets with otherrelationshave applications in several areas.

In discrete mathematics,countable sets(includingfinite sets) are the main focus. The beginning of set theory as a branch of mathematics is usually marked byGeorg Cantor's work distinguishing between different kinds ofinfinite set,motivated by the study of trigonometric series, and further development of the theory of infinite sets is outside the scope of discrete mathematics. Indeed, contemporary work indescriptive set theorymakes extensive use of traditional continuous mathematics.

Combinatorics[edit]

Combinatorics studies the way in which discrete structures can be combined or arranged. Enumerative combinatoricsconcentrates on counting the number of certain combinatorial objects - e.g. thetwelvefold wayprovides a unified framework for countingpermutations,combinationsandpartitions. Analytic combinatoricsconcerns the enumeration (i.e., determining the number) of combinatorial structures using tools fromcomplex analysisandprobability theory.In contrast with enumerative combinatorics which uses explicit combinatorial formulae andgenerating functionsto describe the results, analytic combinatorics aims at obtainingasymptotic formulae. Topological combinatoricsconcerns the use of techniques fromtopologyandalgebraic topology/combinatorial topologyincombinatorics. Design theory is a study ofcombinatorial designs,which are collections of subsets with certainintersectionproperties. Partition theorystudies various enumeration and asymptotic problems related tointeger partitions,and is closely related toq-series,special functionsandorthogonal polynomials.Originally a part ofnumber theoryandanalysis,partition theory is now considered a part of combinatorics or an independent field. Order theoryis the study ofpartially ordered sets,both finite and infinite.

Graph theory[edit]

Graph theoryhas close links togroup theory.Thistruncated tetrahedrongraph is related to thealternating groupA₄.

Graph theory, the study ofgraphsandnetworks,is often considered part of combinatorics, but has grown large enough and distinct enough, with its own kind of problems, to be regarded as a subject in its own right.^[14]Graphs are one of the prime objects of study in discrete mathematics. They are among the most ubiquitous models of both natural and human-made structures. They can model many types of relations and process dynamics in physical, biological and social systems. In computer science, they can represent networks of communication, data organization, computational devices, the flow of computation, etc. In mathematics, they are useful in geometry and certain parts oftopology,e.g.knot theory.Algebraic graph theoryhas close links with group theory andtopological graph theoryhas close links totopology.There are alsocontinuous graphs;however, for the most part, research in graph theory falls within the domain of discrete mathematics.

Number theory[edit]

Number theory is concerned with the properties of numbers in general, particularlyintegers.It has applications tocryptographyandcryptanalysis,particularly with regard tomodular arithmetic,diophantine equations,linear and quadratic congruences, prime numbers andprimality testing.Other discrete aspects of number theory includegeometry of numbers.Inanalytic number theory,techniques from continuous mathematics are also used. Topics that go beyond discrete objects includetranscendental numbers,diophantine approximation,p-adic analysisandfunction fields.

Algebraic structures[edit]

Algebraic structuresoccur as both discrete examples and continuous examples. Discrete algebras include:Boolean algebraused inlogic gatesand programming;relational algebraused indatabases;discrete and finite versions ofgroups,ringsandfieldsare important inalgebraic coding theory;discretesemigroupsandmonoidsappear in the theory offormal languages.

Discrete analogues of continuous mathematics[edit]

There are many concepts and theories in continuous mathematics which have discrete versions, such asdiscrete calculus,discrete Fourier transforms,discrete geometry,discrete logarithms,discrete differential geometry,discrete exterior calculus,discrete Morse theory,discrete optimization,discrete probability theory,discrete probability distribution,difference equations,discrete dynamical systems,anddiscrete vector measures.

Calculus of finite differences, discrete analysis, and discrete calculus[edit]

Indiscrete calculusand thecalculus of finite differences,afunctiondefined on an interval of theintegersis usually called asequence.A sequence could be a finite sequence from a data source or an infinite sequence from adiscrete dynamical system.Such a discrete function could be defined explicitly by a list (if its domain is finite), or by a formula for its general term, or it could be given implicitly by arecurrence relationordifference equation.Difference equations are similar todifferential equations,but replacedifferentiationby taking the difference between adjacent terms; they can be used to approximate differential equations or (more often) studied in their own right. Many questions and methods concerning differential equations have counterparts for difference equations. For instance, where there areintegral transformsinharmonic analysisfor studying continuous functions or analogue signals, there arediscrete transformsfor discrete functions or digital signals. As well asdiscrete metric spaces,there are more generaldiscrete topological spaces,finite metric spaces,finite topological spaces.

Thetime scale calculusis a unification of the theory ofdifference equationswith that ofdifferential equations,which has applications to fields requiring simultaneous modelling of discrete and continuous data. Another way of modeling such a situation is the notion ofhybrid dynamical systems.

Discrete geometry[edit]

Discrete geometryand combinatorial geometry are about combinatorial properties ofdiscrete collectionsof geometrical objects. A long-standing topic in discrete geometry istiling of the plane.

Inalgebraic geometry,the concept of a curve can be extended to discrete geometries by taking thespectraofpolynomial ringsoverfinite fieldsto be models of theaffine spacesover that field, and lettingsubvarietiesor spectra of other rings provide the curves that lie in that space. Although the space in which the curves appear has a finite number of points, the curves are not so much sets of points as analogues of curves in continuous settings. For example, every point of the form $V(x-c)\subset \operatorname {Spec} K[x]=\mathbb {A} ^{1}$ for $K$ a field can be studied either as $\operatorname {Spec} K[x]/(x-c)\cong \operatorname {Spec} K$ ,a point, or as the spectrum $\operatorname {Spec} K[x]_{(x-c)}$ of thelocal ring at (x-c),a point together with a neighborhood around it. Algebraic varieties also have a well-defined notion oftangent spacecalled theZariski tangent space,making many features of calculus applicable even in finite settings.

Discrete modelling[edit]

Inapplied mathematics,discrete modellingis the discrete analogue ofcontinuous modelling.In discrete modelling, discrete formulae are fit todata.A common method in this form of modelling is to userecurrence relation.Discretizationconcerns the process of transferring continuous models and equations into discrete counterparts, often for the purposes of making calculations easier by using approximations.Numerical analysisprovides an important example.

Challenges[edit]

The history of discrete mathematics has involved a number of challenging problems which have focused attention within areas of the field. In graph theory, much research was motivated by attempts to prove thefour color theorem,first stated in 1852, but not proved until 1976 (by Kenneth Appel and Wolfgang Haken, using substantial computer assistance).^[15]

Inlogic,thesecond problemonDavid Hilbert's list of openproblemspresented in 1900 was to prove that theaxiomsofarithmeticareconsistent.Gödel's second incompleteness theorem,proved in 1931, showed that this was not possible – at least not within arithmetic itself.Hilbert's tenth problemwas to determine whether a given polynomialDiophantine equationwith integer coefficients has an integer solution. In 1970,Yuri Matiyasevichproved that thiscould not be done.

The need tobreakGerman codes inWorld War IIled to advances incryptographyandtheoretical computer science,with thefirst programmable digital electronic computerbeing developed at England'sBletchley Parkwith the guidance ofAlan Turingand his seminal work, On Computable Numbers.^[16]TheCold Warmeant that cryptography remained important, with fundamental advances such aspublic-key cryptographybeing developed in the following decades. Thetelecommunicationindustry has also motivated advances in discrete mathematics, particularly in graph theory andinformation theory.Formal verificationof statements in logic has been necessary forsoftware developmentofsafety-critical systems,and advances inautomated theorem provinghave been driven by this need.

Computational geometryhas been an important part of thecomputer graphicsincorporated into modernvideo gamesandcomputer-aided designtools.

Several fields of discrete mathematics, particularly theoretical computer science, graph theory, andcombinatorics,are important in addressing the challengingbioinformaticsproblems associated with understanding thetree of life.^[17]

Currently, one of the most famous open problems in theoretical computer science is theP = NP problem,which involves the relationship between thecomplexity classes PandNP.TheClay Mathematics Institutehas offered a $1 millionUSDprize for the first correct proof, along with prizes forsix other mathematical problems.^[18]

References[edit]

^Richard Johnsonbaugh,Discrete Mathematics,Prentice Hall, 2008.
^Franklin, James(2017)."Discrete and continuous: a fundamental dichotomy in mathematics".Journal of Humanistic Mathematics.7(2): 355–378.doi:10.5642/jhummath.201702.18.S2CID 6945363.Retrieved30 June2021.
^"Discrete Structures: What is Discrete Math?".cse.buffalo.edu.Retrieved16 November2018.
^Biggs, Norman L.(2002),Discrete mathematics,Oxford Science Publications (2nd ed.), The Clarendon Press Oxford University Press, p. 89,ISBN 9780198507178,MR 1078626,Discrete Mathematics is the branch of Mathematics in which we deal with questions involving finite or countably infinite sets.
^Hopkins, Brian, ed. (2009).Resources for Teaching Discrete Mathematics: Classroom Projects, History Modules, and Articles.Mathematical Association of America.ISBN 978-0-88385-184-5.
^Levasseur, Ken; Doerr, Al.Applied Discrete Structures.p. 8.
^Geoffrey Howson, Albert, ed. (1988).Mathematics as a Service Subject.Cambridge University Press. pp. 77–78.ISBN 978-0-521-35395-3.
^Rosenstein, Joseph G.Discrete Mathematics in the Schools.American Mathematical Society. p. 323.ISBN 978-0-8218-8578-9.
^"UCSMP".uchicago.edu.
^Troelstra, A.S.; Schwichtenberg, H. (2000-07-27).Basic Proof Theory.Cambridge University Press. p. 186.ISBN 978-0-521-77911-1.
^Buss, Samuel R. (1998).Handbook of Proof Theory.Elsevier. p. 13.ISBN 978-0-444-89840-1.
^Baader, Franz; Brewka, Gerhard; Eiter, Thomas (2001-10-16).KI 2001: Advances in Artificial Intelligence: Joint German/Austrian Conference on AI, Vienna, Austria, September 19-21, 2001. Proceedings.Springer. p. 325.ISBN 978-3-540-42612-7.
^Brotherston, J.; Bornat, R.; Calcagno, C. (January 2008). "Cyclic proofs of program termination in separation logic".ACM SIGPLAN Notices.43(1): 101–112.doi:10.1145/1328897.1328453.
^Mohar, Bojan;Thomassen, Carsten(2001).Graphs on Surfaces.Johns Hopkins University Press.ISBN 978-0-8018-6689-0.OCLC 45102952.
^^a ^bWilson, Robin(2002).Four Colors Suffice.London: Penguin Books.ISBN 978-0-691-11533-7.
^Hodges, Andrew(1992).Alan Turing: The Enigma.Random House.
^Hodkinson, Trevor R.; Parnell, John A. N. (2007).Reconstruction the Tree of Life: Taxonomy And Systematics of Large And Species Rich Taxa.CRC Press. p. 97.ISBN 978-0-8493-9579-6.
^"Millennium Prize Problems".2000-05-24.Retrieved2008-01-12.

External links[edit]

Discrete mathematics Archived2011-08-29 at theWayback Machineat the utk.edu Mathematics Archives, providing links to syllabi, tutorials, programs, etc.
Iowa Central: Electrical Technologies ProgramDiscrete mathematics forElectrical engineering.

[1] Richard Johnsonbaugh,Discrete Mathematics,Prentice Hall, 2008.

[2] Franklin, James(2017)."Discrete and continuous: a fundamental dichotomy in mathematics".Journal of Humanistic Mathematics.7(2): 355–378.doi:10.5642/jhummath.201702.18.S2CID 6945363.Retrieved30 June2021.

[3] "Discrete Structures: What is Discrete Math?".cse.buffalo.edu.Retrieved16 November2018.

[4] Biggs, Norman L.(2002),Discrete mathematics,Oxford Science Publications (2nd ed.), The Clarendon Press Oxford University Press, p. 89,ISBN 9780198507178,MR 1078626,Discrete Mathematics is the branch of Mathematics in which we deal with questions involving finite or countably infinite sets.

[5] Hopkins, Brian, ed. (2009).Resources for Teaching Discrete Mathematics: Classroom Projects, History Modules, and Articles.Mathematical Association of America.ISBN 978-0-88385-184-5.

[LevasseurDoerr-6] Levasseur, Ken; Doerr, Al.Applied Discrete Structures.p. 8.

[Howson1988-7] Geoffrey Howson, Albert, ed. (1988).Mathematics as a Service Subject.Cambridge University Press. pp. 77–78.ISBN 978-0-521-35395-3.

[Rosenstein-8] Rosenstein, Joseph G.Discrete Mathematics in the Schools.American Mathematical Society. p. 323.ISBN 978-0-8218-8578-9.

[9] "UCSMP".uchicago.edu.

[10] Troelstra, A.S.; Schwichtenberg, H. (2000-07-27).Basic Proof Theory.Cambridge University Press. p. 186.ISBN 978-0-521-77911-1.

[11] Buss, Samuel R. (1998).Handbook of Proof Theory.Elsevier. p. 13.ISBN 978-0-444-89840-1.

[12] Baader, Franz; Brewka, Gerhard; Eiter, Thomas (2001-10-16).KI 2001: Advances in Artificial Intelligence: Joint German/Austrian Conference on AI, Vienna, Austria, September 19-21, 2001. Proceedings.Springer. p. 325.ISBN 978-3-540-42612-7.

[13] Brotherston, J.; Bornat, R.; Calcagno, C. (January 2008). "Cyclic proofs of program termination in separation logic".ACM SIGPLAN Notices.43(1): 101–112.doi:10.1145/1328897.1328453.

[14] Mohar, Bojan;Thomassen, Carsten(2001).Graphs on Surfaces.Johns Hopkins University Press.ISBN 978-0-8018-6689-0.OCLC 45102952.

[4colors-15] Wilson, Robin(2002).Four Colors Suffice.London: Penguin Books.ISBN 978-0-691-11533-7.

[16] Hodges, Andrew(1992).Alan Turing: The Enigma.Random House.

[17] Hodkinson, Trevor R.; Parnell, John A. N. (2007).Reconstruction the Tree of Life: Taxonomy And Systematics of Large And Species Rich Taxa.CRC Press. p. 97.ISBN 978-0-8493-9579-6.

[CMI_Millennium_Prize_Problems-18] "Millennium Prize Problems".2000-05-24.Retrieved2008-01-12.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

v t e Majormathematicsareas
History Timeline Future Lists Glossary
Foundations	Category theory Information theory Mathematical logic Philosophy of mathematics Set theory Type theory
Algebra	Abstract Commutative Elementary Group theory Linear Multilinear Universal Homological
Analysis	Calculus Real analysis Complex analysis Hypercomplex analysis Differential equations Functional analysis Harmonic analysis Measure theory
Discrete	Combinatorics Graph theory Order theory
Geometry	Algebraic Analytic Arithmetic Differential Discrete Euclidean Finite
Number theory	Arithmetic Algebraic number theory Analytic number theory Diophantine geometry
Topology	General Algebraic Differential Geometric Homotopy theory
Applied	Engineering mathematics Mathematical biology Mathematical chemistry Mathematical economics Mathematical finance Mathematical physics Mathematical psychology Mathematical sociology Mathematical statistics Probability Statistics Systems science Control theory Game theory Operations research
Computational	Computer science Theory of computation Computational complexity theory Numerical analysis Optimization Computer algebra
Related topics	Mathematicians lists Informal mathematics Films about mathematicians Recreational mathematics Mathematics and art Mathematics education
Mathematics portal Category Commons WikiProject

Authority control databases
International	FAST
National	Germany Israel United States Japan Czech Republic
Other	Encyclopedia of Modern Ukraine