D421 Discrete Math: Functions and Relations - Set 1 - Part 1

Correct Answer: A well-defined collection of distinct objects

A set is a well-defined collection of distinct objects called elements. Order does not matter and duplicates are not counted.

Correct Answer: ∈

The symbol ∈ means 'is an element of.' For example, 3 ∈ {1, 2, 3} states that 3 belongs to the set.

Correct Answer: A set containing no elements

The empty set, denoted ∅ or {}, contains no elements. It is a subset of every set.

Correct Answer: Every element of A is also an element of B

A ⊆ B means every element of A is also in B. A may equal B; if A is strictly smaller it is a proper subset.

Correct Answer: The set of elements in A or B or both

The union A ∪ B contains every element that is in A, in B, or in both.

Correct Answer: The set of elements common to both A and B

The intersection A ∩ B contains exactly the elements that belong to both A and B.

Correct Answer: Elements in A that are not in B

The difference A − B (or A \ B) consists of the elements that are in A but not in B.

Correct Answer: All elements of the universal set not in A

The complement of A contains every element of the universal set that is not in A.

Correct Answer: The number of elements in the set

Cardinality is the number of elements in a set. The set {a, b, c} has cardinality 3.

Correct Answer: 2^n

A set with n elements has 2^n subsets, since each element is either included or excluded, giving two choices per element.

Correct Answer: 8

With 3 elements the number of subsets is 2^3 = 8, including the empty set and the set itself.

Correct Answer: The set of all subsets of A

The power set P(A) is the set whose elements are all the subsets of A, and it has 2^n members for an n-element set.

Correct Answer: The set of all ordered pairs (a, b) with a in A and b in B

The Cartesian product A × B is the set of all ordered pairs where the first component comes from A and the second from B.

Correct Answer: 12

The Cartesian product has |A| times |B| ordered pairs, so 3 × 4 = 12.

Correct Answer: A subset of the Cartesian product A × B

A relation from A to B is any subset of A × B, meaning a set of ordered pairs linking elements of A to elements of B.

Correct Answer: The set of all first components of the ordered pairs

The domain is the set of all first elements appearing in the ordered pairs of the relation.

Correct Answer: The set of all second components of the ordered pairs

The range is the set of all second elements that appear in the ordered pairs of the relation.

Correct Answer: Every element is related to itself

A relation R on A is reflexive if (a, a) is in R for every element a in A.

Correct Answer: Whenever (a, b) is in R, (b, a) is also in R

A relation is symmetric if for every pair (a, b) in R, the reversed pair (b, a) is also in R.

Correct Answer: Whenever (a, b) and (b, c) are in R, (a, c) is also in R

A relation is transitive if (a, b) and (b, c) in R together imply (a, c) is in R.