User login
Navigation
Recent blog posts
Recent comments
- acephalgic migraine
4 weeks 6 days ago - Triangular Rudiments
4 weeks 6 days ago - Plane singularities
5 weeks 6 days ago - re: Blitz
10 weeks 2 days ago - Blitz products
10 weeks 2 days ago - need blitz basic
10 weeks 2 days ago - DNA Origami
11 weeks 12 hours ago - mazes inside space filling curves ($$$$ cut-the-knot $$$$)
11 weeks 6 days ago - Footkeys prototype
13 weeks 5 days ago - Appetizers
14 weeks 1 day ago
Random image
Who's online
Online users
Search
Discrete math background
"...we try to make predictions about Nature, to anticipate what we’ll see in places we have not yet looked. If additional observations corroborate our expectations, then we’re on the right track. Several skill sets are involved: one must know how to idealize the world, and then how to work with that idealization. Remarkably enough, our schools fail to teach either skill." -- Blake Stacey in The Necessity of Mathematics
Discrete math background
What math topics are not in pre-college cirriculum, topics everyone with an interest in math, computer science, physics or engineering should have seen?Most of what is typically not covered involves discrete math and related formalisms. This list of topics includes mostly discrete mathematics, but also includes related connections with continuous and toplological mathematics. There are many links to Wikipedia topics that you've heard about but nobody told you the formal name. I've found that the Wikipedia math topics are very well written and consistent. They go into a lot of detail that I most often don't understand, but the first paragraph of many of the math fields is usually very good, straight to the point.
Algebra
Number theory
Set theory
Analysis
Group theory
Graph theory
Probability and statistics
Topology
Logic, algorithms, and computation
Maths notation
Background and references
How do we go from nothing to useful abstractions of the real world using math?
What is discrete math?
Discrete mathematics, also called finite mathematics, is the study of mathematical structures that are fundamentally discrete in the sense of not supporting or requiring the notion of continuity. Objects studied in discrete mathematics are largely countable sets such as integers, finite graphs, and formal languages. Discrete spaces are simple examples of a topological space or similar structure, one in which the points are "isolated" from each other.
Discrete mathematics has become popular in recent decades because of its applications to computer science. Concepts and notations from discrete mathematics are useful to study or describe objects or problems in computer algorithms and programming languages.
In some mathematics curricula, finite mathematics courses cover discrete mathematical concepts for business, whereas discrete mathematics courses emphasize concepts for computer science majors, and combinatorics and other specialized courses emphasize the mathematical theory.
For contrast, see continuum, topology, and mathematical analysis.
Discrete mathematics includes the following topics:
| Logic | reasoning, truth |
| Proofs | using logic and language |
| Digital geometry | digitized models and transformations |
| Set theory | collections of elements |
| Number theory | properties of numbers, particularly integers |
| Combinatorics | combinations of arrangements of finite sets |
| Graph theory | relations between elements of finite sets |
| Algorithmics | methods of calculation |
| Computability and complexity | limitations of algorithms |
| Information theory | pattern, estimation, quantification of certainty and uncertainty |
| Partially ordered sets | ordering and arrangements of elements |
| Counting and relations | counting, comparison, and classification of elements |
Algebra
Algebra is a main branch of mathematics concerning the study of structure, relation, and quantity. Elementary algebra, often taught in pre-college math classes, provides an introduction to the basic ideas of algebra, including effects of adding and multiplying numbers, the concept of variables, definition of polynomials, polynomial factorization and determining polynomial roots.
Algebra is much broader than elementary algebra and can be generalized. In addition to working directly with numbers, algebra covers working with symbols, variables, and set elements. Addition and multiplication are abstracted as general operations, and their precise definitions lead to structures such as groups, rings and fields.
complex numbers- i2 = -1
 | Complex number notation  |
Often pre-college math classes introduce complex numbers as a sort of curiosity. They are needed to express the solutions of some polynomial equations like:
where the solution can be expressed as:
x = 0 - i = -i
But the utility and fundamental nature of the complex numbers is hard to exaggerate. Not only are they used extensively in mathematics (mathematical analysis, algebraic number theory, harmonic analysis), they are used in a wide range of applied fields including (but not limited to) signal analysis, engineering, electromagnetism, quantum physics, applied mathematics, chaos theory, and control theory.
In particular, multiplication by a complex number of modulus 1 acts as a rotation on the complex plane.
There are similarities and differences between the real number plane (an infinite set) and the complex plane (another infinite set). A point on the real plane is a 2-tuple, or coordinate pair. A point on the complex plane is a single complex numbers, z, that has a real part (component) and an imaginary part (component). Although complex numbers add just like 2-D vectors, complex number multiplication is easily defined and well-behaved.
If you multiply one complex number by another, it acts as a rotation and scaling transform (an operator) mapping one complex number to a new compex number. [To Do: Argand diagram.]
In programming, a function oftens acts as (is the same as, or impements) an operator. Operators that act on a single object (like -x = -1*x, negation) are called unary operators. Operators that act on two objects (like multiplication of two numbers) are called binary operators. Operators that act on more than two objects can always be broken down into sequences of unary or binary operations.
Richard Feynman called Euler's formula "our jewel" and "the most remarkable formula in mathematics".[2]
This form of complex number has many applications, mostly for representing rotating or oscillating things. For example the vibration of object can be (and most often is) modeled as f(t) = kei( phi(t) ), where f(t) describes the displacement (movement) over the time t. The real part of this complex number is the displacement, and the imaginary part is the phase describing the part of the cycle of vibration. It could be written as z(t) = a(t) + ib(t), where sqrt( a(t)2 + b(t)2 )1/2 = |z| = 1, but there is a very nice reason for writing it in this simple form. Here's the reason: if you want to multiply two rotations (same as applying two rotation transforms in a row), the math is dead simple -- ei(phi1) * ei(phi2) = ei(phi1 + phi1). This is easier, more clear, and the same as doing the calculation (a + bi)*(c + di) where tan-1(a/b).
"Hamilton knew that the complex numbers could be viewed as points in a plane, and he was looking for a way to do the same for points in space. Points in space can be represented by their coordinates, which are triples of numbers (3-tuples), and for many years Hamilton had known how to add and multiply triples of numbers. But he had been stuck on the problem of division: He did not know how to take the quotient of two points in space.
On October 16, 1843, Hamilton and his wife took a walk along the Royal Canal in Dublin. While they walked across Brougham Bridge (now Broom Bridge), a solution suddenly occurred to him. He could not divide triples, but he could divide quadruples. By using three of the numbers in the quadruple as the points of a coordinate in space, Hamilton could represent points in space by his new system of numbers. He then carved the basic rules for multiplication into the bridge".
- i2 = j2 = k2 = ijk = − 1
- ℍ
The multiplication of quaternions is non-commutative. This corresponds to the fact that the order of rotation in three dimensions (like "pitch then roll" and "roll then pitch") matters -- you don't end up at the same orientation if you swap the order of rotation.
There are various hypercomplex number sets that aren't fields -- they don't have division operators.
Complex analysis investigates functions of complex numbers/variables. It is useful in many branches of mathematics, including number theory and applied mathematics, and in physics.
Complex analysis is particularly concerned with the analytic functions of complex variables. Because the separable real and imaginary parts of any analytic function must satisfy Laplace's equation, complex analysis is widely applicable to two-dimensional problems in physics.
Linear algebra had its beginnings in the study of vectors in Cartesian 2-space and 3-space. A vector is a directed line segment, characterized by both its magnitude, represented by length, and its direction. Vectors can be used to represent physical entities such as forces, and they can be added to each other and multiplied with scalars, thus forming the first example of a real vector space.
Modern linear algebra has been extended to consider spaces of arbitrary or infinite dimension. A vector space of dimension n is called an n-space. Most of the useful results from 2- and 3-space can be extended to these higher dimensional spaces. Although people cannot easily visualize vectors in n-space, such vectors or n-tuples are useful in representing data. Since vectors, as n-tuples, are ordered lists of n components, it is possible to summarize and manipulate data efficiently in this framework. For example, in economics, one can create and use, say, 8-dimensional vectors or 8-tuples to represent the Gross National Productof 8 countries. One can decide to display the GNP of 8 countries for a particular year, where the countries' order is specified, for example, (United States, United Kingdom, France, Germany, Spain, India, Japan, Australia), by using a vector (v1, v2, v3, v4, v5, v6, v7, v8) where each country's GNP is in its respective position.
Linear algebra is concerned with the study linear maps (also called linear transformations), and systems of linear equations. Vector spaces are a central theme in modern mathematics; thus, linear algebra is widely used in both abstract algebra and functional analysis. Linear algebra also has a concrete representation in analytic geometry and it is generalized in operator theory. It has extensive applications in the natural sciences and the social sciences, since nonlinear models can often be approximated by linear ones.
Linear maps take elements from a linear space to another (or to itself), in a manner that is compatible with the addition and scalar multiplication given on the vector space(s). The set of all such transformations is itself a vector space. If a basis for a vector space is fixed, every linear transform can be represented by a table of numbers called a matrix. The detailed study of the properties of and algorithms acting on matrices, including determinants and eigenvectors, is considered to be part of linear algebra.
solving simultaneous linear equations
Yuri I. Manin, pg. 99 in "Mathematics and Physics" (translation of "Matematika i fizika", Birkhauser, Boston 1981)
prime sieve (Sieve of Eratosthenes)
distribution of primes
square numbers, properties of
fields
finite fields
Set theory
n-tuples (ordered lists of n terms)
Let (a1, b1) and (a2, b2) be two ordered pairs. Then the characteristic or defining property of ordered pairs is
- (a1, b1) = (a2, b2) ↔ (a1 = a2 & b1 = b2).
Ordered pairs can have other ordered pairs as entries. Hence the ordered pair enables the recursive definition of ordered n-tuples (ordered lists of n terms). For example, the ordered triple (a,b,c) can be defined as (a, (b,c) ), as one pair nested in another. This approach is mirrored in computer programming languages, where it is possible to construct a list of elements from nested ordered pairs. For example, the list (1 2 3 4 5) becomes (1, (2, (3, (4, (5, {} ))))). The Lisp programming language uses such lists as its primary data structure.
relations
An example of binary relation is the "divides" relation between the set of prime numbers P and the set of integers Z, in which every prime p is associated with every integer z that is a multiple of p, and no other. In this relation, for instance, the prime 2 is associated with numbers that include −4, 0, 6, 10, but not 1 or 9; and the prime 3 is associated with numbers that include 0, 6, and 9, but not 4 or 13.
complement
one to one mapping
sets of states, state as dimension
sphere packing
Analysis (mathematical analysis)
reflection transforms
scaling transforms (http://scienceblogs.com/sunclipse/2008/10/rotation_matrices.php)
Arithmetic viewed as symmetry transforms on integers or reals
addition of reals as a continuous translational transform
multiplication as a scaling transform
the complex plane
rotation as a product on the unit complex circle
Klein four-group (symmetry group of a rectangle)
Abelian groups
- For the integers and the operation addition "+", denoted (Z,+), the operation + combines any two integers to form a third integer, addition is associative, zero is the additive identity, every integer n has an additive inverse, −n, and the addition operation is commutative since m + n = n + m for any two integers m and n.
- Every cyclic group G is abelian, because if x, y are in G, then xy = aman = am + n = an + m = anam = yx. Thus the integers, Z, form an abelian group under addition, as do the integers modulo n, Z/nZ.
- Every ring is an abelian group with respect to its addition operation. In a commutative ring the invertible elements, or units, form an abelian multiplicative group. In particular, the real numbers are an abelian group under addition, and the nonzero real numbers are an abelian group under multiplication.
In general, matrices, even invertible matrices, do not form an abelian group under multiplication because matrix multiplication is generally not commutative. However, some groups of matrices are abelian groups under matrix multiplication - one example is the group of 2x2 rotation matrices.
Finite groups
Cayley tables of simple finite groups
The problem of determining if a partially filled square can be completed to form a Latin square is NP-complete.
The popular Sudoku puzzles are a special case of Latin squares; any solution to a Sudoku puzzle is a Latin square. Sudoku imposes the additional restriction that 3×3 subgroups must also contain the digits 1–9 (in the standard version).
Dihedral groups
The nth roots of unity form a cyclic group of order n under multiplication. e.g., 0 = z3 − 1 = (z − s0)(z − s1)(z − s2) where si = e2πi / 3 and a group of {s0,s1,s2} under multiplication is cyclic.
Properties of graphs
Probability and statistics
representative sampling
Topology
dimensions, topological dimension
of X has a refinement 
in which every point of X occurs in at most m+1 sets in , and m is the smallest such integer.
and 
).(Peano's construction of a continuous map from
onto ). Logic, algorithms, and computation
bit-wise logic
It is often useful to bound the running time of graph algorithms. Unlike most other computational problems, for a graph G = (V, E) there are two relevant parameters describing the size of the input: the number |V| of vertices in the graph and the number |E| of edges in the graph.
While a method for computing the solutions to NP-complete problems using a reasonable amount of time remains undiscovered, computer scientists and programmers still frequently encounter NP-complete problems. An expert programmer should be able to recognize an NP-complete problem so that he or she does not unknowingly waste time trying to solve a problem which so far has eluded generations of computer scientists. Instead, NP-complete problems are often addressed by using approximation algorithms in practice.
Alan Turing
Turing machines are to this day the central object of study in theory of computation. He went on to prove that there was no solution to the Entscheidungsproblem by first showing that the halting problem for Turing machines is undecidable: it is not possible to decide, in general, algorithmically whether a given Turing machine will ever halt. While his proof was published subsequent to Alonzo Church's equivalent proof in respect to his lambda calculus, Turing's work is considerably more accessible and intuitive. It was also novel in its notion of a 'Universal (Turing) Machine', the idea that such a machine could perform the tasks of any other machine. The paper also introduces the notion of definable numbers.
Discrete mathematics and proof in the high school
ZDM, The International Journal of Mathematics Education, Volume 36, Number 2 / April, 2004
"As an active branch of contemporary mathematics that is widely used in business and industry, it is clear that discrete mathematics should be an integral part of the school mathematics curriculum, and in fact some topics of discrete mathematics naturally occur in other areas of the mathematics curriculum (National Council of Teachers of Mathematics, 2000). Combinatorics, iteration and recursion, and vertex-edge graphs, for example, are mentioned explicitly as topics to be taught in all grades from kindergarden to high school. ... but there is still a substantial amount of research needed to identify in a more systematic way those topics in descrete mathematics which are most relevant for mathematics instruction. Some first steps have been taken by both mathematicians and nathematics educators, but these attempts seem sporadic and isolated (Kenney & Hirsch 1991; Rosenstein, Franzblau & Roberts, 1997, DIMACS 2001)."
Kenney, M. J. & Hirsch, C. R. (eds.) (1991). Discrete Mathematics across the Curriculum, K-12, 1991 Yearbook. Reston, VA: NCTM.
Rosenstein, J. G.; Franzblau, D. S. & Roberts, F. S. (1997). Discrete Mathematics in the Schools. Notices of the AMS, 47(6), 641–649.
DIMACS (2001) Center for Discrete Mathematics and Theoretical Computer Science: Educational Program. http://dimacs.rutgers.edu/Education/.
National Council of Teachers of Mathematics (Ed.) (2000). Principles and Standards for School Mathematics, Reston, VA: NCTM.
But pacing is not the only problem.
All too often, discussions of what should be done with American mathematics education polarize into a debate between, essentially, pushing pencils by rote and punching calculator buttons by rote. The issue touches all parents and students, yet our attempts to figure it out get nowhere. To put the matter bluntly, we leave students completely unprepared for the type of reasoning we have seen is critical for natural science — yet we sell mathematics as part of the curriculum partly because it’s important for understanding how the world works. We can change what we teach in a great many different ways, without ever delivering on that promise. To use mathematics in the natural sciences, we first decide how we wish to represent some aspect of the world in mathematical form. We then take the diagrams and equations we’ve written and manipulate them according to logical rules, and in so doing, we try to make predictions about Nature, to anticipate what we’ll see in places we have not yet looked. If additional observations corroborate our expectations, then we’re on the right track. (It’s rarely so clean-cut as that — the process can spread across thousands of people and multiple generations of activity — but that’s the gist of it.) Several skill sets are involved: one must know how to idealize the world, and then how to work with that idealization. Remarkably enough, our schools fail to teach either skill."
Comments
Post new comment