When you start reading this, the first thing you should be asking yourselves is “What is Set Theory and why is it relevant?” Though Propositional Logic will prove a useful tool to describe certain aspects of meaning, like the reasoning in (1), it is a blunt instrument.
(1) a. Jacques sang and danced
Therefore: Jacques sang
b. If Jacques kisses Smurfette, she will slap Jacques
Jacques kissed Smurfette
Therefore: Smurfette slaps Jacques
Propositional Logic won’t help us with the argument in (2), which is why we will extend it to Predicate Logic.
(2) Every man is mortal
Aristotle is a man
Therefore: Aristotle is mortal.
Our intuitions tell us that if the first and second sentence are true, then the third necessarily follows. The reasoning goes like this. Suppose the first sentence is true: the collection of men is part of the collection of mortal things. Now suppose the second sentence is also true: Aristotle is a man. The first sentence says that if a thing is in the collection of men, it is also in the collection of mortal things. So it follows that Aristotle is a mortal thing (or simply mortal), which is what the third sentence states. The semantics of Predicate Logic is defined in terms of Set Theory.
A bunch of carrots, a classroom full of students, a herd of elephants: these are all examples of sets of things. Intuitively, you can think of a set as an abstract collection of objects, which may correspond to things in the world or to concepts, etc. A set is sometimes also called a collection.1 The objects that are collected in a set
are called its members or elements. So, a carrot, a student, and an elephant, are members of the sets described above. A Set may also contain other sets as its members.
I offer no definition of what a set is beyond the intuitive notion described above. Instead, I am going to show you what can be done with sets. This is a typical approach to Set Theory, i.e., sets are treated as primitive s of the theory and are not definable in more basic terms. I adopt the notation in (4) for convenience.
(4) a. Capital letters represent sets: A, B, C, …
b. Lower case letters represent members of sets: a, b, c, …, sometimes x, y, z, … The principal concept of Set Theory is belonging, i.e., elements belonging to sets. And this concept is represented using the membership relation, expressed by the rounded Greek letter epsilon ∈, as in (5). It’s negation is expressed using a barred epsilon ∉ as in (6).
(5) x ∈ A
x is an element of the set A.
(6) x ∉ A
x is not an element of the set A.
Elements
The objects in sets are called elements (or members).
If an element e belongs to set S this is represented as e∈S.
If an element f does not belong to set S this is represented as f∉S.
Writing sets
1. Listing method
All of the elements of a set are written.
A = {1, 3, 5, 7, 9}
2. Set - builder method
A typical element is named, along with its description, such as:
B = {x | x is an odd number from 1 to 10}
The vertical bar | is read: ‘‘such that’’, and it also can be written as :
3. Venn diagram
A Venn diagram is used for graphical representation of the set as a collection of its objects.
Example 1
This is a typical set, consisted of numbers 1, 2 and 3 listed inside of braces:
{1, 2, 3}
Alternatively we may choose to describe this set like this
{1, 2, 3} = { integers greater than 0 and less than 4 }
More formally, we may use this notation:
{1, 2, 3} = { x : x is an integer and 0 < x < 4} = { x : x Z, 0 < x < 4 }
Singleton set
Singleton set is a set with only one element.
A singleton set is different from the element itself and it is denoted by the element with surrounding braces.
Ex. 5 – this is number 5
{5} –this is singleton set containing number 5
Empty Set
A set with no elements in it is called an empty set.
This set is unique and it is denoted with the symbol Ø or with empty braces { }.
Infinite set
Set which contain an infinite number of elements is called infinite set.
These sets are often given by a few elements and ellipses which indicate that this sequence continues indefinitely.
A = {1, 2, 3, … }
Subsets
If all the elements of one set X are also elements of another set Y, then X is said to be a subset of Y. Similarly if elements of Z are not elements of another set Y so it is not a subset of Y.
Superset
If a set X is a subset of Y, then Y is said to be a superset of X. Every set is its own subset and superset. The empty set is a subset of all sets.
Example 2
Let A = {1, 2, 3} and B = {1, 2}.
B is a subset of A.
A is not a subset of B then notice that: n (B) < n (A).
SET OPERATIONS
Example: Let A = {10, 11, 12, 13} and B = {12, 13, 14}.
Intersection
Symbol A ∩ B denotes the intersection of two sets.
It is a set comprised of the elements which are in the both sets. We can write this as:
A ∩ B = { x| x∈ A and x ∈ B }
In the example A ∩ B = {12, 13}
If two sets have no elements in common, i.e. A ∩B = Ø we say that they are disjoint.
Union
Symbol A U B denotes the union of two sets.
It is a set comprised of the elements which are in the either set (at least one). We write this as:
A U B = { x : x ∈ A or x ∈ B }
In the example A U B = {10, 11, 12, 13, 14}
Universal set
The set containing all elements of a problem is called the universal set (ℰ).
That is a set from which elements may be considered.
(The notation comes from the French word ensemble).
Complement
If ℰ is universal set and A is a subset of ℰ, then the complement of a set A, denoted by A’, is the
set of all elements not in A.
A’ = { x : x ∉ A }
Cardinality of sets (Number of elements)
The number of elements in a set A is called its cardinality and is denoted by n (A)
Example. If A = {a, b, c, d, e, f} then n (A) = 6.
Properties of Cardinality:
1. n(Ø) = 0
2. n(A’) = n(ℰ) – n(A)
3. if A ∩ B ≠ Ø then
n(AUB) = n(A) + n(B) – n(A ∩ B)
4. if A ∩ B = Ø (disjoint sets) then
n(AUB) = n(A) + n(B)
Set-theoretic equalities
There are a number of general laws about sets which follow from the definitions of settheoretic
operations, subsets, etc. A useful selection of these is shown below. They are
grouped under their traditional names. These equations below hold for any sets X, Y, Z:
1. Idempotent Laws
(a) X ∪ X = X (b) X ∩ X = X
2. Commutative Laws
(a) X ∪ Y = Y ∪ X (b) X ∩ Y = Y ∩ X
3. Associative Laws
(a) (X ∪ Y) ∪ Z = X ∪ (Y ∪ Z) (b) (X ∩ Y) ∩Z = X ∩ (Y ∩ Z)
4. Distributive Laws
(a) X ∪ (Y ∩ Z) = (X ∪ Y) ∩ (X ∪ Z) (b) X ∩ (Y ∪ Z) = (X ∩ Y) ∪ (X ∩ Z)
5. Identity Laws
(a) X ∪ ∅ = X (c) X ∩ ∅ = ∅
(b) X ∪ U = U (d) X ∩ U = X
6. Complement Laws
(a) X ∪ X’ = U (c) X ∩ X’ = ∅
(b) (X’)’ = X (d) X – Y = X ∩ Y’
7. DeMorgan’s Laws
(a) (X ∪ Y)’ = X’ ∩ Y’ (b) (X ∩ Y)’ = X’ ∪ Y’
8. Consistency Principle
(a) X ⊆ Y iff X ∪ Y = Y (b) X ⊆ Y iff X ∩ Y = X
No comments:
Post a Comment