d420 Discrete Math: Functions and Relations - Set 3 - Part 1

Correct Answer: ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣

The principle of inclusion-exclusion provides a formula for calculating the size of the union of two sets, accounting for the overlap (intersection) between them.

Correct Answer: If there are more items than containers, at least one container must contain more than one item

The pigeonhole principle states that if more items are placed into containers than there are containers, at least one container must contain more than one item.

Correct Answer: An ordered arrangement of elements

A permutation is an ordered arrangement of elements from a set, where the order matters.

Correct Answer: A permutation is ordered, but a combination is unordered

In a permutation, the order of elements matters, while in a combination, the order does not matter.

Correct Answer: There are n ways to complete the first task and m ways to complete the second task, so there are nm ways to complete both tasks

The multiplication rule states that if one task can be completed in n ways and another in mmm ways, then both tasks can be completed in nmnmnm ways.

Correct Answer: If n objects are placed into k containers, at least one container must contain more than n/k objects

The generalized pigeonhole principle states that if n objects are placed into k containers, at least one container must contain more than [n/k] objects.

Correct Answer: A function where every element of the domain maps to a unique element in the codomain

An injective function is one where distinct elements in the domain map to distinct elements in the codomain.

Correct Answer: The set of all integers greater than or equal to zero

The set of natural numbers N consists of all non-negative integers, including zero.

Correct Answer: The set of numbers that can be expressed as a fraction a/b, where a and b are integers and b≠0

The set of rational numbers Q includes all numbers that can be expressed as a ratio of two integers.

Correct Answer: The number of elements in the set

The cardinality of a set is the number of elements contained within the set.

Correct Answer: The set of all possible subsets of a

The power set of a set a is the set of all subsets of a, including the empty set and a itself.

Correct Answer: Their intersection is the empty set

Two sets are disjoint if their intersection is the empty set, meaning they have no elements in common.

Correct Answer: The set of all elements in U that are not in A

The complement of A set a is the set of all elements in the universal set U that are not in A.

Correct Answer: A relation where each element of the domain is paired with exactly one element of the codomain

A function is a relation that assigns exactly one element of the codomain to each element of the domain.

Correct Answer: A relation that is reflexive, symmetric, and transitive

An equivalence relation is one that satisfies the properties of being reflexive, symmetric, and transitive.

Correct Answer: The set of elements in A that are not in B

The set difference A−B is the set of elements that are in A but not in B.

Correct Answer: It maps distinct elements of the domain to distinct elements of the codomain

An injective function ensures that each distinct element in the domain maps to a unique element in the codomain.

Correct Answer: The Cartesian product of sets A and B

The Cartesian product A×B represents the set of ordered pairs (a,b) where a∈A and b∈B.

Correct Answer: All of the above

A binary relation on a set can have various properties, including reflexivity, symmetry, and transitivity.

Correct Answer: Every element in the set is related to itself

A reflexive relation is one where every element in the set is related to itself.