# Basic Structures: Sets, Functions, Etc.

Sets
Meaning of Sets

A set is an unordered collection of 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. A set is an unordered collection of objects, called elements or members of the set. A set is said to contain its elements. We write aA to denote that a is an element of the set A. The notation aA denotes that a is not an element of the set A.

There are two ways of describing, or specifying the members of, a set
The two ways are:

Roster method: refers to a technique in representing a set by directly listing all of its elements, which are separated by commas and enclosed by a pair of curly brackets.
Example: The set V of all vowels in the English alphabet can be written as V = {a, e, i, o, u}. Example: The set V of all vowels in the English alphabet can be written as V = {a, e, i, o, u}.

Set builder: We characterize all those elements in the set by stating the property or properties they must have to be members.
For instance, the set O of all odd positive integers less than 10 can be written as O = {x | x is an odd positive integer less than 10} or, specifying the universe as the set of positive property or properties they must have to be members.
For instance, the set O of all odd positive integers less than 10 can be written as O = {x | x is an odd positive integer less than 10} or, specifying the universe as the set of positive integers, as O={xℤ+ | x is odd and x < 10}.

Special Sets

We often use this type of notation to describe sets when it is impossible to list all the elements of the set. For instance, the set Q+ of all of the set. For instance, the set ℚ+ of all positive rational numbers can be written as
ℚ+={x ∈ | x = p / q, for some positive integers p and q}.
These sets, each denoted using a boldface letter, play an important role in discrete mathematics:
= {0, 1, 2, 3, ...}, the set of natural numbers
= {..., -2, -1, 0, 1, 2, ...}, the set of integers
ℤ+ = {1, 2, 3, ...}, the set of positive integers
= {p/q | p ∈ Z, q ∈ Z, and q ≠ 0}, the set of rational numbers {p/q | p ∈ Z, q ∈ Z, and q ≠ 0}, the set of rational numbers
, the set of real numbers
ℝ+, the set of positive real numbers
, the set of complex numbers.

The Empty Set and Naive Set Theory

The Empty Set:
The set with no members: ∅

Naive Set Theory:

Venn Diagrams

A Venn diagram (also called primary diagram, set diagram or logic diagram) is a diagram that shows all possible logical relations between a finite collection of different sets. These diagrams depict elements as points in the plane, and sets as regions inside closed curves.

Subsets

The set A is a subset of B iff every element of A is also an element of B. We use the notation AB to indicate that A is a subset of the set B.
We see that AB if and only if the quantification ∀x(x ∈ A → x ∈ B) is true.

The set A is a subset of B iff every element of A is also an element of B. We use the notation AB to indicate that A is a subset of the set B.
We see that AB if and only if the quantification ∀x(xAxB) is true.

Theorem for Subsets :

For every set S,

For every set S,

1. ∅ ⊆ S.
2. S ⊆ S. SS.

The set A is a subset of B iff every element of A is also an element of B. We use the notation AB to indicate that A is a subset of the set B.
We see that AB if and only if the quantification ∀x(x ∈ AxB) is true. The set A is a subset of B iff every element of A is also an element of B. We use the notation AB to indicate that A is a subset of the set B.
We see that AB if and only if the quantification ∀x(xAxB) is true.

The Size of a Set

Let S be a set. 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|.

Let S be a set. 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|.
Remark: The term cardinality comes from the common usage of the term cardinal number as the size of a finite set.
For Example: Let A be the set of odd positive integers less than 10. Then |A| = 5.

Power Sets

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).

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).
For Example:
If S is the set {x, y, z}, then the subsets of S are
{} (the empty set or the null set)
{x}
{y}
{z}
{x, y}
{x, z}
{y, z}
{x, y, z}
and hence the power set of S is {{}, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y, z}}.
Size of the power set of a set of size n is 2n. Why? See Pascal's Triangle

Cartesian Products

Let A and B be sets. The Cartesian product of A and B, denoted by A x B, is the set of all ordered pairs (a, b), where a ∈ A and b ∈ B. Hence,
A x B = {(a, b) | a ∈ A ∧ b ∈ B}.

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.
In other words, (a1, a2, ... , an) = (b1, b2, ... , bn) if and only if ai = bi, for i = 1, 2, ... , n.

Test Yourself!
1. How many subset/s does the power set of an empty set have?
1. Zero
2. Three
3. Two
4. One
2. What is the cardinality of the set of odd positive integers less than 10?
1. 5
2. 12
3. 10
4. 7
3. The set of whole numbers is ___
1. Finite
2. Empty
3. Infinite
4. ___ is a collection of objects
1. A proposition
2. Cardinality
3. A set
4. A function
5. If ∀x(x ∈ A → x ∈ B) is true, that means:
1. A ⊆ B
2. A and B are mutually exclusive sets
3. None of the above
4. B ⊆ A

1. d; 2. a; 3. c; 4. c; 5. a;

Set Operations

Two, or more, sets can be combined in many different ways.
For instance, starting with the set of mathematics majors at your school and the set of computer science majors at your school, we can form the set of students who are mathematics majors or computer science majors, the set of students who are joint majors in mathematics and computer science, the set of all students not majoring in mathematics, and so on.

Types of Set Operations
Union

Two sets can be "added" together. The union of A and B, denoted by AB, is the set of all things that are members of either A or B.

Examples:
{1, 2} ∪ {1, 2} = {1, 2}.
{1, 2} ∪ {2, 3} = {1, 2, 3}.
{1, 2, 3} ∪ {3, 4, 5} = {1, 2, 3, 4, 5}

Intersection

A new set can also be constructed by determining which members two sets have "in common". The intersection of A and B, denoted by AB, is the set of all things that are members of both A and B. If AB = ∅, then A and B are said to be disjoint.

Examples:
{1, 2} ∩ {1, 2} = {1, 2}.
{1, 2} ∩ {2, 3} = {2}.

Set Difference

Two sets can also be "subtracted". The relative complement of B in A (also called the set-theoretic difference of A and B), denoted by AB, is the set of all elements that are members of A but not members of B.

Complements

In certain settings all sets under discussion are considered to be subsets of a given universal set U. In such cases, UA is called the absolute complement or simply complement of A, and is denoted by an A with a bar over it.
For instance:
1. {1, 2} − {1, 2} = ∅.
2. {1, 2, 3, 4} − {1, 3} = {2, 4}.
Some basic properties of complements:
1. ABBA for AB.
2. AA = U.
3. AA = ∅.
4. A = A.
5. AA = ∅.
6. U = ∅ and = U.
7. AB = AB.

Set Identities

The fundamental laws of set algebra :

1. Commutative laws:
AB = BA
AB = BA
2. Associative laws:
(AB) ∩ C = A ∩ (B ∩ C)
(AB) ∪ C = A ∪ (B ∪ C)
3. Distributive laws:
A ∩ (B ∪ C) = (AB) ∪ (A ∩ C)
A ∪ (B ∩ C) = (AB) ∩ (A ∪ C)
4. Identity laws:
AU = A
A ∪ ∅ = A
5. Complement laws:
AA = U
AA = ∅
6. Idempotent laws:
AA = A
AA = A
7. Absorption laws:
A ∩ (AB) = A
A ∪ (AB) = A
De Morgan's laws

If A and B are any two sets then,

1. AB = AB
2. AB = AB
Computer Representation of Sets

There are various ways to represent sets using a computer. One method is to store the elements of the set in an unordered fashion. However:
Wastes time searching when doing union, intersection, etc.

We can represent set by a bit string: bit x is on if x is in the set.
For Example : Let U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, and the ordering of elements of U has the elements in increasing order; that is, ai = i. What bit strings represent the subset of all odd integers in U, the subset of all even integers in U, and the subset of integers not exceeding 5 in U?
Solution: The bit string that represents the set of odd integers in U, namely, {1, 3, 5, 7, 9}, is 10 1010 1010.
All even integers in U: 01 0101 0101.

Test Yourself!
1. The difference of {2,4,5} and {2,3,5} is the set:
1. {3}
2. {2,5}
3. {4}
4. {3,4}
2. The intersection of the sets {6,7,9} and {6,7,8} is the set:
1. {8,9}
2. {6,7}
3. {6}
4. Empty set
3. Which of the following laws says A ∩ U = A?
1. Identity
2. Complement
3. Idempotent
4. Absorption
4. What bit strings represent the subset of all odd integers in {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}?
1. 11 1111 1111
2. 10 1010 1010
3. 01 0101 0101
4. 00 0000 0000
5. Which one of the following is the distributive law?
1. A ∪ (A ∩ B) = A
2. A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
3. A ∪ ∅ = A A ∪ ∅ = A
4. (A ∪ B) ∪ C = A ∪ (B ∪ C) (A ∪ B) ∪ C = A ∪ (B ∪ C)

1. c; 2. b; 3. a; 4. b; 5. b;

Functions

A function is a relation between a set of inputs and a set of permissible outputs with the property that each input is related to exactly one output.
Let A and B be nonempty sets. A function f from A to B is an assignment of exactly one element of B to each element of A. We write f(a) = b if b is the unique element of B assigned by the function f to the element a of A. If f is a function from A to B, we write f : AB.

One-to-one Functions

A function f is said to be one-to-one, or an injunction, if and only if f(a) = f(b) implies that a = b for all a and b in the domain of f. A function is said to be injective if it is one-to-one.
Note that a function f is one-to-one if and only if f (a) ≠ f (b) whenever a ≠ b. This way of expressing that f is one-to-one is obtained by taking the contrapositive of the implication in the definition.
For example: Determine whether the function f from {a, b, c, d} to {1, 2, 3, 4, 5} with f(a) = 4, f(b) = 5, f(c) = 1, and f(d) = 3 is one-to-one?
Answer: The function f is one-to-one because f takes on different values at the four elements of its domain. as f(a) = 4, f(b) = 5, f(c) = 1, and f(d) = 3

Onto Functions

A function f from A to B is called onto, or a surjection, if and only if for every element bB there is an element a ∈ A with f(a) = b. A function f from A to B is called onto, or a surjection, if and only if for every element bB there is an element aA with f(a) = b. A function f is called surjective if it is onto.
For Example: Is the function f(x) = x + 1 from the set of integers to the set of integers onto?
This function is onto, because for every integer y there is an integer x such that f(x) = y. To see this, note that f(x) = y if and only if x + 1 = y, which holds if and only if x = y − 1.

Function Composition

The function composition of two functions takes the output of one function as the input of a second one. More specifically, the composition of f with a function g: YZ is the function (g º f: XZ) defined by
(g º f)(x) = g(f(x)).
The order of the composition can be important. For example, suppose f(x) = x2 and g(x) = x + 1. Then g(f(x)) = x2 + 1, while f(g(x)) = (x + 1)2, which is x2 + 2x + 1, a different function.

Inverse Functions

Let f be a one-to-one correspondence from the set A to the set B. The inverse function of f is the function that assigns to an element b belonging to B the unique element a in A such that f(a) = b. The inverse function of f is denoted by f−1. Hence, f−1(b) = a when f(a) = b.

Because f maps a to 3, the inverse f−1 maps 3 back to a. This function is onto, because for every integer y there is an integer x such that f(x) = y. To see this, note that f(x) = y if and only if x + 1 = y, which holds if and only if x = y − 1.

The Graphs of Functions

Two Important Functions

Let x be a real number. The floor function rounds x down to the closest integer less than or equal to x, and the ceiling function rounds x up to the closest integer greater than or equal to x.

Floor
Ceiling

Let x be a real number. The floor function rounds x down to the closest integer less than or equal to x, and the ceiling function rounds x up to the closest integer greater than or equal to x.

Test Yourself!
1. If f(x) = x3 and g(x) = x + 5 then g(f(x)) is equal to:
1. x3 + 125
2. x3 + 5
3. x6
4. (x + 5)3
2. Floor(-2.7) =
1. -2
2. -3
3. 2
4. -2.5
3. Ceil(-2.7) =
1. 2
2. -3
3. -2
4. -2.5
4. Which of the following functions is one-to-one, if the domain of x is the integers?
1. f(x) = x2 - 2
2. f(x) = xn - x where n > 0
3. f(x) = |x - 2|
4. f(x) = x3
5. Which of the following functions is an onto function, if the domain of x is the positive integers?
1. f(x) = x + 3
2. f(x) = x2
3. f(x) = x − 4
4. f(x) = x2 − 2
6. The inverse of f(x) = 2x + 3 is f -1y =
1. (y/2) - 3
2. (y - 2)/3
3. 2y + 3
4. (y - 3)/2

1. b; 2. b; 3. c; 4. d; 5. c; 6. d;

Sequences

A sequence is a function from a subset of the set of integers (usually either the set {0, 1, 2, ...} or the set {1, 2, 3,...}) to a set S. We use the notation an to denote the image of the integer. We call an a term of the sequence.
For Example: Consider the sequence {a}, where
a = 1/n
The list of the terms of this sequence, beginning with a1, namely, a1, a2, a3, a4,...,
starts with
1, 1/2, 1/3, 1/4,....

Types of Sequence
1. A geometric progression is a sequence of the form a, ar, ar2, ..., arn, ... where the initial term a and the common ratio r are real numbers.
2. An arithmetic progression is a sequence of the form a, a + d, a + 2d, ... , a + nd, ... where the initial term a and the common difference d are real numbers.
3. A recurrence relation for the sequence {an} is an equation that expresses an in terms of one or more of the previous terms of the sequence, namely, a0, a1, ... , an−1, for all integers n with nn0, where n0 is a nonnegative integer. A sequence is called a solution of a recurrence relation if its terms satisfy the recurrence relation. (A recurrence relation is said to recursively define a sequence. We will explain this alternative terminology in Chapter 5.)

The Fibonacci sequence, f0, f1, f2, ... , is defined by the initial conditions f0 = 0, f1 = 1, and the recurrence relation fn = fn − 1 + fn − 2 for n = 2, 3, 4,....
4. Summation (Σ) is the addition of a sequence of numbers; the result is their sum or total. If numbers are added sequentially from left to right, any intermediate result is a partial sum, prefix sum, or running total of the summation.
5. Look-and-say sequence
Test Yourself!
1. (21) + (22) + (23) +...+ (2n) =
1. 2((2n) - 1)
2. 2((2(n-1)) - 1)
3. 2(n-1)
4. 2((2(n + 1)) - 1)
2. Given the following terms a1=8 and a2=13, what is a3 in an arithmetic sequence?
1. 18
2. 21
3. 34
4. 26
3. Given the following terms a1=8 and a2=32, what is a3 in a geometric sequence?
1. 120
2. 40
3. 52
4. 128
4. Consider the sequence 7,7,7,7,7.. which one of the following is true?
1. Sequence is only geometric
2. Sequence is arithmetic and geometric
3. Sequence is neither arithmetic nor geometric
4. Sequence is only arithmetic
5. The recurrence relation for the sequence 1, 5, 9, 13, 17,.. is:
1. x(n+1)=2x(n)+1
2. x(n+1)=x(n)+4
3. x(n+1)+4=x(n)
4. x(n+1)=x(n)1/2

1. a; 2. a; 3. d; 4. b; 5. b;

Cardinality of Sets

The sets A and B have the same cardinality if and only if there is a one-to-one correspondence from A to B. When A and B have the same cardinality, we write |A| = |B|.

If there is a one-to-one function from A to B, the cardinality of A is less than or the same as the cardinality of B and we write |A| ≤ |B|. Moreover, when |A| ≤ |B| and A and B have different cardinality, we say that the cardinality of A is less than the cardinality of B and we write |A| < |B|.

Countable Sets

A set that is either finite or has the same cardinality as the set of positive integers is called countable. A set that is not countable is called uncountable. When an infinite set S is countable, we denote the cardinality of S by ℵ0 (where ℵ is aleph, the first letter of the Hebrew alphabet). We write |S| = ℵ0 and say that S has cardinality "aleph null."
For Example: Show that the set of all integers is countable.
Solution: We can list all integers in a sequence by starting with 0 and alternating between positive and negative integers: 0, 1, -1, 2, -2, ... Alternatively, we could find a one-to-one correspondence between the set of positive integers and the set of all integers. The function f(n) = n/2 when n is even and f(n) = -(n − 1)/2 when n is odd is such a function. Consequently, the set of all integers is countable.

A surprising result: The rational numbers are countable.
How do we order them?
All rational numbers p/q where p + q add to 2, then all where they add to 3...
So...
1/1, 1/2, 2/1, 1/3, 3/1, 1/4, 2/3, 3/2, 4/1...

An Uncountable Set

An uncountable set (or uncountably infinite set) is an infinite set that contains too many elements to be countable. The uncountability of a set is closely related to its cardinal number: a set is uncountable if its cardinal number is larger than that of the set of all natural numbers.
There is an injection from the smaller set to the larger set, but no bijection.

Theorems
1. If A and B are countable sets, then AB is also countable.
2. SCHRÖDER-BERNSTEIN THEOREM
If A and B are sets with |A| ≤ |B| and |B| ≤ |A|, then |A| = |B|. In other words, if there are one-to-one functions f from A to B and g from B to A, then there is a one-to-one correspondence between A and B.
Test Yourself!
1. If A and B are countable sets then:
1. A ∪ B is also countable
2. A < B
3. B < A
4. A is a subset of B
2. What is the cardinality of the power set of the set {1,2,4}?
1. 3
2. 8
3. 6
4. 5
3. The cardinality of A = {5,6,3,2,3,2} is:
1. 6
2. 4
3. 7
4. 5
4. True or False: a set is uncountable if its cardinal number is larger than that of the set of all natural numbers
1. False
2. True
5. True or False: the set of all integers is uncountable
1. True
2. False