We're Open
+44 7340 9595 39
+44 20 3239 6980

UNDERSTANDING OF KEY CONCEPTS IN MANY AREAS OF MATHEMATICS AND COMPUTING

  100% Pass and No Plagiarism Guaranteed

UNDERSTANDING OF KEY CONCEPTS IN MANY AREAS OF MATHEMATICS AND COMPUTING

Set Theory

Set theory is a branch of mathematics that plays an interesting role in the study of computational theory. It is also essential to the understanding of key concepts in many areas of mathematics and computing.

Definitions

A SET is simply an unordered collection of objects which contain no duplicate objects.

The first thing you probably noticed is the rather obvious use of an ill-defined term – namely, “object”. What is an object? Well – pretty much anything. That’s the point and power of set theory. On the one hand we could talk about the set of cars parked in the lot outside of McDonalds. Then again, we could be talking about a set of abstract objects such as “The set of non-negative integers that are multiples of 13”.

If you glance at the definition of a set again you will also notice two important things – sets have no particular ordering of the elements. So, the set containing 1, 2, and 6 is EXACTLY the same as the set containing 6,2, and 1 or the set containing 1,6,and 2. A second important property of sets is that they do not allow duplicate objects. This limitation is sometimes dropped but the result is that you have what is commonly called a “multi-set” rather than a true set.

Notation

There are a variety of ways to represent a set. A common approach, if the set is rather small in size, is to list each element of the set, separated by commas, inside of curly-braces { and }. For example.

{A, G, J, D } {1, 2, 4, 3, 6, 8} {2,4,6,8,10} {Bill, Sally, Joe, Joan, John}

This notation works fine for very small finite sets but if sets become larger in size, or God-forbid infinite, it obviously breaks down quickly. Since sets are often used to contain values that have some property, we can often represent a set using elipses to indicate that some pattern is to be repeated. For example,

{ 1, 3, 5, 7, 9, …, 99} representes the odd integers from 1-99.
{2, 4, 6, … , 20} - even positive integers less than or equal to 20.

Even some infinite sets can be represented in this fashion.

{5, 10, 15, 20, 25, … } - positive multiples of 5.

This notation works well when there is a simple and obvious pattern to be identified but breaks down when the pattern is either too complex to see or is ambiguous. In such cases we need to use a notation known as set-building notation.

This technique allows us to use a variable, say x, to represent an arbitrary element of a set, and then explicitly list the property that all such elements of the set share. For example,

S1 = { x | x is a positive integer greater than 5 and a multiple of 13 }

S2 = { x | x is a student enrolled in both CSC-364 and MAT-385 }

S3 = { x | 0.0


Set Equivalence

Two sets, S and T are equivalent, that is S == T, if and only if they contain the same elements. More formally,

S == T iff x (x S < -- > x  T) where < -- > is the logical biconditional.

If you look at the definition, you will note that when we attempt to prove that two sets are equal we must prove something in two directions. That is, we must show that if we assume that x is a member of set S then we can show that it is also a member of set T AND we must then assume that x is a member of set T and show that it follows that x would be a member of set S as well.

Universal Set

The universal set (usually represented as U ) is a concept of set theory that occasionally plays a pivotal role in proofs. One might assume that, since any object can be placed into a set with any other objects, that the universal set would simply be the universe itself. Although this is certainly possible, the universal set is often defined to be something more limited in scope. For our purposes, the universal set is simply the collection of objects from which we select specific elements of a set. For example, we might have a universal set of all integers and from this universal set we might choose to build a set S consisting of all multiples of 7. Often, the universal set is left implicit. This is usually the case if the specific nature of U is of little or no importance to the proof or theory we are examining. When U is of importance, it is usually explicitly defined.

For example, let U = { p | p is a syntactically legal Java program }. Let S = { x | x is a program that outputs the message “Hello World” at some point during its execution.}. In this example we need not consider any Java files that contain syntax errors or are not properly structured as part of our universe.

Subset and Proper Subset

A set S is said to be a subset of a set T, represented as S ⊆ T if the following is true:

S ⊆ T iffx (x  S  x  T)

that is, every element of S is also an element of the set T. Obviously, this does not imply that the two sets are exactly the same as T may contain elements that S does not.

Examples:

{ 2, 4, 6 } ⊆ {2, 4, 6}
{2,4,6,8} ⊆ { 1,2,3,4,5,6,7,8,9,10} 
{x | x is a positive integer } ⊆ { y | y is an integer } 
{p | p is a syntactically legal java program of less than 100 lines} ⊆ {r | r is a syntactically legal Java program}

For any set S, the empty set is considered to be a subset of S. That is ∅ ⊆ S.This may seem odd but by the definition x is an element of S implies x is an element of T. BUT, if you remember your logic, FALSE implies ANYTHING and thus since there is no x that is an element of S we have FALSETRUE.

It should also be obvious that given any set S it is a subset of itself. That is, S ⊆ S since any x in S is obviously in S!
A proper subset is represented as S ⊂ T, and indicates that there exists at least one element in T that is NOT in the set S. That is, all of the elements in S are contained in T but T contains more. In the examples above, all except the first example would be proper subset relationships.

Set Cardinality

The total size of a set is known formally as its cardinality. We usually represent the cardinality of a set S using the notation |S|. Thus if S = {a,b,c} then |S| == 3. This may seem to a trivial issue but things get interesting when we move beyond finite sets and into infinite ones.

Please note that the empty set ∅ or { } has a cardinality of 0 as it contains no elements.

For many of us, the concept of an infinite set is a bit strange but we have grown to feel comfortable with it. If one were to ask the cardinality of the set of all integers we would quickly reply “infinite” – smile, and feel pretty good about ourselves. Similarly, if one were to be asked the cardinality of the set of all real numbers we would do the same. But what if you were asked if these two sets were of equal cardinality? Are they truly the same size?

Interestingly, the answer is a resounding “NO!”. One of the two sets is actually larger than the other. Although the proof and justification for this is beyond the scope of this course, one can gain insight by noting a few things about the two sets.

First, let us discuss the set of all integers. Clearly it is infinite in size. There is no “last” or “largest”value in the set as we can always add one to it to get a new, larger element. But the set of integers has an interesting property – it is countable.

A set is countable if given a value in the set we can provide the “next” value with certainty. For example, in the set of all integers (we will name it ℤ ), if I give you the value 56 then you can, with certainty, tell me the “next” integer is 57. If I say 973245 you say 973246. In fact, we say that the cardinality of the set of all integers is a countable infinity. Formally, we represent this as ℵ0 (pronounced “aleph-naught). Many sets are countable infinities. For example the set of positive integers that are multiples of 4 is such a set!

S4 = {4, 8, 12, 16, … }

The cardinality of the set above is also ℵ0 !!!! Now that should bother you. If what was just stated is true then |ℤ | == |S4| which means they have the same cardinality! But how can that be? Clearly S4 is a proper subset of ℤ correct? That is, every element of S4 is contained in ℤ but ℤcontains elements not found in S4.

This is the beauty and the mystery of working with infinities. The two sets above are of the same cardinality and yet one of them is a proper subset of the other! Strange but true. This may lead you to assume that all infinities are of equal cardinality. That is, given two sets that contain an infinite number of elements, then they have equal cardinality – right? Wrong.

Remember the set of all real numbers? Let us call it ℝ this set is clearly infinite. But is it countable? If you are given an element in the set, can you provide the “next” element? You might be tempted to say “yes” but you would be wrong. If you were given 3.45 then what is the next real number? If you said 3.46 then you are wrong. Consider those two values 3.45 and 3.46. Are there any real numbers between them? Yes. For example 3.455 lies between them. So does 3.4537654. In fact, there are an infinite numbers of real numbers that lie between 3.45 and 3.46. Obviously there is no magic property of these two real numbers. Given ANY two real numbers we will find that there are an infinite collection of reals that lie between them! Thus ℝ is NOT a countable infinity.

Again, you would need to study more advanced set theory courses but it turns out that not all infinities are of equal cardinality. We have the countable infinity ℵ0 and an uncountable infinity which is often called the power of the continuum ℂ .

It turns out that |ℵ0 | < |ℂ| . Strangely, this fact turns out to be essential to understanding a problem known as undecidability in computational theory.

Set Union

Given two sets S and T we can produce a new set S∪T known as the union of S and T by creating a new set that contains all of the elements found in either S or T or both (but obviously without duplicates since sets do not allow duplicate elements).

For example, if S = { a,c,g, 5} and T = { 1,5, c, 8, H} then S∪T = {a,c,g,1,5,8,H}

Note that the elements c and 5 appear only once in the union set.

There are a few important properties of set union which are worth noting.

S∪S = S, obviously nothing new is added or removed.
S∪∅=S, since the empty set can add nothing new to the union

S∩U = S, only those elements of S will be found also in U.

Power Set of S

Any objects can be elements of a set. This includes other sets! For example, all of the following are sets.

S1 = { a, b, c, d }
S2 = { 1, {e,r,t}, 3, {1,3,5,7,9} }
S3 = { {a,b,c}, ∅ , {a,b}, {0,1,2,3}}

Clearly, S1 is a standard set of 4 elements but sets S2 and S3 are also 4 element sets! In S2, the first and third elements are the digits 1 and 3 but the second and fourth elements are themselves sets. Set S3 contains 4 elements, all of which are themselves sets, including the empty set.

The power set 2S of a set S is the set containing all of the subsets of S. For example,

S = { 0, 3, 6} 2S = {∅, {0}, {3}, {6}, {0,3,}, {0,6}, {3,6}, {0,3,6} }

NOTE that the power set of S contains both the empty set and the set S itself since both are subsets of S!!!

You might also note that the notation used for the power set 2S reflects the cardinality of the power set of any set S. That is, if |S| = x, then the |2S | = 2x

So, if |S| = 5, then the power set of S will contain 25 or 32 elements.

Now if you really like strange math-facts or want to freak out your friends and neighbors then point out to them that |2ℵ0| == |ℂ| which is pretty cool…. If you take the power set of aleph-naught it is the same cardinality as the power of the continuum.

Set Difference and Complement

The set difference of two sets S and T is a set containing the elements found in S but NOT found in T. That is

S-T = { x | x∊S and x∉T}

For example,

S = {a,b,c,d,e,f} T = {a,c,d,e} then S-T={b,f}

Note the following properties of set difference:

S-S=∅
S-∅=S

Now that we have defined set difference, we can define the complement of the set S. For this set of notes we will represent the complement of a set S as S’ . Given a universal set U and a set built from it named S we can define S’ as follows:

S’ = { x | x∊U and x∉S} = U-S

That is, the complement of a set S is the set of elements NOT in S but found in the universal set. So if our universal set were the set of all integers and S was the set of all odd integers then S’ would be the set of all even integers as they are a part of the universal set but not found in S.

Cartesian Products SxT

The Cartesian product of two sets S and T, represented as SxT, is the set of all ordered pairs (x,y) where x∈S and y∈T.

OK – that’s a bit much to easily digest but it is a pretty easy concept once you see an example or two.

Given two sets S and T we simply create a new set containing all of the possible pairs (x,y) using the lements x from S and y from T. For example,

S={a,b,c} T={1,2} then SxT = { (a,1), (a,2), (b,1), (b,2), (c,1), (c,2) }

Notice that each element of the Cartesian product is an ordered pair. For example the third element is the ordered pair (b,1) where the b comes from the set S and the 1 from the set T. Also note that all possible pairs are listed.

The cardinality | SxT | = |S| * |T|, so, for example, if |S|=4 and |T|=6, then |SxT| = 24.

You should note that SxT ≠TxS. This is because the ordering of the pairs does matter. That is, (a,1) and (1,a) are tow different ordered pairs!!!!

Relations and Functions

We can think of a relation between a set S and a set T to be a subset of the Cartesian product SxT. That is, a relation maps elements from S to corresponding elements in T.

When we talk about a relation R on sets S and T, SRT we often refer to the set S as the domain of the relation and the set T as the range of the relation. For example, if we let the set S below be our domain and the set T below to be the range, then we can define a relation R as shown.


S∪U= U, since the universal set already contains all possible elements in S.

Set Intersection

Again, given two sets S and T we can create a new set S∩T known as the intersection of S and T by adding to the new set only those elements that appear only in both S and T. That is, any element in S∩T must be found in S and must also be an element of T.

For example, S = { 1,2,3,4,5,6} and T={2,4,6,8,10} then S∩T ={2, 4, 6}

Note that the elements 1,3,5,8,10 do NOT appear in both S and T and are thus not included in the intersection of the two sets.

Similar to Union, we have some important properties worth noting about the intersection.
S∩S = S, since any element in S is found in S.
S∩∅ = ∅ , since the empty set contains no elements and thus none will be found in S.

S = { 1,2,3,4,5,6} T = { 0, 1} SRT={ (1,1), (2,0), (3,1), (4,0), (5,1), (6,0) }

Note that SRT is clearly a subset of SxT and in fact a proper subset of it. You might wonder why this matters. Well look again at our example. Note that we could define R to be the relation that maps an element x in the set S to the corresponding element y in T that represents the remainder of X divided by two. That is, since 1,3,5 are odd their remainder when divided by two is 1 and so the pairs (1,1) (3,1) and (5,1) are in our set. Similarly, the values (2,0) (4,0) and (6,0) are also present since their remainder when divided by two is 0.

A function is simply a relation that is well-behaved – that is, in a function, each and every element in the domain maps to one and only one element in the range. Our example above turns out to have been a function. As you can see, all of the elements in our domain S were mapped to some element in T and each was only mapped to a single element. Note however, that if we had added the pair (6,1) to the relation R then it would have NOT been a function since the element 6 of our domain S would have been mapped to two different values in the range T – namely, (6,0) and (6,1).

Note that we often represent a function using what is known as functional notation. So for example if our domain set S were {1,2,3,4,5} and our range set were {2,4,6,8,10} and our function f was { (1,2), (2,4), (3,6), (4,8), (5,10)} we could represent it as f(1)=2, f(2)=4, f(3)=6, f(4)=8, f(5)=10. This allows us to capture many functions in a concise fashion. So in this example we could describe the function f as f(x)=2*x.

One to One and Onto Functions

As mentioned, functions are relations that map every item from the domain to some item in the range. Certain functions have additional properties that can be useful. The first such property is one-to-one (often written 1-1).

A 1-1 function maps each individual item x of the domain to a distinct item in the range set. That is, if x and y are elements of the domain, then ∀x,y∈domain, f(x)≠ f(y). So no two elements of the domain will ever map to the same element of the range. Our previous example is such a function.

An onto function is one which maps some element/elements of the domain to every single element of the range. We say the function “covers” the range meaning that every item in the range is mapped to by at least one element of the domain.

Consider, domain={-1,1,-2,2,-3,3} range={1,4,9} and f(x)=x2

Clearly this is NOT a 1-1 function as f(-2) = f(2) = 4. So since two different elements of the domain map to the same element of the range it cannot be 1-1. It IS however an onto function. This is because every element of the range is mapped to by at least one element of the domain.

 


100% Plagiarism Free & Custom Written,
Tailored to your instructions


International House, 12 Constance Street, London, United Kingdom,
E16 2DQ

UK Registered Company # 11483120


100% Pass Guarantee

STILL NOT CONVINCED?

View our samples written by our professional writers to let you comprehend how your work is going to look like. We have categorised this into 3 categories with a few different subject domains

View Our Samples

We offer a £ 2999

If your assignment is plagiarised, we will give you £ 2999 in compensation

Recent Updates

Details

  • Title: UNDERSTANDING OF KEY CONCEPTS IN MANY AREAS OF MATHEMATICS AND COMPUTING
  • Price: £ 140
  • Post Date: 2024-08-28T18:23:38+00:00
  • Category: Assignment
  • No Plagiarism Guarantee
  • 100% Custom Written

Customer Reviews

UNDERSTANDING OF KEY CONCEPTS IN MANY AREAS OF MATHEMATICS AND COMPUTING UNDERSTANDING OF KEY CONCEPTS IN MANY AREAS OF MATHEMATICS AND COMPUTING
Reviews: 5

A masterpiece of assignment by , written on 2020-03-12

The rates are a bit expensive for me of the essay writing service but the overall look is amazing. The references and formatting are done beautifully. So, I feel that the high rates are worth all these qualities. I want to thank you for great help.
Reviews: 5

A masterpiece of assignment by , written on 2020-03-12

Now I am happy that I made the right decision of coming to Insta Research for help. My term paper was so technical and analytical at the same time. I got really confused about what to do but got relaxed when I was given such a humble writer. He clarified my concepts with the best explanations and discussions. I almost interacted with him on daily basis within the writing process. The best feature of this site is quick delivery as I got the work before my deadline. Additionally, the term paper is written skillfully and handled quite professionally. Now I am able to take a deep sigh of relief and thank you all for such speedy help. The quality of the work made my day.