### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Elements of Discrete Mth I MTH 231

PCC

GPA 3.98

### View Full Document

## 51

## 0

## Popular in Course

## Popular in Math

This 20 page Class Notes was uploaded by August Feeney on Monday October 19, 2015. The Class Notes belongs to MTH 231 at Portland Community College taught by Staff in Fall. Since its upload, it has received 51 views. For similar materials see /class/224652/mth-231-portland-community-college in Math at Portland Community College.

## Reviews for Elements of Discrete Mth I

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/19/15

Introduction to Linear Algebra Introduction Linear algebra is the study of systems of linear equations more about that later and is an integral part of MTH 23139s discussion of Graph Theory Classical graph theory represents graphs as pictures and graph theory results are demonstrated or proved using geometric constructs Computers on the other hand process numbers much more ef ciently than pictures and graphs are represented by matrices The adjacency incidence Laplacian and degree matrices of a graph capture its essential properties and the techniques for working with matrices are the essence of linear algebra By way of introduction a 17760 equafz39o is an equation of the form a1x1 a2x2 anxn b where an are known real or complex valued coef cients b is a real or complex value and xnrepresents an unknown real or complex value In linear equations products of unknown values such as x1x2 or xn3 are not permitted and the coef cients are not more general functions e g sine function A system of 17760 aqua10173 is two or more sets of related linear equations such as simple simultaneous equations presented in elementary algebra For example 3x12x2 4x3l x15x23 is a binary system of linear equations in three unknowns In general we may have an arbitrary number of equations and unknowns in a system If we have m equations in 17 unknowns then we could write a11x1 a12x2 alnxn b1 a21x1 a22x2 ahxn b2 am1x1 amzx2 aman bn The coefficients an and value bn are quotnumbersquot by which usually is meant real or complex numbers Note that all of the essential information in a system of linear equations is contained in these numbers and so the above system is usually written as a matrix 71 1 a12 a1 51 a2 1 a22 a2n 52 am 1 am 2 quot am n bn Matrices are a compact notation for expressing systems of linear equations More speci cally a matrix X is a rectangular array of values If the values are real numbers then we say quot is a matrix over IRquot The values in the array are entries in X The subscripts shown the above example are in quotrow majorquot order ie the rst index is the row and the second index is the column Using this common convention if we say quot is an m X 17 matrix over IRquot we mean that X has mrows and 17 columns and the entries are real numbers Finally let39s go back to the pair of simultaneous equations 3x12x2 4x3l x1 5 x2 3 De ne the following matrices X1 3 2 4 l X x2 b 1 5 0 3 x 3 The simultaneous equations would then be written as the matrix aqua017 Ax b Again the point here is that matrices provide a compact notational convention but the underlying equations are the linear equations shown above Matrix Operations Addition Multiplication Suppose X is an m X n matrix over IR and 6 is a p X q matrix over IR By de nition it 6 if and only if all of the following are true mp nq aijbijVaE7AbE6 In other words two matrices are identical if they have identical entries and the same number of rows and columns Matrix addition is relatively straightword but the key rule is that the operands must have the same number of rows and columns ie and 6 are additivey corformabe In other words addition of matrices of different sizes is not defined at least in MTH 231 Suppose X and 6 are two m X n matrices Then G X 6 means cij aij bij In other words the elements of the matrix sum are the sum of the elements of the operand matrices From this it follows that matrix addition has many of the same properties as quotnormalquot addition of real numbers specifically The sum of any two matrices is also a matrix More formally matrix addition over real numbers is closed Matrix addition is associative A B C A B C Matrix addition is commutative A B B A There exists a matrix called the zero matrix 0 such that A 0 A for all matrices A 0 is the identity matrix for addition For every matrix A over real numbers there is a unique matrix A such that A A 0 In other words every matrix has an additive inverse or negative These properties simply mean that given m and n the set of all matrices with m rows and n columns is an abeI39cm group under addition If you have not studied groups in algebra then don t worry about this concept for MTH 231 Matrix multiplication comes in two avors Scalar multiplication of matrices involves a matrix X over real numbers and a single real number or scalar If The scalar product 6 11 is a matrix where bij kaij ailIr k In other words a scalar product is computed by multiplying every entry in a matrix by the same constant value Scalar products have a number of properties derived from real number arithmetic tA B er B where Iris a real number while A and B are matrices rA er A where Irandare real numbers and A is a matrix gA tA where Irand 39 are real numbers and A is a matrix lAA The second type of matrix multiplication is not nearly as straightforward as scalar multiplication Remember that matrices are a compact representation of systems of linear equations Suppose we have the system Y1 3X1 39 5X2 y2 5x1 3x2 The matrix version of this system is Ax y where 35 53 X1 Y1 x l and y The goal of quottruequot matrix multiplication is allow the matrix X y 2 2 equation Ax yto generate the original linear system of equations when the operation is completed To see how this can happen suppose we have a second system of linear equations Z1y1y2 Z23 13923 2 Z3 0y1 2y2 whose matrix form is Z Bywhere 21 l l y1 z 22 B 1 2 andyasbeforeis 23 0 3 y2 So what we have here is two systems of linear equations the rst a twoequation system in y and x and the second a threeequation system in y and z We can apply a normal algebraic subsitution and express the threeequation system in terms of x 21 3x1 5x25x1 3x2 3 5x15 3x2 22 3x1 5x2 25x1 3x2 3 25x15 23x2 Z3 03x1 5x21 35x1 3x2 0 35x10 33 x2 3 5 5 3 and the corresponding matrix is 3 10 5 6 0 15 0 9 Using matrix equations we have Ax y and z By We wam to be able to substitute and associate such that this means 2 BAx BAx since the underlying operations are simply real number algebra 3 5 5 3 In other words we need to de ne matrix multiplication such that BA 3 10 5 6 if the 015 09 matrix equations are going to accurately re ect what happens in the linear systems This requires one simple rule the number of columns in B must equal the number of rows in A This is a fundamental requirement so let me be precise If B is a matrix with m rows and n columns and A is a matrix with p rows and q columns then the product BA is de ned if and only if n p The product AB is de ned if and only if q m Thus in general AB i BA since one may be de ned and the other not de ned The actual operation of matrix multplication is straightforward Again suppose B is an m X n matrix and A is an n X p matrix ie A has as many rows as B has columns The the matrix C BA is de ned 7 by cij 281754117 The matrix C is an m X p matrix Suppose we have the following two matices gh a c agbickahbjcl X and 1 J Thenthe productmatrixZX def k1 dge1 ltdhej For example let 4 3 2 0 3 X and 2 2 Then 1 l 0 2 1 Z W 24023 2 23023 1 2 3 7 7 14120 2 13120 1 7 2 1 MuI WJACY 2 3 1 2 1 Matrix multiplication follows some of the general rules of quotnormalquot multiplication ABC ABC associatiVity AB C AB AC distribution over matrix addition ABCACBC tAB erB where Iris a real number Linear Algebra and Maple Maple has a nice Linear Algebra package w1 1 111611194 gebr ampX Add Aaj39w39m BackwardSubs m e Ba a am39yg Bay39s BezouMam x B139a 139ag017aForm 2 311139 W 1 1 C u we 139 Li W A C u we 139 L n 39 Comm1 Comm70117161131017 C 0um110peraf139017 Colum Space Compam39o lam39x C011a 11 139011Vumbeig C a sfa tlafmc C a sfcmeecor C opy CreatePemum 39wq CrossPoducl DeefeColzmm Delete30w Dare17111711111 D111g017al D111g017aMaf139Jg 0177161757071 01171611510175 Dol Poa ucl Egg1G w39u39v m 1 p 339 1739 Equa ForwardSubs 39fue Frobem39usForm Gauss139cmE13917113911a1 139011 Ge erafeEqua 39wm Ge erafelam39x Game1c GefResul amfype Gel esulfSIape G139Ve sRofaf139017lafr1x GramScIm139a 1 Ha reMam39x Hermz39feForog Hermi cmfro wose Hesse bergForm MlbertlofrX HouseholderVomit de IWMofrX fersecI39o BoS y IsDe fe lsOrfIogomzl SSmilor IsU foiy Jordo BlocWorbg Joro cmForm Ailc2177 1 UDecomposz39foo LeosSquareg LireorSolve 39 39 39 magnetu ywjt w 9 Mo Mo MairMd Morlrpr 1 h 1 1 1V w All w 39 1 39r 1V w MM 1v a Qtquotowe MofrXScolorMulfipl Ix a MV 1 39r 1v 139 139 1w 1 Moor Modular Mullply NoUserVolue Norm 1W W39 p 1 1r 0M 1 1 A quota a 5 P139Vof PopoVForm QRP I 39 39 D 1 A 13a 40 V1 mm Rook RoIo olCoqo z39coForm ReducedRochIelo Form Row Row017716175on RowOperaton RowSpace ScoldrMofrJg 1 1 Scam V1 mm S M u A rgulorVolueg SwirlForm SfroqglyC 1 S 1V w A SM V1 mm SumBosng Sylvester11mng Toeplfl Zlorfx Trace fromoose T 39 39 1 x 0 Jam I up 1 A Vectoer o I 1 V 1 39 1 39r km 1W V1 1 1 39 Z eroM arrX Z ero V ecfor Zip Matrix values are entered in Math mode using the quotMatrixquot tab in the left column 01 A 0 0 01 lo 0 10 31 0 0 10 lo 0 AddAB 1 1 lo 0 MullleA B 0 0 lo 0 MullleA A 0 0 lo 0 Morszo wer B 3 3 4 5 6 7 1 0 0 0 l 3 Matrix Fundamentals Let Fm be the set of all matrices having mrows and 17 columns As noted above F is an abelian group i e it is closed under matrix addition and the addition behaves quotnormallyquot The existence of an additive inverse or quotnegative matrixquot allows us to perform subtraction as a form of addition Unfortunately multiplication and division are not as convenient and many of the rules are different from real or complex number multiplication Consider the matrices A and B above Note that Mull7044A B 0 0 0 0 0 1 0 0 In general even if the matrices are mulMDi cafively corformable the rows and columns are correct AB i BA ie multiplication is not commutative Now consider the additive identity matrix 0 9 Muirpm 3 A 10 0 0 C2 0 0 0 0 11 0 0 Noticethat MufpJAB 0 0 12 0 0 MurwMQB 0 0 13 0 0 In other words AB CB but A i C In other words matrix multiplication does not factor in a quotreal numberquot sense Also note that AB 0 even though neither A nor B is 0 There is a multiplicative identity for matrices namely a matrix with IS on the diagonal and 0 everywhere else The multiplicative identity quotIquot is given in Maple by Idem391sz arrM 2 2 1 0 0 1 The multiplicative identity has the property that IA A Al for all matrices 14 There is no multiplicative inverse for matrices such that AA391 I A39lA which makes division dif cult Recall that the multiplicative inverse of real number x is x391 such that xx391 l which is the multiplicative identity for real numbers Every nonzero real number x has an inverse namely This x is not the case for matrices Consider the matrix A above There is no matrix X such that AX I because the second row of AX must be 0 0 However some matrices do possess an inverse just not all matrices If the matrix is a square matrix same number of rows as columns with no inverse the matrix is smgular If the matrix is invertable then it is a sf guar Each nonsingular matrix has a unique inverse Matrix versdA Error in Li nearAl gebra LAMain MatrixInverse s ingular matrix Nonsingular matrices are convenient because if A is a nonsingular matrix then BA 0 gt B 0 technically a nonsingular matrix can not be azero all11mlquot The transpose of a matrix is the juxtaposition of the rows and columns Speci cally if A is an m X n matrix then the tranpose B AT is bij aji Maple will provide the transpose l 2 3 X 4 5 6 7 8 9 2 3 4 5 6 15 7 8 9 fly79003411 4 7 2 5 8 16 6 9 The race of a matrix is the sum of the diagonal entries of the matrix from upper left to lower right TraceX 15 17 Determinants Assume for the sake of this discussion that all matrices are square matrices over IR The concept of the determinant of a matrix is related to the idea of the volume of a gure Suppose we haveA i j and we interpret the rows as vectors x y coordinates in the plane This gives a picture of two lines We can quotclosequot the gure by completing the parallelogram A quotclosedquot gure includes the concept of an area or twodimensional volume This idea generalizes to larger matrices ie a square matrix with 3 columns generates to a solid gure in 3dimensional space An arbitrary n X n matrix creates an ndimensional solid corresponding to a 2dimensional parallelogram an l Ipal UelepQDEQ The determinant function calculates the quotvolumequot of this gure If A is an n X n matrix the determinant of A is identi ed by detA The determinant function is unique for each size of a matrix and has the following properties detA 0 if A has any duplicate rows detI 0 where I is the identity matrix 0 detAB detA X detB The actual calculation of a determinant value for a given matrix is beyond the scope of this course but Maple provides an easy shortcut l 2 3 4 5 6 18 7 8 9 Deferm a X 0 19 Eigenvalues and Eigenvectors The German word quoteigenquot means quotproperquot or quotownquot The words quoteigenvaluequot and quoteigenvectorquot are linguistic abominations that have become common in mathematics so MTH 231 will continue the tradition Suppose A is a n X n matrix The scalar value 7 is an eige value of A if and only if A M is a singular matrix Suppose X is a n X 1 matrix ie a column matrix that is not 0 X is an eige vecorof A if and only if A MX 0 If 7 is an eigenvalue and X is an eigenvector then AX XX In geometric terms an eigenvector is a vector whose direction is not changed when multiplied by A although the magnitude may change 110 Finally think about the function detA II For example letA 0 2 0 then A II 0 0 3 0 2 I 0 detA II is a function speci cally 0 0 3 I l I 2 I 3 I 6 11 I 6 r2 r3 In general the function detA II is apolynomial where I is the unknown and is called the character1m Dob170mm of A The roots of the characteristic polynomial are the eigenvalues of the matrix Maple provides tools for calculating the eigenvalues eigenectors and characteristic polynomials of a matrix 110 Az 0 2 0 003 549217 values A C haracferLyI39cPoy omm A x Egg7 vectors A 6x3 6x211x 2 3 l 110 020 003 a l 0 l l 0 0 0 l 0 20 21 22 23 What Is MTH 231 Mathematics 3 7 Mathematicians are a fairly disagreeable lot and it should be no surprise that there is no single comprehensive answer to the question quotWhat is mathematicsquot Bertrand Russell proposed the following de nition quotPure Mathematics is the class of all propositions of the form p implies a where p and q are propositions containing one or more variables the same in the two propositions and neither p nor a contains any constants except logical constantsquot Russell The Principles of M athematics 1903 The term quotpurequot is often contrasted with the term quotappliedquot when discussing mathematics but there is no clear dividing line between pure and applied mathematics In a general informal sense quotpurequot mathematics is the study of what we know or can deduce if we assume some set of facts or propositions A system of reasoning usually known as a mathematical logic is used to form conclusions from premises MTH 231 will introduce one common system of mathematical logic commonly known as first order logic FOL that we can use to deduce conclusions in a variety of different mathematical areas Applied mathematics generally consists of a set of tools and procedures that are useful in disciplines such as physics chemistry biology and others Mathematics is fundamental to many of these elds but the interest of a practitioner is in using mathematics not developing mathematics Pure mathematics discovers conclusions applied mathematics uses these conclusions to understand something about the world The art of pure mathematics is discovering new conclusions while the art of applied mathematics is determining which of these conclusions might relate to the quotreal worldquot For example George Boole published the bookAn Investigation of the Laws of Thought in 1854 in which he introduced a new type of algebra based on the mathematical structures concealed in everyday speech Boole s algebra was largely ignored until 1939 when Claude Shannon discovered the algebra provided a good description of digital switching circuits Boolean algebra is now 7 considered a fundamental tool for all programmers and computer scientists Numbers MTH 231 explores elements of discrete mathematics The nature of discrete mathematics is best understood in the context of numbers so a brief introduction to numbers is in order The rst thing to realize however is that a formal and precise de nition of num ber is elusive Most modern mathematicians view numbers in terms of number systems or collections of individual numbers Number systems are distinguished by the arithmetical operations addition subtraction multiplication division et al that can be performed on them There are six main number systems natural numbers integer numbers rational numbers real numbers complex numbers and transfinite num ers Natural Numbers 37 W Natural numbers are the counting numbers e g 1 2 3 The set of all natural numbers usually is denoted N Natural numbers have been used since mankind began counting things In more recent times about 200 AD or so the number zero 0 was invented and most computer scientists regard zero as a natural number The broader mathematical community is somewhat divided on this topic A formal de nition of natural numbers is credited to Guiseppe Peano who in 1889 published the first version of the Peano Axioms The Peano Axioms de ne natural numbers in terms of an object 0 and an operation s called asuccessor function The Peano Axioms state that natural numbers are any number system that has the following properties 1 For allx sx i 0 In other words 0 is not the successor of any other number 2 For allx and y ifx ythen sx i sy In other words every number has a unique successor 3 IfA is any subset of natural numbers and if 0 is in A and if sx is inA wheneverx is in A thenA is the set of all natural numbers Intuitively the object 0 is the number 0 and the operation 3 is addition This means sx is the same as x l The third axiom is called the Axiom of Induction and will be discussed in great detail later in MTH 231 What is most important at this point is that the Peano Axioms are axioms ie we can assume they are true and therefore have no need to prove these properties In fact we will apply our system of mathematical reasoning first order logic to these axioms to derive some interesting conclusions Integer Numbers Natural numbers are very useful for counting things but these are not the only whole numbers The introduction of negative numbers allows numbers to be used for more than counting e g with negative numbers we can subtract The concept of zero is essential to the idea of negative numbers Zero is the additive identity which means that adding zero to any number leaves the number unchanged A negative number can be defined as the value that when added to a natural number results in zero In other words if n is a natural number then n is the negative natural number such that n n 0 The set of all integers positive natural numbers negative numbers and zero is denoted Z for the German word quotzahlenquot or quotnumbersquot Integers are the system where subtraction is always possible 6rdinals and Cardinals A brief digression is in order at this point The term quotcountingquot is too informal for our purposes T Natural numbers and integers have two general purposes The first purpose is to identify the size of something eg the size of a set of objects This is the basic idea of counting to identify how many or how much of something Numbers that are used to identify size or magnitude are called cardinals and the cardinality of something is its size For example the cardinality of the set of days in a week is 7 meaning that there are 7 days in a week Another use of integers is to express order or position in a list For example we often speak of quotthe first thing the second thing the third thingquot and so forth Numbers that are used to identify 7 order are called ordinals Rational Numbers Natural numbers allow addition due to the successor function of the Peano Axioms and integer numbers allow both addition and subtraction Furthermore both natural and integer numbers can be used as ordinals or cardinals Counting and ordering things are important tasks and share the property of wholeness In other words if one is counting objects e g rocks one may have 1 or 2 but never anything between 1 or 2 There is no concept of quothalf a rockquot if you take one rock and break it then you have more than one smaller rocks The wholeness property of integers and natural numbers is simply the idea that between any two successive numbers there is nothing In other words there is no integer value that between 1 and 2 The idea of wholeness is sometimes referred to as chunky ie natural numbers and integers are chunky since they come in chunks This property is also called discreteness integers and natural numbers are discrete values Discrete values are sufficient for counting and ordering but not for many other types of applications One such application is measurement such as length height or weight Measurements are not discrete and so integer numbers are not adequate In a pure mathematical sense we need additional arithmetic operations beyond addition and subtraction In particular we need division If we add or subtract two integers we get another 1nteger but if we d1v1de two integers may get something that is not an integer eg A rational number is the ratio of two integers eg fraction The set of all possible fractions the set of all ratios of integers is the rational number system or Q for quotquotientsquot Rational numbers are measurement numbers although not all measurements are rational numbers More formally rational numbers are the number system that mostly allows division although not division by zero RTeaI Numbers Rational numbers are extremely useful for measuring things but it has been known for thousands of years that some measurements can not be expressed as rational numbers The classic example of this is the length of the diagonal of the unit square Suppose one has a square whose sides are of length 1 Then the length of the diagonal of the square is I 2 a fact known to ancient Greeks This value is not a rational number a fact that was also known to the ancient Greeks Clearly the rational numbers must be extended to deal with these nonrational measurements The extension of rational numbers to include irrational numbers yields the set of real numbers or IR A formal de nition of real numbers Will be given later in this course but an 1nforma de nition is that the real number system is the set of all numbers with a nite or in nite decimal expansion For example is a real number with decimal expansion 05 and is a real number with decimal expansion 03333 Similarly J is a real number with decimal expansion 7 141421 The Polynomial Problem 37 391a2x2 alx a0 where al A polynomial equation is an expression of the form anxn an1x are known values and x is an unknown value Polynomials arise in a number of practical circumstances and the quotpolynomial problemquot is the question of how to determine the value of the unknown x In particular one seeks the root of the polynomial which is the value of x when anxn an1xn391 a2x2 alx a0 0 If you graph a polynomial the root is where the graph crosses the x axis The polynomial problem has inspired a great number of mathematical insights but at this point in MTH 231 the purpose of introducing this notion is to distinguish two different categories of numbers 1 If a number is the root of a polynomial with integer coef cients then the number is called an algebraic number 2 If a number is not the root of any polynomial with integer coef cients then the number is called a trancenalental number 60mplex Numbers Simple polynomials may have no real number solution for example the polynomial x2 1 In order to address the polynomial problem mathematicians introduced the object i with the property i2 1 The set of all numbers of the form a bi where a and b are real numbers forms the complex number system or C Complex numbers are beyond the scope of MTH 231 T rans nite Numbers l Infinity is not a simple concept Consider the following 1 There are an in nite number of natural numbers since one can always add 1 to a natural number and get a new natural number 2 There are an in nte number of integer numbers since every natural number has a negative 3 There are an in nite number of rational numbers since there are an in nite number of numerators and denominators 4 There are an in nite number of algebraic numbers since there are an in nite number of integer coefficients Intuitive there are quotmorequot rational numbers than integers since there are in nitely many rational numbers between any two integers But what does quotmorequot mean in the context of in nite Georg Cantor proved in 1874 that there are more real numbers than algebraic numbers and this led him to the rst systematic consideration of mathematical in nity Cantor recognized that two sets are the same size if there is a onetoone correspondence between elements in the sets For example suppose one has two classrooms full of students at PCC Which classroom has more students Cantor s method is to pair students from each classroom create pairs of students with one from classroom A and the other from classroom B Continue making pairs until you exhaust one classroom If there are any students left in the other classroom then it has more students The idea of forming pairs is intuitive and simple but leads to some nonintuitive results Consider the case of natural and integer numbers At rst glance it might seem that there are more integers than natural numbers but this is not the case Consider the following rule for making pairs If n is an even natural number 2 4 etc then pair it with the integer number Since n is even the quotient will be an integer Ifn is an odd naturl number 1 3 5 etc then pair it with with L J ie the largest negative 1 integer smaller than 2 This creates the following pairs 1 gt 0 2 gt 1 3 gt 1 etc It is easy to show that every natural number is paired with a unique integer and each integer is paired with a unique natural number Since every natural number and every integer are paired with nothing left over it follows that there are the same number of integers and there are natural numbers Similarly Cantor showed that there are more real numbers than there are integers by showing that some real numbers can not be paired with integers Thus in nity comes in at least two different quotsizesquot The numbers used to denote different sizes of in nite are called trans m39te numbers The smallest transfinite number is No or quotalephnullquot Cantor ran out of Greek letters so he moved to Hebrew alphabet N0 is the cardinality of the integers and natural numbers Any set with this cardinality is called quotcountably infinite since the natural numbers can be used to count the set Rational numbers have cardinality NO as well a strange result demonstrated by Cantor In other words there are exactly the same number of natural numbers as integers as rational numbers ie HNl lZl lQl N0 These are the traditional domains of discrete mathematics The next largest transfinite number is N1 and it is assumed but never proven that this is the cardinality of the real numbers R This assertion is known as the Continuum Hypothesis and R is said to be continuous Formally the Continuum Hypothesis states that 2Nn N 1 but is an undecidable question Real and complex number algebra and calculus are the traditional domain of continuous mathematics It is generally believed that there is no transfinite number that falls between the size of the integers and the size of the real numbers Sets with cardinality N1 or greater are uncountably in nite Note that transfinite numbers appear to be discrete Is the quotreal worldquot discrete or continuous Discrete Math V MTH 231 is a discrete math course which means that the numbers and sets we use are all countably in nite Calculus and realnumber algebra are continuous math courses and they focus on numbers and sets that are uncountably in nite In MTH 231 we will look at first order mathematical logic and use FOL as our quotsystem of reasoningquot when we derive conclusions MTH 231 will also discuss set theory and graph theory Set theory is a foundation of mathematics which means that the axioms of set theory can be used to derive virtually all mathematical results Graph theory is a very useful applied tool for 7 computer science purposes Algebraic Systems Numbers are best thought of as members of number systems A number system consists of objects numbers together with operations addition subtraction that can be performed on those objects Natural numbers have addition integers have addition and subtraction rationals introduce division and so forth Collections of objects and operations are called algebraic structures Number systems are one type of algebraic structure but there are many many others Algebraic structures can be categorized by the properties of their operations and the nature of their objects Sets MTH 231 will discuss sets in much greater detail later but the basic de nition is quite simple a set is a collection of objects Sets have a cardinality size but no ordinality order In other words the set A a b c is identical to the set A b c a and the cardinality ofthe set is lAl 3 When the elements ofa set are listed we assume duplicate elements are the same ie A a bc aabbcc cccba and lAl is still 3 Monoids V Sets are very basic ideas and since they contain no operations they are not considered algebraic structures Perhaps the simplest algebraic structure is the monoid which formally is a set that has an identity element and is closed under a binary operation A quotbinary operationquot is simply an operation that takes two operands like addition subtraction multiplication division and so forth As noted above an identity element is an element that leaves the other operand unchanged Zero 0 is the identity element for addition x l l x x and one 1 is the identity element for multiplication l x xl x In order to understand the nature of monoids consider the quottraditional quot natural numbers 1 2 3 Addition is a binary operation and the natural numbers are closed under addition since the sum of any two natural numbers is a natural number Multiplication is also a binary operation and the product of any two natural numbers is a natural number However the quottraditionalquot natural numbers 1 2 3 do not form a monoid under addition because there is no additive identity The number 10 form a monoid under multiplication however since 1 is included This is one motivation for including zero in the natural numbers If zero is included then natural 7 numbers form a monoid under both addition and multiplication Groups W A group is a monoid with the additional qualities of associativity and inverse More precisely a group is a set of values and a binary operation and The set is closed under the binary operation a requirement of monoids The set includes an identity element for the binary operation a requirement of monoids The operation is associative eg ABC ABC The set contains an inverse for every element The inverse of a value x is another value y such that whenx and y are operands the result is the identity element T The natural numbers 012 form a monoid under addition and multiplication and these operations are associative However natural numbers do not form a group with these operations because there is no additive or multiplicative inverse in the natural numbers In order to form a group under addition we need the negative numbers and in order to form a group under multiplication we need the rational numbers With addition the inverse is the negative X X l l 0 and w1th multiplication the inverse of 1s 1e x l x x Rings V A ring is a quotgroup on steroidsquot Speci cally a ring is a set of values along with two binary operations which we will call and that satisfy the properties The set is closed under both and The operation is associative a b c a b c The operation is commutative a b b a The operation is associative abc abc The set contains an identity for the operation which we will call 0 The set contains an inverse for the operation for every element 0 and are left distributive eg ab c abac and are right distributive eg b ca ba ca These properties may look a lot like arithmetic but notice what is missing need does not need to be commutative There does not need to be any identity for There does not need to be any inverse for The integers form a ring under addition and multiplication hence the use of the quot and quotquot symbols for ring operations as do the rational real and complex number systems Rings are extremely useful in computer science applications including hardware design and program data structures Fields If the three missing properties listed above are added to a ring the result is a eld The rational real and complex number systems are elds under addition and multiplication but not the integers The idea of a eld is that these are the structures that support quotnormalquot arithmetic and all of the arithmetic operations you are used to from real number algebra apply to any eld Perhaps the most interesting property of a field is the idea of extension which allows new elds to be built from existing elds Suppose F is a set that forms a eld under and If you nd a polynomial P that has no roots in F you can add the root to F and the resulting set F is also a eld under and This is precisely the technique use to create complex numbers from real numbers The polynomialP x2 1 has no root in IR so 139 was introduced and the resulting extension is C The properties ofa eld guarantee that C is a eld since it is an extension oflR

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.