Basic Structures: Sets, Functions, Sequences, Sums, and Matrices Flashcards
Set: ( Intuitive Definition)
A set is an unordered collection of distinct objects, called elements or members of the set. A
set is said to contain its elements. We write a ∈ A to denote that a is an element of the set A.
The notation a ∉ A denotes that a is not an element of the set A.
Notations to represent Set:
- Roaster Method.
2. Set builder
Roaster Method:
Members of the set are listed between braces
The set V of all vowels in the English alphabet can be written as V = {a, e, i, o, u}.
OR
The set of positive integers less than 100 can be denoted by {1, 2, 3, … , 99}.
ellipses (…) are used when the general pattern of the
elements is obvious so as to be able to represent wout listing all its members.
Set Builder:
The general form of this notation is {x ∣ x has property P} and is read “the set of all x such that x has
property P.”
what are
N , Z, Q , R , C ?
N = {1, 2, 3, …}, the set of all natural numbers
Z = {… ,−2,−1, 0, 1, 2, …}, the set of all integers
Z+ = {1, 2, 3, …}, the set of all positive integers
Q = {p∕q ∣ p ∈ Z, q ∈ Z, and q ≠ 0}, the set of all rational numbers
R, the set of all real numbers
R+, the set of all positive real numbers
C, the set of all complex numbers
Intervals:
Sets of all the real
numbers between two numbers a and b, with or without a and b. If a and b are real numbers
with a ≤ b, we denote these intervals by
[a, b] = {x | a ≤ x ≤ b} –Closed Interval
[a, b) = {x | a ≤ x < b}
(a, b] = {x | a < x ≤ b}
(a, b) = {x | a < x < b}. – Open Interval
Remark: Some books use the notations [a, b[, ]a, b], and ]a, b[ for [a, b), (a, b], and (a, b), respectively.
What is a datatype or type?
A datatype or type is the name of a set, together with a set of operations that can be performed on objects from that set.
2 Sets are equal if:
Two sets are equal (A = B) if and only if they have the same elements. Therefore, if A and B are sets,
then A and B are equal if and only if ∀x(x ∈ A ↔ x ∈ B).
The order of elements does not matter.
The number of times an element occurs in set also does not matter as long as it is a member.
Empty Set:
Set with no elements aka Null Set.
Denoted by: ∅ or { }
Singleton Set:
A set with one element.
{∅} : Single element of this singleton is empty set itself.
Naive Set theory:
Set: Collection of objects. This is based on intuitive notion of objects.
The theory that results from this intuitive definition of the set, and the use of the intuitive notion that for any property whatever, there is a set consisting of exactly the objects of this property, leads to paradoxes.
To avoid this there is “Axiomatic Set Theory” : by building set theory beginning
with axioms.
This book uses Naive Set theory.
Venn Diagram:
and why are they used?
In Venn diagrams the universal set U, which
contains all the objects under consideration, is represented by a rectangle.
Inside this rectangle, circles or other
geometrical figures are used to represent sets. Sometimes points are used to represent the particular elements of the set.
Venn diagrams are often used to indicate the relationships between
sets.
SubSet and SuperSet:
The set A is a subset of B, and B is a superset of A, if and only if every element of A is also an
element of B. We use the notation A ⊆ B
[ ∀x(x ∈ A → x ∈ B) should be true]
to indicate that A is a subset of the set B. If, instead,
we want to stress that B is a superset of A, we use the equivalent notation B ⊇ A.
(So, A ⊆ B and B ⊇ A are equivalent statements.)
Determine If A is or not a subset of B:
Showing that A is a Subset of B:
To show that A ⊆ B, show that if x belongs to A then x also
belongs to B.
Showing that A is Not a Subset of B :
To show that A ⊈ B, find a single x ∈ A such that x ∉ B.
Theorem 1 , every non-empty set S has at least how many sets and who?
at least two subsets, the empty set and the set S itself. THEOREM 1 For every set S, i. ∅ ⊆ S ii. S ⊆ S.
Proper Subset:
A ⊂ B
A is a proper subset of B
if and only if
∀x(x ∈ A → x ∈ B) ∧ ∃x(x ∈ B ∧ x ∉ A)
Venn Diagram:
in Rect, a circle B and in it a circle A. show a point in B n, not A.
Show that two sets are equal:
To show that two sets A and B are equal, show that
A⊆ B and B ⊆ A.
A = B if and only if ∀x(x ∈ A → x ∈ B) & ∀x(x ∈ B → x ∈ A) or equivalently if and only if
∀x(x ∈ A ↔ x ∈ B),
A = {∅, {a}, {b}, {a, b}}
B = {x ∣ x is a subset of the set {a, b}}.
is A = B? or A ⊂ B?
Sets may have other sets as members. For instance, we have the sets
Note that these two sets are equal, that is, A = B.
Also note that {a} ∈ A, but a ∉ A
Cardinality of set S?
If there are exactly n distinct elements in S where n is a nonnegative integer,
we say that S is a finite set and that n is the cardinality of S. The cardinality of S is denoted
by |S|.
|∅| = 0.
When Is a set infinite:
A set is said to be infinite if it is not finite.
Power Set:
Given a set S, the power set of S is the set of all subsets of the set S. The power set of S is
denoted by P(S).
Careful:
Power set will have ∅ as its element and not {∅}.
Rest elements will all be sets as well.
How many elements will a power set have?
If a set has n elements, then its power set has 2^n elements.
BUT HOW!!?
I guess cuz every element has a choice of being present or being absent. so 2 multiplied n times.
Ordered n-tuples:
The ordered n-tuple (a1, a2, … , an) is the ordered collection that has a1 as its first element,
a2 as its second element, … , and an as its nth element
Remember sets are unordered, that’s why we need a different structure.
When are two ordered n tuples equal?
If and only if each corresponding pair of their
elements is equal. In other words, (a1, a2, … , an) = (b1, b2, … , bn) if and only if ai = bi
i = 1, 2, … , n.
Ordered Pairs:
Ordered 2-tuples
Cartesian product: of 2 sets
Let A and B be sets. The Cartesian product of A and B, denoted by A × B, is the set of all
ordered pairs (a, b), where a ∈ A and b ∈ B. Hence,
A × B = {(a, b) ∣ a ∈ A ∧ b ∈ B}.
Note that the Cartesian products A × B and B × A are not equal unless A = ∅ or B = ∅ (so
that A × B = ∅) or A = B (see Exercises 33 and 40). This is illustrated in Example 18.
Cartesian product of more than 2 sets:
The Cartesian product of the sets A1, A2, … , An, denoted by A1 × A2 × ⋯ × An, is the set of
ordered n-tuples (a1, a2, … , an), where ai belongs to Ai for i = 1, 2, … , n. In other words,
A1 × A2 × ⋯ × An = {(a1, a2, … , an) ∣ ai ∈ Ai for i = 1, 2, … , n}.
Note that when A, B, and C are sets, (A × B) × C is not the same as A × B × C
What is A^n ?
A^n = {(a1, a2, … , an) ∣ ai ∈ A for i = 1, 2, … , n}.
A^2 = A * A
What is a relation?
A subset R of the Cartesian product A × B is called a relation from the set A to the set B. The
elements of R are ordered pairs.
A relation from
a set A to itself is called a relation on A.
Recall the use of Set notations with Quantifiers:
Sometimes we restrict the domain of a quantified statement explicitly by making use of a particular notation.
For example, ∀x ∈ S(P(x)) denotes the universal quantification of P(x) over all
elements in the set S.
In other words, ∀x ∈ S(P(x)) is shorthand for
∀x(x ∈ S → P(x)).
Similarly, ∃x ∈ S(P(x)) denotes the existential quantification of P(x) over all elements in S.
That is,
∃x ∈ S(P(x)) is shorthand for ∃x(x ∈ S ∧ P(x)).
Truth Set:
predicate :P
domain : D
Truth set of P : set of elements x in D for which P(x)
is true.
{x ∈ D ∣ P(x)}.Relate the truth values over domain U
when considering Truth set of P(x) and both the quatifiers:
∀xP(x) is true over the domain U if and only if the truth set of P is the set U.
Likewise, ∃xP(x) is true over the domain U if and only if the truth set of P is nonempty.
- This exercise presents Russell’s paradox. Let S be the
set that contains a set x if the set x does not belong to
itself, so that S = {x ∣ x ∉ x}.
a) Show the assumption that S is a member of S leads to Links a contradiction.
b) Show the assumption that S is not a member of S leads
to a contradiction.
By parts (a) and (b) it follows that the set S cannot be defined as it was. This paradox can be avoided by restricting the types of elements that sets can have.
What is the union of sets?
Let A and B be sets. The union of the sets A and B, denoted by A ∪ B, is the set that contains
those elements that are either in A or in B, or in both.
A ∪ B = {x ∣ x ∈ A ∨ x ∈ B}.
In Venn diag, circle A and B will be both shaded.
What is the Intersection of sets?
Let A and B be sets. The intersection of the sets A and B, denoted by A ∩ B, is the set containing those elements in both A and B.
A ∩ B = {x ∣ x ∈ A ∧ x ∈ B}.
Venn diagram: Shade the part belonging to A and B both, overlapped area.
Disjoint Sets:
Two sets are called disjoint if their intersection is the empty set.
Principle
of inclusion-exclusion :
A ∪ B| = |A| + |B| − |A ∩ B|.
Enumeration
An enumeration is a complete, ordered listing of all the items in a collection. The term is commonly used in mathematics and computer science to refer to a listing of all of the elements of a set.
difference of sets A and B
A∖B :
Let A and B be sets. The difference of A and B, denoted by A − B, is the set containing those
elements that are in A but not in B. The difference of A and B is also called the complement
of B with respect to A.
A − B = {x ∣ x ∈ A ∧ x ∉ B}.
Venn Diag: Shade the circle A but which does not include B.
Complement of Set:
Let U be the universal set. The complement of the set A, denoted by A(bar), is the complement of
A with respect to U. Therefore, the complement of the set A is U − A.
A = {x ∈ U ∣ x ∉ A}.
U is a superset of A..
Venn Diag: Shade everything but A.
Identity laws
A ∩ U = A
A ∪∅= A
Domination laws
A ∪ U = U
A ∩∅=∅
Idempotent laws
Complementation law
Commutative laws
A ∪ A = A
A ∩ A = A
(Abar)bar = A
A ∪ B = B ∪ A
A ∩ B = B ∩ A
Associative laws
A ∪ (B ∪ C) = (A ∪ B) ∪ C
A ∩ (B ∩ C) = (A ∩ B) ∩ C
