Generated with Monsha

Save this resource to edit, expand, or export it, or create more resources for free.

Discrete Mathematics: Set Theory and Induction Assessment

Questions
University (Grade 13)
English

Discrete Mathematics: Set Theory, Relations, and Induction Assessment

Set Theory and Logic Assessment

1. In the context of Russell's Paradox (1902), consider the set

. Which of the following statements best describes the logical consequence of the existence of

in naive set theory?
A. The assumption

logically necessitates that

, while the assumption

necessitates that

. B. The set

is equivalent to the universal set

, which contains itself, thus resolving the contradiction. C. The paradox is avoided by defining

as a proper class rather than a set, allowing

to be false without contradiction. D. The contradiction is resolved by the Empty Set Axiom, which proves that

must be empty.
2. According to the construction of natural numbers using the successor function

where

, which of the following represents the set identified as '2'?
A.

B.

C.

D.

3. Let

be a set with

elements. If we define the power set of

as

, what is the cardinality of

?
A. 1 B. 2 C. 4 D. 16
4. The Extensionality Axiom states that two sets are equal if and only if they have exactly the same elements. Which of the following is a direct logical consequence of this axiom?
A. Every set is a subset of the power set of its union. B. A set cannot be an element of itself. C. For any set

, the set

is distinct from the singleton

. D. The empty set

is unique.
5. Using the Kuratowski definition (1921), an ordered pair is defined as

. What is the result of the operation

?
A.

B.

C.

D.

6. Given two relations

and

, the composition

is defined in the provided materials. If

and

, what is

?
A.

B.

C.

D.

7. A relation

is defined as functional if for every

, there is at most one

such that

. For

to be considered a 'total function' from

to

, what additional condition must be met?
A.

B.

C.

D.

must be injective.
8. Let

be a partial function. The preimage (inverse image) of an element

is denoted as

. Which condition guarantees that

?
A.

is in the input domain of

. B.

is a total function. C.

is a universal relation. D.

.
9. In the Principle of Complete Induction for

, the induction hypothesis used to prove

is more powerful than in ordinary induction. Which of the following represents the hypothesis for Complete Induction?
A.

B.

only C.

D.

10. A function

is defined by primitive recursion as

and

. If

,

, and

, what is the value of

?
A. 7 B. 11 C. 13 D. 17
11. Regarding the generalized intersection operation

, why does the provided material state that

is not defined?
A. Because the intersection of no sets must result in the empty set, which is a contradiction. B. Because the empty set has no elements to serve as a bound for the subset axiom. C. Because the definition

would be vacuously true for all

, implying a set of all sets. D. Because the intersection operation is only valid for finite collections of sets.
12. A set

is defined as 'inductive' if it satisfies two specific conditions. If a set

is inductive, which of the following must be true?
A.

is a finite set. B.

contains only the empty set. C.

. D.

.
13. The Axiom of Infinity is essential in Zermelo-Fraenkel Set Theory because it guarantees:
A. The existence of at least one inductive set. B. That the power set of any set is larger than the set itself. C. That the union of any collection of sets is a set. D. That the successor of any natural number is also a natural number.
14. Consider the property

. Based on the provided examples, what is the smallest base case

for which this property can be proven using induction?
A.

B.

C.

D.

15. If

is an ordered pair defined by Kuratowski's method, which set represents the 'second coordinate' or 'second projection'

?
A. The set

such that

. B. The set

such that

. C. The unique element

extracted from the structure of

. D. The set

.
16. Given a set

, the successor set is defined as

. Which of the following is always true regarding the relationship between

and

?
A.

B.

C.

D.

17. The 'Subset Axiom' (also known as the Axiom of Specification) allows for the construction of a set

. What is the primary restriction of this axiom compared to naive comprehension?
A. The elements

must be chosen from a pre-existing set

. B. The property

cannot involve any logical quantifiers. C. The resulting set

must be a subset of the empty set. D. It only applies to sets of natural numbers.
18. In the study of relations, the universal relation on sets

and

is denoted as

. If

and

, what is the universal relation?
A.

B.

C.

D.

19. Let

be the identity relation on set

. What are the domain and range of

?
A.

,

B.

,

C.

,

D.

,

20. According to the proposition on the associativity of composition, which of the following equalities holds for relations

,

, and

?
A.

B.

C.

D.


Discrete Mathematics: Set Theory and Induction Assessment

Set Theory and Logic Quiz

1. Which axiom of Zermelo-Fraenkel Set Theory ensures that if two sets have exactly the same elements, they are identical?
A. Extensionality Axiom B. Empty Set Axiom C. Pairing Axiom D. Subset Axiom
2. Russell's Paradox specifically demonstrates a contradiction in naive set theory when defining a set as the collection of all sets that:
A. Contain an infinite number of elements B. Do not contain themselves as a member C. Are proper subsets of the empty set D. Are defined by recursive functions
3. In the von Neumann construction of natural numbers, the set identified as '2' is composed of which elements?
A.

B.

C.

D.

4. According to the Power Set Axiom, if a finite set

has exactly

elements, how many elements are contained in its power set

?
A.

B.

C.

D.

5. The Subset Axiom (Axiom of Specification) prevents paradoxes by requiring that when defining a new set based on a property

:
A. The elements must be selected from a pre-existing set

B. The property

cannot involve the empty set C. The resulting set must be finite D. The elements must be natural numbers
6. Using Kuratowski's definition (1921), which set-theoretic structure correctly represents the ordered pair

?
A.

B.

C.

D.

7. Given the sets

and

, which of the following represents the Cartesian product

?
A.

B.

C.

D.

8. For a binary relation

, the domain of

, denoted

, is formally defined as:
A. The set of all elements in

related to some

B. The set of all ordered pairs contained within

C. The union of sets

and

D. The set of elements

such that there exists some

with

9. The identity relation

on a set

is defined as

. If

, which set represents

?
A.

B.

C.

D.

10. A relation

between sets

and

is considered "functional" if and only if:
A. Every element in

is mapped to at least one element in

B. For every

, there is at most one

such that

C. The range of the relation is exactly equal to the set

D. The sets

and

are identical
11. A partial function

is categorized as a "total function" (or simply a function) when:
A. Its range is a subset of

B. It is an empty relation C. Its domain

is exactly equal to the input set

D. It maps every element of

to the same unique element in

12. Given a function

and an element

, the set

is defined as the:
A. Image of

B. Domain of

C. Range of

D. Preimage (or inverse image) of

13. For two functions

and

, the composition

is defined as the function that:
A. Maps

to

B. Maps

to

C. Represents the union of the graphs of

and

D. Is the Cartesian product of the domains of

and

14. In the Principle of Induction (Version 3), what does the term "induction hypothesis" specifically refer to?
A. The verification that the property holds for the base case

B. The assumption that the property

holds for an arbitrary

C. The final proof that the property holds for all natural numbers D. The process of testing small values to find a pattern
15. Complete Induction differs from ordinary induction primarily because the induction hypothesis in complete induction assumes:
A. The property holds only for the initial base case B. The property holds for the specific successor value

C. The property holds for all values

such that

D. The property holds for all infinite sets simultaneously
16. In axiomatic set theory, the Axiom of Infinity is necessary to guarantee the existence of a set that is:
A. Non-empty and finite B. Equal to its own power set C. A singleton containing only the empty set D. Inductive
17. The Theorem of Recursion on

states that given a fixed element

and a function

, there exists:
A. A unique function

satisfying the recursive definition B. Multiple valid functions

that can satisfy the definition C. A relation that cannot be classified as a function D. A set

that is proven to be empty
18. Why is the intersection of an empty collection of sets, denoted

, considered undefined?
A. Because the empty set has no members to intersect B. Because it would logically contain all possible objects, making it too large to be a set C. Because the Subset Axiom requires the collection to be non-empty D. Because intersections are only defined for numeric sets
19. Given two sets

and

, the relative complement

is the set consisting of elements that are:
A. Elements of both

and

B. Elements of

that are not in

C. Elements of

that are not in

D. Elements that are not in the union of

and

20. The successor of a set

, which is the basis for defining natural numbers, is the set

defined as:
A.

B.

C.

D.