Chapter 14: Mathematical Foundations - Revision history

Daniel Robbins: /* Language Recognition */

2015-08-28T18:14:55Z

‎Language Recognition

Daniel Robbins: /* Rings */

2015-08-28T18:11:48Z

‎Rings

Daniel Robbins: /* Rings */

2015-08-28T18:10:08Z

‎Rings

Daniel Robbins: /* Rings */

2015-08-28T18:06:15Z

‎Rings

Daniel Robbins: /* Rings */

2015-08-28T18:03:57Z

‎Rings

Daniel Robbins: /* Group */

2015-08-28T18:02:49Z

‎Group

Daniel Robbins: /* Prime Number, GCD */

2015-08-28T17:55:22Z

‎Prime Number, GCD

Daniel Robbins: /* Divisibility */

2015-08-28T17:43:13Z

‎Divisibility

Daniel Robbins: /* Number Theory */

2015-08-28T17:35:14Z

‎Number Theory

Daniel Robbins: /* Numerical Precision, Accuracy, and Errors */

2015-08-28T17:00:40Z

‎Numerical Precision, Accuracy, and Errors

@@ Line 1,306: / Line 1,306: @@
 [[File:Chomsky Hierarchy of Grammars.jpg|thumb|200px|frame|Figure 14.23: Chomsky Hierarchy of Grammars]]
-Context-Sensitive Grammar: All fragments in
+''Context-Sensitive Grammar'': All fragments in
 the RHS are either longer than the corresponding
 fragments in the LHS or empty, i.e., if b → a, then |b| < |a| or a = ∅.

← Older revision		Revision as of 18:11, 28 August 2015
Line 1,779:		Line 1,779:
	}}{{ReferenceList}}		}}{{ReferenceList}}
	}}		}}
		+	{{EndSection\|title=Acknowledgments\|body=
		+
		+	The author thankfully acknowledges the contribution
		+	of Prof. Arun Kumar Chatterjee, Ex-Head,
		+	Department of Mathematics, Manipur University,
		+	India, and Prof. Devadatta Sinha, Ex-Head,
		+	Department of Computer Science and Engineering,
		+	University of Calcutta, India, in preparing
		+	this chapter on Mathematical Foundations.}}

← Older revision		Revision as of 18:10, 28 August 2015
Line 1,753:		Line 1,753:
	simply −''a''/''b'', and the multiplicative inverse is ''b''/''a''		simply −''a''/''b'', and the multiplicative inverse is ''b''/''a''
	provided that ''a'' ≠ 0.		provided that ''a'' ≠ 0.
		+
		+	{{EndSection\|title=References\|body=
		+	{{reference
		+	\|number=1
		+	\|author=K. Rosen
		+	\|article=
		+	\|publication=Discrete Mathematics and Its Applications
		+	\|edition=7th ed.
		+	\|publisher=McGraw-Hill
		+	\|issue=
		+	\|date=2011
		+	\|part=
		+	\|link=
		+	}}{{reference
		+	\|number=2
		+	\|author=E.W. Cheney and D.R. Kincaid
		+	\|article=
		+	\|publication=Numerical Mathematics and Computing
		+	\|edition=6th ed.
		+	\|publisher=Brooks/Cole
		+	\|issue=
		+	\|date=2007
		+	\|part=
		+	\|link=
		+	}}{{ReferenceList}}
		+	}}

← Older revision		Revision as of 18:06, 28 August 2015
Line 1,733:		Line 1,733:
	is a commutative or Abelian ring. The ring has 1		is a commutative or Abelian ring. The ring has 1
	as its identity element.		as its identity element.
		+
		+	Let’s note that the second operation may not
		+	have an identity element, nor do we need to find
		+	an inverse for every element with respect to this
		+	second operation. As for what distributive means,
		+	intuitively it is what we do in elementary mathematics
		+	when performing the following change:
		+	a * (b + c) = (a * b) + (a * c).
		+
		+	A field is a ring for which the elements of the
		+	set, excluding 0, form an Abelian group with the
		+	second operation.
		+
		+	A simple example of a field is the field of rational
		+	numbers (R, +, *) with the usual addition
		+	and multiplication operations. The numbers of
		+	the format ''a''/''b'' ∈ R, where ''a'', ''b'' are integers and
		+	''b'' ≠ 0. The additive inverse of such a fraction is
		+	simply −''a''/''b'', and the multiplicative inverse is ''b''/''a''
		+	provided that ''a'' ≠ 0.

@@ Line 1,726: / Line 1,726: @@
 a • (b + c) = (a • b) + (a • c) holds. Further, if
 • is commutative, then the ring is said to be commutative.
-If there is an identity element for the • operation, then the ring is said to have an identity
+If there is an identity element for the • operation, then the ring is said to have an identity.

← Older revision		Revision as of 18:02, 28 August 2015
Line 1,688:		Line 1,688:
	generate ''S'' and their inverses. It is the smallest subgroup		generate ''S'' and their inverses. It is the smallest subgroup
	of ''G'' containing ''S''.		of ''G'' containing ''S''.
		+
		+	For example, let ''G'' be the Abelian group whose
		+	elements are ''G' = {0, 2, 4, 6, 1, 3, 5, 7} and whose
		+	group operation is addition modulo 8. This group
		+	has a pair of nontrivial subgroups: ''J'' = {0, 4} and
		+	''H'' = {0, 2, 4, 6}, where ''J'' is also a subgroup of ''H''.
		+
		+	In group theory, a cyclic group is a group that
		+	can be generated by a single element, in the
		+	sense that the group has an element ''a'' (called the
		+	''generator'' of the group) such that, when written
		+	multiplicatively, every element of the group is a
		+	power of ''a''.
		+	A group G is cyclic if G = {a<sup>n</sup> for any integer n}.
		+
		+	Since any group generated by an element in a
		+	group is a subgroup of that group, showing that
		+	the only subgroup of a group G that contains a is
		+	G itself suffices to show that G is cyclic.
		+
		+	For example, the group ''G'' = {0, 2, 4, 6, 1, 3, 5,
		+	7}, with respect to addition modulo 8 operation,
		+	is cyclic. The subgroups ''J'' = {0, 4} and ''H'' = {0, 2,
		+	4, 6} are also cyclic.
		+
		+	===Rings===
		+
		+	If we take an Abelian group and define a second
		+	operation on it, a new structure is found that is
		+	different from just a group. If this second operation
		+	is associative and is distributive over the
		+	first, then we have a ring.
		+
		+	A ring is a triple of the form (S, +, •), where (S,
		+	+) is an Abelian group, (S, •) is a semigroup, and
		+	• is distributive over +; i.e., “ a, b, c ∈ S, the equation
		+	a • (b + c) = (a • b) + (a • c) holds. Further, if
		+	• is commutative, then the ring is said to be commutative.
		+	If there is an identity element for the • operation, then the ring is said to have an identity

← Older revision		Revision as of 17:55, 28 August 2015
Line 1,618:		Line 1,618:
	prime if all possible pairs i<sub>h</sub>, i<sub>k</sub>, h ≠ k drawn from		prime if all possible pairs i<sub>h</sub>, i<sub>k</sub>, h ≠ k drawn from
	the set X are relatively prime.		the set X are relatively prime.
		+
		+	==Algebraic Structures==
		+
		+	This section introduces a few representations
		+	used in higher algebra. An algebraic structure
		+	consists of one or two sets closed under some
		+	operations and satisfying a number of axioms,
		+	including none.
		+
		+	For example, group, monoid, ring, and lattice
		+	are examples of algebraic structures. Each of
		+	these is defined in this section.
		+
		+	===Group===
		+
		+	A set S closed under a binary operation • forms a
		+	group if the binary operation satisfies the following
		+	four criteria:
		+
		+	* Associative: ∀a, b, c ∈ S, the equation (a • b) • c = a • (b • c) holds.
		+	* Identity: There exists an identity element I ∈ S such that for all a ∈ S, I • a = a • I = a.
		+	* Inverse: Every element a ∈ S, has an inverse a' ∈ S with respect to the binary operation, i.e., a • a' = I; for example, the set of integers Z with respect to the addition operation is a group. The identity element of the set is 0 for
		+	the addition operation. ∀x ∈ Z, the inverse of x would be –x, which is also included in Z.
		+	* Closure property: ∀a, b ∈ S, the result of the operation a • b ∈ S.
		+	* A group that is commutative, i.e., a • b = b • a, is known as a commutative or Abelian group.
		+
		+	The set of natural numbers N (with the operation
		+	of addition) is not a group, since there is no
		+	inverse for any x > 0 in the set of natural numbers.
		+	Thus, the third rule (of inverse) for our operation
		+	is violated. However, the set of natural number
		+	has some structure.
		+
		+	Sets with an associative operation (the first
		+	condition above) are called semigroups; if they
		+	also have an identity element (the second condition),
		+	then they are called monoids.
		+
		+	Our set of natural numbers under addition is
		+	then an example of a monoid, a structure that
		+	is not quite a group because it is missing the
		+	requirement that every element have an inverse
		+	under the operation.
		+
		+	A monoid is a set S that is closed under a single
		+	associative binary operation • and has an identity
		+	element I ∈ S such that for all a ∈ S, I • a = a • I = a. A monoid must contain at least one element.
		+
		+	For example, the set of natural numbers N
		+	forms a commutative monoid under addition with
		+	identity element 0. The same set of natural numbers
		+	N also forms a monoid under multiplication
		+	with identity element 1. The set of positive integers
		+	P forms a commutative monoid under multiplication
		+	with identity element 1.
		+
		+	It may be noted that, unlike those in a group,
		+	elements of a monoid need not have inverses. A monoid can also be thought of as a semigroup
		+	with an identity element.
		+
		+	A ''subgroup'' is a group ''H'' contained within a
		+	bigger one, ''G'', such that the identity element of
		+	''G'' is contained in ''H'', and whenever h<sub>1</sub> and h<sub>2</sub> are
		+	in ''H'', then so are h<sub>1</sub> • h<sub>2</sub> and h<sub>1</sub><sup>−1</sup>. Thus, the elements
		+	of ''H'', equipped with the group operation on
		+	''G'' restricted to ''H'', indeed form a group.
		+
		+	Given any subset ''S'' of a group ''G'', the subgroup
		+	generate ''S'' and their inverses. It is the smallest subgroup
		+	of ''G'' containing ''S''.

← Older revision		Revision as of 17:43, 28 August 2015
Line 1,579:		Line 1,579:
	Let Z<sup>+</sup> = {n ∈ Z \| n > 0} and ''a'', ''b'' ∈ Z, m ∈ Z+,		Let Z<sup>+</sup> = {n ∈ Z \| n > 0} and ''a'', ''b'' ∈ Z, m ∈ Z+,
	then a is congruent to ''b modulo m'', written as ''a'' ≡ ''b'' (''mod m''), if and only if ''m'' \| ''a−b''.		then a is congruent to ''b modulo m'', written as ''a'' ≡ ''b'' (''mod m''), if and only if ''m'' \| ''a−b''.
		+
		+	===Prime Number, GCD===
		+
		+	An integer p > 1 is prime if and only if it is not
		+	the product of any two integers greater than 1,
		+	i.e., p is prime if p > 1 ∧ ∃ ¬ a, b ∈ N: a > 1, b >
		+	1, a * b = p.
		+
		+	The only positive factors of a prime p are 1
		+	and p itself. For example, the numbers 2, 13, 29,
		+	61, etc. are prime numbers. Nonprime integers
		+	greater than 1 are called composite numbers. A
		+	composite number may be composed by multiplying
		+	two integers greater than 1.
		+
		+	There are many interesting applications of
		+	prime numbers; among them are the publickey
		+	cryptography scheme, which involves the
		+	exchange of public keys containing the product
		+	''p''*''q'' of two random large primes ''p'' and ''q'' (a private
		+	key) that must be kept secret by a given party.
		+	The greatest common divisor gcd(a, b) of integers
		+	a, b is the greatest integer d that is a divisor
		+	both of a and of b, i.e.,
		+
		+	d = gcd(a, b) for max(d: d\|a ∧ d\|b)
		+
		+	For example, gcd(24, 36) = 12.
		+
		+	Integers ''a'' and ''b'' are called relatively prime or
		+	coprime if and only if their GCD is 1.
		+
		+	For example, neither 35 nor 6 are prime, but
		+	they are coprime as these two numbers have no
		+	common factors greater than 1, so their GCD is 1.
		+
		+	A set of integers X = {i<sub>1</sub>, i<sub>2</sub>, …} is relatively
		+	prime if all possible pairs i<sub>h</sub>, i<sub>k</sub>, h ≠ k drawn from
		+	the set X are relatively prime.

← Older revision		Revision as of 17:35, 28 August 2015
Line 1,483:		Line 1,483:
	include integer, real number, natural number,		include integer, real number, natural number,
	complex number, rational number, etc.		complex number, rational number, etc.
		+
		+	===Divisibility===
		+
		+	Let’s start this section with a brief description of
		+	each of the above types of numbers, starting with
		+	the natural numbers.
		+
		+	''Natural Numbers''. This group of numbers starts
		+	at 1 and continues: 1, 2, 3, 4, 5, and so on. Zero
		+	is not in this group. There are no negative or fractional
		+	numbers in the group of natural numbers.
		+	The common mathematical symbol for the set of
		+	all natural numbers is N.
		+
		+	''Whole Numbers''. This group has all of the natural
		+	numbers in it plus the number 0.
		+
		+	Unfortunately, not everyone accepts the above
		+	definitions of natural and whole numbers. There
		+	seems to be no general agreement about whether
		+	to include 0 in the set of natural numbers.
		+
		+	Many mathematicians consider that, in Europe,
		+	the sequence of natural numbers traditionally
		+	started with 1 (0 was not even considered to be
		+	a number by the Greeks). In the 19th century, set
		+	theoreticians and other mathematicians started
		+	the convention of including 0 in the set of natural
		+	numbers.
		+
		+	''Integers''. This group has all the whole numbers
		+	in it and their negatives. The common mathematical
		+	symbol for the set of all integers is Z, i.e., Z = {…, −3, −2, −1, 0, 1, 2, 3, …}.
		+
		+	''Rational Numbers''. These are any numbers that
		+	can be expressed as a ratio of two integers. The
		+	common symbol for the set of all rational numbers
		+	is Q. Rational numbers may be classified into
		+	three types, based on how the decimals act. The decimals either do not exist, e.g., 15, or, when
		+	decimals do exist, they may terminate, as in 15.6,
		+	or they may repeat with a pattern, as in 1.666...,
		+	(which is 5/3).
		+
		+	''Irrational Numbers''. These are numbers that
		+	cannot be expressed as an integer divided by an
		+	integer. These numbers have decimals that never
		+	terminate and never repeat with a pattern, e.g., PI
		+	or √2.
		+
		+	''Real Numbers''. This group is made up of all the
		+	rational and irrational numbers. The numbers that
		+	are encountered when studying algebra are real
		+	numbers. The common mathematical symbol for
		+	the set of all real numbers is R.
		+
		+	''Imaginary Numbers''. These are all based on the
		+	imaginary number ''i''. This imaginary number is
		+	equal to the square root of −1. Any real number
		+	multiple of ''i'' is an imaginary number, e.g., ''i'', ''5i'',
		+	''3.2i'', ''−2.6i'', etc.
		+
		+	''Complex Numbers''. A complex number is a
		+	combination of a real number and an imaginary
		+	number in the form a + b''i''. The real part is a, and
		+	b is called the imaginary part. The common mathematical
		+	symbol for the set of all complex numbers
		+	is C.
		+
		+	For example, 2 + 3''i'', 3−5''i'', 7.3 + 0''i'', and 0 + 5''i''.
		+	Consider the last two examples:
		+
		+	7.3 + 0''i'' is the same as the real number 7.3.
		+	Thus, all real numbers are complex numbers with
		+	zero for the imaginary part.
		+	Similarly, 0 + 5''i'' is just the imaginary number
		+	5''i''. Thus, all imaginary numbers are complex
		+	numbers with zero for the real part.
		+
		+	Elementary number theory involves divisibility
		+	among integers. Let a, b ∈ Z with a ≠ 0.The expression
		+	a\|b, i.e., ''a divides b'' if ∃c ∈ Z: b = ac, i.e., there
		+	is an integer c such that c times a equals b.
		+
		+	For example, 3\|−12 is true, but 3\|7 is false.
		+
		+	If ''a'' divides ''b'', then we say that a is ''a'' factor of
		+	''b'' or ''a'' is a divisor of ''b'', and ''b'' is a multiple of ''a''.
		+	''b'' is even if and only if 2\|''b''.
		+
		+	Let ''a'', ''d'' ∈ Z with d > 1. Then ''a mod d'' denotes
		+	that the remainder ''r'' from the division algorithm
		+	with dividend ''a'' and divisor ''d'', i.e., the remainder
		+	when a is divided by d. We can compute (''a mod d'') by: ''a'' − ''d'' * &lfloor;a/d&rfloor;, where &lfloor;a/d&rfloor; represents the floor of the real number.
		+
		+	Let Z<sup>+</sup> = {n ∈ Z \| n > 0} and ''a'', ''b'' ∈ Z, m ∈ Z+,
		+	then a is congruent to ''b modulo m'', written as ''a'' ≡ ''b'' (''mod m''), if and only if ''m'' \| ''a−b''.

← Older revision		Revision as of 17:00, 28 August 2015
Line 1,472:		Line 1,472:
	and recorded as 15.47 mm with ±0.01 mm maximum		and recorded as 15.47 mm with ±0.01 mm maximum
	allowable error has 3 significant digits.		allowable error has 3 significant digits.
		+
		+	==Number Theory==
		+	{{RightSection\|{{referenceLink\|number=1\|parts=c4}}}}
		+
		+	Number theory is one of the oldest branches
		+	of pure mathematics and one of the largest. Of
		+	course, it concerns questions about numbers,
		+	usually meaning whole numbers and fractional or
		+	rational numbers. The different types of numbers
		+	include integer, real number, natural number,
		+	complex number, rational number, etc.