Discrete Math

Tuesday

Set

A well-defined collection of objects or ideas.

Element

An object or idea that is a member of a set.

Roster Method

A method of representing sets by listing the elements that belong to the set.

Descriptive Method

A method of representing sets by describing the properties that the elements must possess.

Set-Builder Notation

A method of describing a set by stating the properties that its members must satisfy.

Set A

A = {a, e, i, o, u}

Set B

B = {𝑥 | 𝑥 is a letter of the alphabet}

Set C

C = {Alaska, Maine, Florida}

Set D

D = {1, 2, 5, 9}

Set E

E = {𝑥 | 𝑥 is an odd whole positive number}

Set F

F = {𝑥 | 𝑥 is a student in your school}

Set G

G = {President Eisenhower, President Kennedy, President Johnson}

Set H

H = {1, chair, automobile}

Set I

I = {𝑥 | 𝑥 is a whole number}

Set J

J = {𝑥 | 𝑥 is a day of the week that begins with letter A}

Basic Concepts of Sets

The fundamental ideas that define sets and their operations.

Undefined Terms

Terms that cannot be precisely defined but are understood intuitively, such as set and element.

Intuitive Understanding

The comprehension of concepts based on instinct rather than formal definitions.

Examples of Sets

Illustrations used to explain the concept of sets, such as the set of vowels or the set of states.

Mathematicians Boole and Cantor

Developers of set theory in the 19th century.

Properties of Sets

Characteristics that define the elements belonging to a set.

Collection of Objects

A group of items that can be classified as a set.

Well-Defined Collection

A collection where the elements can be clearly identified.

Set Notation

The symbolic representation used to denote sets and their elements.

Capital Letters in Sets

Used to name sets, such as A, B, and C.

Lowercase Letters in Sets

Used to represent the elements of the set, such as 𝑥, y, and 𝑧.

Separation of Elements

Elements in a set are separated by commas and enclosed in braces, { }.

Roster Method

A way to list all elements of a set when the number of elements is small.

Descriptive Method

A way to define a set when the number of elements is large, using a property that elements share.

Set E

E = {𝑥 | 𝑥 is an odd whole positive number}, meaning E is the set of elements such that each element is an odd whole positive number.

Roster Example of Set E

E = {1, 3, 5, ...}, where the three dots indicate that the sequence continues indefinitely.

Finite Set

A set that contains some fixed number of elements.

Infinite Set

A set that does not contain a fixed number of elements.

Element-Set Relation

An element can either belong to a set (indicated by ' ∈ ') or not belong to a set (indicated by ' ∉ ').

Symbol for Belongs To

The symbol ' ∈ ' indicates that an element belongs to a set.

Symbol for Does Not Belong To

The symbol ' ∉ ' indicates that an element does not belong to a set.

Example of Set A

A = {a, e, i, o, u}; then a ∈ A, b ∉ A, and t ∉ A.

Example of Set E

E = {1, 3, 5, ...}; then 3 ∈ E, 6 ∉ E, 13 ∈ E, and 100 ∉ E.

Equal Sets

Two sets A and B are equal (A = B) if every element of A is in B and every element of B is in A.

Example of Equal Sets

Let A = {1, 2, 3, 4} and B = {3, 4, 1, 2}; then A = B.

Order of Elements in a Set

The order of elements in a set is unimportant; changing the order does not change the set.

Example of Set A and Set B

Let A = {g, e, o, r} and B = {𝑥 | 𝑥 is a letter in President Washington's first name}; A = B.

Non-repetition in Sets

An element in a set is never repeated.

Example of Non-equal Sets

If A = {a, e, i, o, u} and B = {𝑥 | 𝑥 is a letter of the alphabet}, then A ≠ B.

Equivalent Sets

Two sets A and B are equivalent (𝐴≃𝐵) if for each element in A there is exactly one element in B and vice versa.

Example of Equivalent Sets

Let A = {1, 2, 3} and B = {a, b, c}; then 𝐴≃𝐵.

Subset

Set A is a subset of B if each element of A is an element of B, indicated by A ⊂ B.

Subset

A is contained in B or A is a subset of B.

Negation of Subset

A is not a subset of B is written A ⊄ B.

Self Subset

Every set is a subset of itself, that is, for any set A, we have A ⊂ A.

Proper Subset

Set A is a proper subset of set B if and only if set A is contained in set B and not equal to B. That is, if A ⊂ B and A ≠ B.

Improper Subset

Set A is an improper subset of set B if and only if set A is contained in set B and is equal to B. That is, if A ⊂ B and A = B.

Improper Subset Notation

To denote that A is an improper subset of set B, we write A ⊆ B.

Example of Proper Subset

Given A = {1, 2, 3, 4, 5}, B = {2, 4}, and C = {2, 4, 5, 6}, we have B ⊂ A and B ≠ A; B is a proper subset of A.

Example of Improper Subset

Given A = {1, 2, 3, 4, ...}, B = {1, 4, 9, 16, ...}, C = {x | x is a whole positive number squared}, we conclude B = C, B and C are improper subsets of one another.

Disjoint Sets

Two sets A and B are disjoint if and only if no element of set A is an element of set B and no element of set B is an element of set A.

Example of Disjoint Sets

Given A = {1, 3, 5, 7} and B = {2, 4, 6, 8}, then A and B are disjoint since A and B have no elements in common.

Example of Non-Disjoint Sets

Given A = {2, 3, 5, 7} and B = {1, 3, 6, 8}, then A and B are not disjoint since 3 ∈ A and 3 ∈ B.

Universal Set

The universal set, denoted by U, is the set containing all the elements under discussion.

Example of Universal Set

If we are discussing the sets formed from the letters in people's name, our universal set would then be all the letters of the alphabet, U = {a, b, c, d, ..., z}.

Null Set

The null or empty set, denoted by ∅ or { }, is the set containing no elements.

Example of Null Set

The set of past female presidents of the United States.

Example of Null Set

The set of all odd numbers that are evenly divisible by 2.

Subset of Null Set

The null set contains no elements, it is defined to be a subset of every set. That is, for any set A, we have ∅ ⊂ A.

Power Set

By the power set of a given set A, we mean the set of all possible subsets of set A.

Number of Subsets

If set A contains n number of elements, then there are 2^n number of subsets of A.

Example of Power Set

Find the power set of A = {1, 2}. Since the set contains 2 elements, there are 2^2 = 4 subsets of set A.

Power Set

The power set of 𝐴 is P(𝐴) = {∅, {1}, {2}, {1, 2}}.

Number of Subsets

Since the set contains 3 elements, there are 2^3 = 8 subsets of set 𝐵.

Complement

The complement of a set 𝐴 is the set of elements in the universal set which are not in set 𝐴.

Example of Complement

Let U = {1, 2, 3, 4, 5, 6, 7, 8} and 𝐴 = {1, 3, 6}; then 𝐴′ = {2, 4, 5, 7, 8}.

Union

The union of two sets 𝐴 and 𝐵, written 𝐴∪𝐵, is the set of elements that belong to 𝐴 or to 𝐵 or to both.

Example of Union

Let 𝐴 = {1, 3, 4, 6} and 𝐵 = {2, 3, 5, 9}; then 𝐴∪𝐵 = {1, 2, 3, 4, 5, 6, 9}.

Intersection

The intersection of two sets 𝐴 and 𝐵, written 𝐴∩𝐵, is the set of all elements which belong to both 𝐴 and 𝐵.

Example of Intersection

Let 𝐴 = {1, 2, 3, 5, 6} and 𝐵 = {2, 3, 4, 6, 8}; then 𝐴∩𝐵 = {2, 3, 6}.

Disjoint Sets

If 𝐴 and 𝐵 have no elements in common, then 𝐴∩𝐵 = ∅, implying that 𝐴 and 𝐵 are disjoint sets.

Difference

The difference of set 𝐴 minus set 𝐵, written 𝐴 - 𝐵, is the set of elements which belongs to 𝐴 but which do not belong to 𝐵.

Example of Difference

Let 𝐴 = {1, 2, 3, 4, 5, 6} and 𝐵 = {3, 5, 6, 7, 9}; then 𝐴 - 𝐵 = {1, 2, 4} and 𝐵 - 𝐴 = {7, 9}.

Subset

If 𝐴 is a subset of 𝐵, then 𝐴 - 𝐵 = ∅.

Example of Subset

Let 𝐴 = {1, 2, 3} and 𝐵 = {1, 2, 3, 4, 5}; then 𝐴 - 𝐵 = ∅ and 𝐵 - 𝐴 = {4, 5}.

Finding Complement of Intersection

To find (𝐴∩𝐵)′, first find 𝐴∩𝐵: 𝐴∩𝐵 = {3, 6}, then (𝐴∩𝐵)′ = {1, 2, 4, 5, 7, 8, 9}.

Union with Intersection of Complements

To find 𝐴∪(𝐵′ ∩𝐶), first find 𝐵′ = {1, 2, 5, 8, 9}, then 𝐵′ ∩𝐶 = {5, 8}, and finally 𝐴∪(𝐵′ ∩𝐶)= {2, 3, 5, 6, 8}.

Intersection of Complements

To find (𝐴∪𝐵)′ ∩(𝐴∪𝐶′), first find 𝐴∪𝐵 = {2, 3, 4, 5, 6, 7}, then (𝐴∪𝐵)′ = {1, 8, 9}, and finally intersect with (𝐴∪𝐶′) = {1, 9}.

Venn Diagram

Pictorial representation of sets and their relations.

Universal Set (U)

Set containing all possible elements in a context.

Proper Subset

Set A is a subset of B, excluding B.

Disjoint Sets

Sets with no elements in common.

Set Operations

Mathematical procedures involving sets, like union.

Inclusion-Exclusion Principle

Calculates size of union of overlapping sets.

Set Relations

Describes how sets interact, like subsets or intersections.

Elements of a Set

Individual items contained within a specific set.

Complement of a Set

Elements not in the specified set.

Intersection of Sets

Elements common to both sets.

Union of Sets

All elements from both sets combined.

Set A and B

Two sets that can have overlapping elements.

Set A is a subset of U

All elements of A are in the universal set.

Set A and B are not disjoint

Sets share at least one common element.

Elements x in A

x belongs to set A.

Elements x not in A

x does not belong to set A.

Set A is a proper subset of B

All elements of A are in B, but not vice versa.