All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Share

Description

ioioi

Tags

Transcript

Abstract
Algebra deals with more than computations such as addition or exponentiation; it also studies relations.Calculus touches on this a bit with locating extreme values and determining where functions increase and decrease; and in elementary algebra
you occasionally “solve” inequalities
involving the order relations of < or
≤,
but this almost seems like an intrusion foreign to the main focus, which is making algebraic calculations. Relational ideas have become more important with the advent of computer science and the rise of discrete mathematics, however. Many contemporary mathematical applications involve binary or n-ary relations in addition to computations. Other kinds of relations, particularly ones that impose an order of one sort or another on a set. This will lead us to investigate certain order-structures
(posets, lattices
) and to introduce an abstract type of algebra known as Boolean Algebra. Our exploration of these ideas will nicely tie together some earlier ideas in logic and set theory as well as lead us into areas that are of crucial importance to computer science.
Introduction
Lattices
have a number of applications,and they provide one way for us to introduce and become familiar with Boolean Algebra, a field of prime importance to computer science.In order to concentrate on lattices that are most appropriate for this final focus, we need to consider a fair number of new properties of relations.
Definition of a Lattice
A
lattice
is a partially ordered set in which every two elements have a unique supremum (also called a least upper bound or join) and a unique infimum (also called a greatest lower bound or meet).
An example is given by the natural numbers, partially ordered by divisibility, for which
the unique supremum is the least common multiple and the unique infimum is the greatest common divisor.
Example of lattice
Given a set S={1,2,3,4,5,6,7,8}, defined by a partial order relation Divisibility. Now consider all 4 elements containing sub-graphs, out of which {1,2,4,8} is a Lattice obviously . Is {1,2,3,6} also a lattice? Each and every pair of elements of this sub-graph has a greatest Lower Bound and Least Upper Bound Defined. So is it a Lattice?
{1,2,3,6} is a lattice since it is the set of all divisors of 66, and so the smallest common multiple of any of its members must also be a divisor of 66, and likewise the greatest common divisor. In this case the set is so small that it's easy to test this for all pairs: {1,2}, {1,3}, {1,6}, {2,3}, {2,6}, {3,6}. If it works for pairs of members of a finite set, then a trivial induction shows that it works for larger numbers of members of that finite set. That goes like this: suppose {a,b} has a least upper bound c, and {c,d} has a least upper bound e. Then e must be the least upper bound of {a,b,d} since e is an upper bound of {c} and therefore of {a,b}, and is also an upper bound of {d}, and nothing smaller than e can be an upper bound of {d,e}; hence cannot be an upper bound of {a,b,d}. Every time one new member is added (as d was in this case) the same thing can be done again.

Related Search

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks