Back to Subject

Unit 2: Ordered Sets and Lattices - Practice Quiz

MTH265 — Discrete Mathematics For Computing 60 Questions
0 Correct 0 Wrong 60 Left
0/60

1 Which three properties define a partial order relation on a set?

introduction Easy
A. Reflexive, antisymmetric, and transitive
B. Reflexive, symmetric, and transitive
C. Irreflexive, symmetric, and transitive
D. Irreflexive, antisymmetric, and asymmetric

2 In an ordered set, the antisymmetric property states that if and , then which of the following must be true?

ordered sets Easy
A.
B.
C.
D.

3 What is a totally ordered set (also known as a chain)?

ordered sets Easy
A. A poset where no elements are comparable
B. A poset where every two elements are comparable
C. A poset with a finite number of elements
D. A poset that has a maximum and a minimum element

4 For a relation on a set to be reflexive, which condition must hold for all ?

ordered sets Easy
A.
B.
C.
D.

5 In a Hasse diagram, which types of edges are intentionally omitted to simplify the drawing?

Hasse diagrams of partial ordered sets Easy
A. Reflexive loops and transitive edges
B. Edges between comparable elements
C. Edges connecting to the minimal elements
D. Symmetric and asymmetric edges

6 How is the relation visually represented in a standard Hasse diagram?

Hasse diagrams of partial ordered sets Easy
A. The node for is placed higher than the node for , with a sequence of upward edges connecting them.
B. A directed arrow points from to .
C. The node for is placed higher than the node for , with a sequence of downward edges connecting them.
D. The nodes and are placed on the same horizontal level.

7 What is another common name in computer science for finding a consistent enumeration of a finite poset?

consistent enumeration Easy
A. Hashing
B. Binary search
C. Topological sorting
D. Breadth-first search

8 If a function is a consistent enumeration for a poset , what must be true if in ?

consistent enumeration Easy
A.
B.
C.
D.

9 What is the supremum of a subset in a partially ordered set?

supremum and infimum Easy
A. The maximum element in the entire poset
B. The greatest lower bound of
C. The least upper bound of
D. Any upper bound of

10 What is the infimum of a subset in a partially ordered set?

supremum and infimum Easy
A. The greatest lower bound of
B. Any lower bound of
C. The minimal element of the entire poset
D. The least upper bound of

11 If a subset of a poset has a supremum, how many suprema can it possibly have?

supremum and infimum Easy
A. At least two
B. Infinitely many
C. Exactly one
D. Depends on the size of the set

12 Two posets and are isomorphic if there exists a bijection that satisfies which of the following?

isomorphic (similar) ordered sets Easy
A. if and only if
B. if and only if
C. if and only if
D. if and only if

13 A set is called well-ordered if every non-empty subset contains which of the following?

well-ordered sets Easy
A. An upper bound
B. Both a least and a greatest element
C. A least element
D. A greatest element

14 Which of the following standard mathematical sets is a well-ordered set under the usual "less than or equal to" relation?

well-ordered sets Easy
A. The set of natural numbers
B. The set of rational numbers
C. The set of all integers
D. The set of real numbers

15 By definition, a lattice is a partially ordered set in which every pair of elements has which of the following?

lattices and bounded lattices Easy
A. Only an infimum
B. Only a supremum
C. A complement
D. Both a supremum and an infimum

16 In a bounded lattice, what do the special symbols and generally represent?

lattices and bounded lattices Easy
A. The first and second elements in a chain
B. The least upper bound and greatest lower bound of a specific subset
C. The global maximum and global minimum elements, respectively
D. The global minimum and global maximum elements, respectively

17 A lattice is considered distributive if which two operations distribute over each other?

distributive lattices Easy
A. Union () and Complement ()
B. Meet () and Join ()
C. Addition () and Multiplication ()
D. Supremum and Minimum

18 Which of the following is a classic example of a distributive lattice?

distributive lattices Easy
A. The power set of a set under subset inclusion
B. The lattice of all subgroups of a group
C. A pentagon lattice ()
D. A diamond lattice ()

19 In a bounded lattice with minimum and maximum , an element is a complement of if which of the following holds?

complements and complemented lattices Easy
A. and
B. and
C. and
D. and

20 What is a complemented lattice?

complements and complemented lattices Easy
A. A lattice that contains no bounds or
B. A lattice where only the bounds and have complements
C. A bounded lattice where every element has at least one complement
D. A lattice where every element has exactly two complements

21 Let be ordered by divisibility. Which of the following pairs of elements is incomparable?

ordered sets Medium
A. 4 and 6
B. 2 and 8
C. 2 and 6
D. 3 and 12

22 In the Hasse diagram of the poset ordered by divisibility, which element is an immediate predecessor of 12?

Hasse diagrams of partial ordered sets Medium
A. 8
B. 2
C. 4
D. 3

23 A consistent enumeration (topological sort) of a poset is a linear ordering such that:

consistent enumeration Medium
A. If in the poset, then in the linear order.
B. If in the poset, then in the linear order.
C. All incomparable elements in the poset become equal in the linear order.
D. The maximal element in the poset is always first in the linear order.

24 Let be the poset of the power set of ordered by set inclusion . What is the supremum of and ?

supremum and infimum Medium
A.
B. {c}
C. {a, b}
D. {a, b, c}

25 Consider the poset ordered by divisibility. What is the infimum of the subset in ?

supremum and infimum Medium
A.
B. It does not exist
C. 6
D. 1

26 Two posets and are isomorphic if there exists a bijection such that for all :

isomorphic (similar) ordered sets Medium
A. implies
B. if and only if
C. they have the exact same number of elements without structural constraints
D. implies (but the converse is not required)

27 Which of the following ordered sets is a well-ordered set under the standard less-than-or-equal-to relation ()?

well-ordered sets Medium
A. The set of all natural numbers
B. The open interval of real numbers
C. The set of all integers
D. The set of all positive rational numbers

28 Let be a lattice. Which of the following identifies the absorption laws in ?

lattices and bounded lattices Medium
A.
B. and
C. and
D. and

29 Which of the following lattices is NEVER a distributive lattice?

distributive lattices Medium
A. The pentagon lattice
B. The set of natural numbers under the standard relation
C. The power set of a set under inclusion
D. A totally ordered set (chain) with 4 elements

30 In a bounded lattice , an element is a complement of an element if:

complements and complemented lattices Medium
A. and
B. and
C. and
D. and

31 Let be the set of all positive divisors of 30, ordered by divisibility. What are the bounds (least element) and (greatest element) of this lattice?

lattices and bounded lattices Medium
A. ,
B. ,
C. ,
D. ,

32 When drawing a Hasse diagram for a poset, which of the following relations are NOT represented by an edge?

Hasse diagrams of partial ordered sets Medium
A. Transitivity relations where a middle element exists ( and )
B. Both reflexivity and transitivity relations
C. Immediate predecessors
D. Reflexivity relations ()

33 A relation on a set is a partial order if it is:

ordered sets Medium
A. Reflexive, symmetric, and transitive
B. Reflexive, antisymmetric, and transitive
C. Reflexive, antisymmetric, and symmetric
D. Irreflexive, antisymmetric, and transitive

34 Let . Which of the following relations on is NOT a partial order?

introduction Medium
A.
B.
C.
D.

35 Suppose a project has tasks . The prerequisites form a poset where , , and . Which of the following is a valid consistent enumeration of these tasks?

consistent enumeration Medium
A.
B.
C.
D.

36 Let be a distributive lattice. If and , what can be definitively concluded about and ?

distributive lattices Medium
A.
B. No conclusion can be drawn.
C. is the complement of
D.

37 Consider the lattice under divisibility. What is the complement of 2?

complements and complemented lattices Medium
A. 15
B. 30
C. 5
D. 3

38 Let be a total order and be a poset. Are and isomorphic?

isomorphic (similar) ordered sets Medium
A. Yes, because there is a bijection between them.
B. Yes, because both are bounded lattices.
C. No, because is not a total order.
D. No, because they have a different number of elements.

39 If is a well-ordered set, which of the following MUST be true?

well-ordered sets Medium
A. is a totally ordered set (chain).
B. Both A and C are true.
C. has no infinite descending chains.
D. contains a maximum element.

40 In a lattice, the operations (supremum) and (infimum) satisfy the idempotent laws. What is the idempotent law for ?

supremum and infimum Medium
A.
B.
C.
D.

41 How many non-isomorphic partial orders (up to isomorphism) can be defined on a set of exactly 3 elements?

ordered sets Hard
A. 6
B. 3
C. 5
D. 4

42 Consider the Boolean lattice , represented by the subsets of an -element set ordered by inclusion. What is the minimum for which the Hasse diagram of is non-planar?

Hasse diagrams of partial ordered sets Hard
A. 4
B. 5
C. 3
D. 6

43 Let be a poset with elements and cover relations , , and . What is the total number of valid consistent enumerations (linear extensions) of ?

consistent enumeration Hard
A. 4
B. 8
C. 5
D. 6

44 Let be the set of all continuous real-valued functions on . For , define a partial order where if for all . Which of the following statements is true regarding ?

supremum and infimum Hard
A. It forms a lattice, but it is not distributive.
B. It forms a distributive lattice.
C. It does not form a lattice because the supremum of two continuous functions is not guaranteed to be continuous.
D. It does not form a lattice because it is not well-ordered.

45 Which of the following conditions is both necessary and sufficient for two finite partially ordered sets and to be isomorphic?

isomorphic (similar) ordered sets Hard
A. They have the exact same number of minimal and maximal elements and the same height.
B. There exists a bijective function such that if , then .
C. Their Hasse diagrams contain the same number of vertices and edges.
D. There exists a bijective function such that .

46 Let and be two well-ordered sets. Under which of the following Cartesian product operations is the resulting set NOT necessarily well-ordered?

well-ordered sets Hard
A. The resulting sets are well-ordered in all the above cases.
B. The Lexicographical order on
C. The Lexicographical order on
D. The Product order on

47 Consider the lattice , consisting of a minimum element , a maximum element , and mutually incomparable elements strictly between and . For which values of is a modular lattice but NOT a distributive lattice?

lattices and bounded lattices Hard
A.
B.
C.
D.

48 Birkhoff's Representation Theorem states that any finite distributive lattice is isomorphic to the lattice of lower sets (ideals) of a uniquely determined underlying poset . What are the elements of this underlying poset in relation to ?

distributive lattices Hard
A. The set of all atoms of
B. The maximal chains of
C. The join-irreducible elements of
D. The meet-irreducible elements of

49 Let be a bounded, distributive lattice. If an element has a complement , which of the following statements must rigorously hold true?

complements and complemented lattices Hard
A. Every other element in must also have at least one complement.
B. is the unique complement of .
C. may not be unique, but any other complement must satisfy .
D. is only guaranteed to be unique if is a Boolean algebra.

50 Let be a strict partial order relation on a set consisting of elements. What is the absolute maximum number of ordered pairs that can be contained in ?

introduction Hard
A.
B.
C.
D.

51 Consider the partially ordered set formed by all partitions of an -element set, ordered by refinement (a partition is 'less than' another if it is finer). What is the total number of elements in the longest possible chain in this poset?

ordered sets Hard
A.
B.
C.
D.

52 When drawing the Hasse diagram for the poset of positive divisors of (where are distinct primes) under divisibility, how many vertices and edges will the diagram contain?

Hasse diagrams of partial ordered sets Hard
A. 12 vertices and 24 edges
B. 24 vertices and 36 edges
C. 24 vertices and 52 edges
D. 24 vertices and 46 edges

53 Consider a poset whose Hasse diagram forms a directed tree rooted at a single minimum element (an arborescence). The tree has root with children and . has one child . has two children and . What is the total number of consistent enumerations of this poset?

consistent enumeration Hard
A. 60
B. 120
C. 36
D. 20

54 Let be a lattice. An element is called join-irreducible if implies or . In the lattice of positive divisors of under divisibility, how many completely join-irreducible elements are there?

supremum and infimum Hard
A. 4
B. 12
C. 5
D. 3

55 Let be a poset, and its dual be the poset with the inverted relation (). A poset is self-dual if . Which of the following finite posets is NOT self-dual?

isomorphic (similar) ordered sets Hard
A. The lattice of divisors of 36 under divisibility.
B. The Boolean lattice .
C. The poset formed by the positive divisors of 30 strictly greater than 1 under divisibility.
D. The pentagon lattice .

56 In the standard foundations of mathematics (Zermelo-Fraenkel set theory), the Well-Ordering Theorem states that every set can be well-ordered. This theorem is rigorously logically equivalent to which of the following statements?

well-ordered sets Hard
A. Every partially ordered set has a maximal element.
B. The Axiom of Choice.
C. Every totally ordered set is order-isomorphic to a subset of the real numbers.
D. The Continuum Hypothesis.

57 Consider a bounded finite modular lattice . Which fundamental theorem or condition ensures that all maximal chains between the minimum element and the maximum element contain the exact same number of elements?

lattices and bounded lattices Hard
A. Dilworth's Theorem.
B. The Dedekind-MacNeille Completion Theorem.
C. The Jordan-Dedekind chain condition.
D. Birkhoff's Representation Theorem.

58 Let be a lattice. The Theorem provides a structural characterization of distributive lattices. According to this theorem, is distributive if and only if:

distributive lattices Hard
A. can be mapped to a linear order.
B. Every element in has at most one complement.
C. contains no sublattice isomorphic to the Boolean lattice .
D. contains no sublattice isomorphic to the pentagon lattice or the diamond lattice .

59 A Boolean algebra is fundamentally defined as a lattice that is bounded, distributive, and complemented. How many non-isomorphic Boolean algebras exist that contain exactly 12 elements?

complements and complemented lattices Hard
A. 2
B. 0
C. 1
D. 4

60 Let be a finite set. A relation on is defined as a quasi-order (or preorder) if it is reflexive and transitive. How can the quasi-order be naturally transformed into a proper partial order?

introduction Hard
A. By taking the quotient set of under the equivalence relation where .
B. By removing all symmetric pairs strictly from .
C. By computing the antisymmetric closure of .
D. It is mathematically impossible unless is inherently antisymmetric from the beginning.
Previous MCQ
Unit 1
Next MCQ
Unit 3