UNIT 1. Basic Set Theory
Unit 1. Basic Set Theory - vocabulary.
|
1.1 Definition. A set is a well-defined collection of distinct objects.Two sets are equal if and only if every element of one is an element of the other (they have precisely the same elements). Sets are conventionally denoted with capital letters. |
||
|
1.2 Describing sets. Intensional definition (Semantic description): ”A is the set whose members are the first three natural numbers.” Extensional definition (The list of members in curly brackets): A = {1,2,3} or using a variable x and then defining the scope of x: A = {x I x > 0 and x < 4} “A equals x such that x is greater than 0 and x is less than 4.” |
||
|
1.3 Membership. If a is a member of A, this is denoted: a ∈ A If a is not a member of A, this is denoted: a ∉ B The number of elements in a particular set is a property known as cardinality (informally – this is the size of a set). |
||
|
1.4 Types of sets. |
||
|
an empty set |
a set with no elements
|
A= ∅ A= {} |
|
a singleton |
a set with only one element |
B = {a} |
|
a finite set |
a set that has a finite number of elements Set C is a finite set of 3 elements. |
C = {a,b,c}
|
|
an infinite set |
a set that is not a finite set (a set with infinite number of elements) |
D= {…-2,-1,0,1,2,…} (the set of all integers) |
|
a countable set
|
a set with the same cardinality as some subset of the set of natural numbers E is a countable infinite set. |
E= {…,-2,-1,0,1,2,…}
|
|
an uncountable set
|
A set that is not countable is called an uncountable set. F is an uncountably infinite set. |
F= (the set of all real numbers) |
|
1.5 A universe A universe is a class that contains as elements all the entities one wishes to consider in a given situation. |
||
|
1.6 Set operations. The union A ∪ B The union of A and B is the set of all elements that are members of either A or B. |
||
|
The intersection A ∩ B The intersection of A and B is the set of all elements that are members of both A and B. If A ∩ B = ∅ then A and B are said to be disjoint (see above). |
||
|
The relative complement A \ B (or A − B) The relative complement of B in A (also called: the set-theoretic difference of A and B ) is the set of all elements that are members of A but not members of B. |
||
|
The (absolute) complement A’= U \ A The complement of A are all elements of A’ that are not elements of A. |
||
|
The cartesian product A x B The Cartesian product of two sets A and B is the set of all ordered pairs (a,b) such that a is a member of A and b is a member of B. |
||
|
The symmetric difference AΔB = (A \ B) ∪ (B \ A) The symmetric difference of two sets is the set of elements which are in either of the sets and not in their intersection. |
||
|
1.7 Inclusion (containment). a subset / a superset A ⊆ B If every member of set A is also a member of set B, then A is said to be a subset of B or equivalently: B is a superset of A. All elements of A are also elements of B. A is contained inside B. a proper (strict) subset / a proper (strict) superset A ⊂ B If A is a subset of B, but there exists at least one element of B which is not an element of A (A is not equal to B) then A is a proper subset of B, and B is a proper superset of A. equal sets A = B If there doesn’t exist at least one element of B which is not an element of A, then A is equal to B. disjoint sets A ∩ B = ∅ Sets A and B are said to be disjoint if they have no element in common. Their intersection is an empty set. |
||
Unit 1. Basic Set Theory - reading.
Reading #1 Georg Cantor – the inventor of Set Theory.
Georg Cantor 1845 - 1918 (ca 1870)
|
Georg Ferdinand Ludwig Philipp Cantor (March 3, 1845 – January 6, 1918) was a German mathematician, best known as the inventor of set theory, which has become a fundamental theory in mathematics. Cantor established the importance of one-to-one correspondence between the members of two sets, defined infinite and well-ordered sets, and proved that the real numbers are "more numerous" than the natural numbers. In fact, Cantor's method of proof of this theorem implies the existence of an "infinity of infinities". He defined the cardinal and ordinal numbers and their arithmetic. Cantor's work is of great philosophical interest, a fact of which he was well aware. Cantor's theory of transfinite numbers was originally regarded as so counter-intuitive – even shocking – that it encountered resistance from mathematical contemporaries such as Leopold Kronecker and Henri Poincaré. The objections to Cantor's work were occasionally fierce: Poincaré referred to his ideas as a "grave disease" infecting the discipline of mathematics, and Kronecker's public opposition and personal attacks included describing Cantor as a "scientific charlatan", a "renegade" and a "corrupter of youth." Adapted from: http://en.wikipedia.org/wiki/Georg_Cantor |
Reading #2 Venn Diagram
John Venn 1834-1923 Logician and Matematician
|
A Venn diagram or set diagram is a diagram that shows all possible logical relations between a finite collection of sets.
|
Unit 1. Basic Set Theory - problems.
Problem #1.1 Definition. Fill in the empty spaces:
A set is a 1)....................of 2) ................... .Two sets are equal 3) ...................every element of one is an element of 4) ................... (they have precisely the same elements). Sets are 5) ................... with capital letters.
|
the other / well-defined collection / conventionally denoted / if and only if / distinct objects |
Problem #1.2 Describing sets. Give one example of:
a) an intensional definition;
b) an extensional definition.
Problem #1.3 Membership. Fill in the empty spaces:
If a is a member of A, this 1) ...................: a ∈ A If a is not 2)...................A, this is denoted: a ∉ B The number of elements in a particular set is a property known as 3)................... (informally – this is 4)...................).
|
the size of a set / a member of / cardinality / is denoted |
Problem #1.4 Types of sets. Fill in the empty spaces:
|
1) |
A set that is not countable is called an uncountable set. F is an uncountably infinite set. |
2) |
|
a countable set
|
3) |
E= {…,-2,-1,0,1,2,…} |
|
a finite set |
4) |
C = {a,b,c} |
|
A universe |
5) |
U |
|
6) |
a set with only one element |
B = {a} |
|
an empty set |
a set with no elements |
7) |
|
8) |
a set that is not a finite set (a set with infinite number of elements) |
D= {…-2,-1,0,1,2,…} (the set of all integers) |
|
a singleton / a set that has a finite number of elements Set C is a finite set of 3 elements / A= ∅ ; A= {} / a class that contains as elements all the entities one wishes to consider in a given situation / an infinite set / F= (the set of all real numbers) / a set with the same cardinality as some subset of the set of natural numbers E is a countable infinite set / an uncountable set |
Problem #1.5 A universe. Correct the mistake in the definition:
A universe is a class that contains as elements the entities one wishes to consider in a given situation.
Problem #1.6 Set operations. Fill in the empty spaces:
1) The set of all elements that are members of either A or B is called .................... . It is denoted .......... .
2) The set of all ordered pairs (a,b) such that a is a member of A and b is a member of B is called .................... . It is denoted .......... .
3) The set of all elements that are members of both A and B is called .................... . It is denoted .......... .
4) The set of elements which are in either of the sets and not in their intersection is called .................... . It is denoted .......... .
5) The set of all elements that are members of A but not members of B is called .................... . It is denoted ..........
6) All elements of A’ that are not elements of A are called .................... . They are denoted .......... .
Problem #1.7 Inclusion (containment). Match two halves of the definitions:
|
1) Two sets are equal if and only if |
a) then A is said to be a subset of B or equivalently: B is a superset of A. All elements of A are also elements of B. A is contained inside B. |
|
2) Sets A and B are said to be disjoint |
b) then A is a proper subset of B, and B is a proper superset of A. |
|
3) If every member of set A is also a member of set B, |
c) every element of one is an element of the other (they have precisely the same elements). |
|
4) If A is a subset of B, but there exists at least one element of B which is not an element of A (A is not equal to B), |
d) if they have no element in common. Their intersection is an empty set. |
Additional problems:
Problem #1/8 (example) Draw a Venn diagram to represent the relationship between the sets
X = {1,3,5,6,7,8,9} and Y = {2,4,6,7,8,10}
Solution We find that X ∩ Y = {6,7,8}. For the Venn diagram:
Step 1) Draw two overlapping circles to represent the two sets;
Step 2) Write down the elements in the intersection;
Step 3) Write down the remaining elements in the respective sets.
Problem #1/9 (example) Draw a Venn diagram to represent the relationship between the sets:
X = {1,2,3,4,5,6} and Y = {2,4,6}
Solution We find that: X ∩ Y = {2,4,6} which is equal to the set Y.
For the Venn diagram
Step 1) Draw one circle within another circle;
Step 2) Write down the elements in the inner circle;
Step 3) Write down the remaining elements in the outer circle.
Problem #1/10 Given U = {2,4,6,8,10,12,14,16,18,20}
X = {4,6,8,10} and Y = {8,10,12,14}
Find X ∪ Y and draw a Venn diagram to illustrate X ∪ Y. Explain the steps.
Problem #1/11 Given U = {2,4,6,8,10,12,14,16,18,20}
X = {2,8} and Y = {2,4,8,10,14,20}
Find X ∪ Y and draw a Venn diagram to illustrate X ∪ Y. Explain the steps.
Definitions, pictures and articles for reading adapted from:
http://en.wikipedia.org/wiki/Georg_Cantor http://en.wikipedia.org/wiki/Transfinite_number
http://en.wikipedia.org/wiki/Venn_diagram ; http://en.wikipedia.org/wiki/John_venn