Introduction to Sets

Sets

• A set is an unordered collection of objects
• Objects in a set are called elements or members
• The notation a ∈ A denotes that a is an element. For example, a belongs to A
• a ∉ A means that a is not a member of A

Describing a Set

Roster Method

• Elements are listed explicitly
• Order is not important
• Ellipses (...) describe sets without listing all members when the pattern is clear

Important Sets

• N = natural numbers = {1,2,3....}
• W = Whole numbers = {0,1,2,3....}
• Z = integers = {...,-3,-2,-1,0,1,2,3,...}
• Z+ = positive integers = {1,2,3,.....} = N
• Q = rational numbers
• R = set of real numbers
• R+ = set of positive real numbers
• C = set of complex numbers

Set-Builder Notation

• Property or properties that all members must satisfy are specified
• S = {x | x is a positive integer less than 100}
• A predicate may be used: S = {x | P(x)}

Interval Notation

• [a,b] = {x|a≤x≤ b}
• [a,b) = {x|a≤x0
• Empty set is different from a set containing the empty set; Ø ≠ {0}

Set Equality

• Two sets are equal if and only if they have the same elements
• If A and B are sets, then A and B are equal if and only if ∀x(x ∈ A ↔ x ∈ B)

Subsets and Proper Subsets

• The set A is a subset of B, if and only if every element of A is also an element of B
• The notation A ⊆ B indicates that A is a subset of the set B
• A ⊆ B holds if and only if ∀x(x∈ A → x ∈ B) is true
• If A ⊆ B, but A ≠B, then A is a proper subset of B, denoted by A ⊂ B

Cardinality of Sets

• The cardinality of a finite set A, denoted by |A|, is the number of (distinct) elements of A and means #elements in A

Power Sets

• The set of all subsets of a set A, denoted P(A), is called the power set of A
• If a set has n elements, then the cardinality of the power set is 2^n

Tuples

• The ordered n-tuple (a1,a2,...,an) is the ordered collection that has a₁ as its first element and a₂ as its second element and so on until aₙ as its last element
• Two n-tuples are equal if and only if their corresponding elements are equal
• 2-tuples are called ordered pairs
• The ordered pairs (a,b) and (c,d) are equal if and only if a = c and b = d

Cartesian Product

• The Cartesian Product of two sets A and B, denoted by A X B is the set of ordered pairs (a,b) where a ∈ A and b ∈ B
  • AxB = {(a,b)|ає А and bє B}

Set Operations

• Let A and B be sets. The union of the sets A and B, denoted by AUB, is the set: {x | x ∈ A v x ∈ B}.
• The intersection of sets A and B, denoted by A ∩ B, is {x|x ∈ A ^ x ∈ B}.
• If the intersection is empty, then A and B are said to be disjoint
• If A is a set, then the complement of the A (with respect to U), denoted by A, is the set U - A = {x | x ∈U \x ∉ A}
• The complement of A is sometimes denoted by Ac
• The difference of A and B, denoted by A - B, is the set containing the elements of A that are not in B
  • A- B = {x | x ∈ A ^ x ∉ B}= A ∩ B

Theorem

• A ∪ B = all elements in both sets
• x∈ A ∪ B ⇔ x ∈ A V x ∈ B.
• If the intersection of A and B = elements in common
• x∈ A ∩ B ⇔ x ∈ A Λ x ∈ B.

Laws, Identities and Proofs

• See tables in content for the various set laws and identities with associated 'logic'
• DeMorgan's Laws can be proven using different methods

Membership Tables

• Verify that elements in the same combination of sets always either belong or do not belong to the same side of the identity
• Use 1 to indicate it is in the set and a 0 to indicate that it is not

Functions:

• A function f from A to B, denoted f: A→ B is an assignment of each element of A to exactly one element of B
• Write f(a) = b if b is the unique element of B assigned by the function f to the element a of A

Domain and Codomain

• Functions are sometimes called mappings or transformations (of sets)

Representing Functions

• Functions may be specified in different ways, including explicit statements and/or formulas

Function Types

• In functions, each input has only one output
• Bijections: (1-1 and onto) - A function f is a one-to-one correspondence, or a bijection, if it is both one-to-one and onto (surjective and injective)
• Injections: A function f is said to be one-to-one, or injective, if and only if f(a) = f(b) implies that a = b for all a and b in the domain of f
• A function f is called an injection if it is one-to-one, where each element in the codomain has at most one preimage.
• Surjections: A function f from A to B is called onto or surjective, if and only if for every element b∈ B there is an element a ∈ A with f(a)=b and where f(A) = B or Range (f) = B

Inverse Functions

• Let f be a bijection from A to B. Then the inverse of f, denoted f −1, is the function from B to A defined as f −1(y) = x iff f (x) = y
• No inverse exists unless f is a bijection

Composition of Functions

• Let f: B→C, g: A→B
• The composition of f with g, denoted fog is the function from A to C defined by fog(x) = f(g(x))

Important Functions

• The floor function, denoted f(x) = ⌊x⌋ is the largest integer less than or equal to x
• The ceiling function, denoted f(x) = ⌈x⌉ is the smallest integer greater than or equal to x