Set Theory and Mathematical Logic Practice Quiz (28 questions)

1. Which feature makes a sentence a proposition in logic?

A. It has a truth value, either true or false.

B. It contains a connective joining two simpler sentences.

C. It expresses a command whose fulfillment can be observed.

D. It asks a question with a definite answer.

Answer: (A)

Explanation

A proposition is a sentence that can be assigned one of the truth values true or false. A command or question is not a proposition merely because it has a possible fulfillment or answer.

2. If proposition A is false, what is the truth value of its negation ¬A?

A. Undetermined, because A has no truth value.

B. True only when A and another proposition are both false.

C. True, because negation reverses A’s truth value.

D. False, because a negation preserves A’s truth value.

Answer: (C)

Explanation

The negation ¬A is true whenever A is false, and false whenever A is true. The claim that negation preserves A’s truth value confuses negation with leaving the proposition unchanged.

3. A student knows that A is true and B is false; what is the truth value of A ∧ B?

A. False, because a conjunction is false whenever either proposition is true.

B. True, because the truth of A determines the conjunction.

C. False, because a conjunction requires both propositions to be true.

D. True, because a conjunction requires at least one proposition to be true.

Answer: (C)

Explanation

A conjunction is true exactly when both of its component propositions are true, so A ∧ B is false in this case. The condition that at least one proposition be true applies to disjunction, not conjunction.

4. If A is false and B is true, what is the truth value of A ∨ B?

A. True, because a disjunction is true when at least one proposition is true.

B. True, because a disjunction is true only when both propositions are false.

C. False, because the first proposition is false.

D. False, because a disjunction requires both propositions to be true.

Answer: (A)

Explanation

A disjunction is true when at least one of its propositions is true, so A ∨ B is true here. Requiring both propositions to be true is the condition for a conjunction.

5. For the implication A ⇒ B, what must hold whenever the implication is true?

A. At least one of A and B is true, regardless of which one.

B. A and B have the same truth value in every case.

C. Whenever A is true, B is true; A is the hypothesis and B is the conclusion.

D. Whenever B is true, A is true; B is the hypothesis and A is the conclusion.

Answer: (C)

Explanation

A ⇒ B states that whenever its hypothesis A is true, its conclusion B is true. The reverse condition, that B’s truth guarantees A’s truth, is the converse and is not part of the implication’s definition.

6. A theorem establishes A ⇒ B but gives no further information; which conclusion about B ⇒ A is justified?

A. The converse B ⇒ A is equivalent to the contrapositive of A ⇒ B.

B. The converse B ⇒ A has not been established by A ⇒ B alone.

C. The converse B ⇒ A holds whenever A and B are both propositions.

D. The converse B ⇒ A follows automatically from A ⇒ B.

Answer: (B)

Explanation

An implication does not by itself establish its converse, so proving A ⇒ B alone gives no guarantee that B ⇒ A holds. The converse is a separate implication with its direction reversed.

7. What must be shown to establish that A and B are logically equivalent?

A. Both A ⇒ B and B ⇒ A must hold.

B. The contrapositive of A ⇒ B must hold, without a reverse implication.

C. A ⇒ B must hold, while B ⇒ A may fail.

D. A and B must be true at the same time in one case.

Answer: (A)

Explanation

Logical equivalence A ⇔ B requires implications in both directions: A ⇒ B and B ⇒ A. Establishing just one direction proves an implication, not equivalence.

8. To prove A ⇒ B directly, what is the appropriate starting strategy?

A. Prove B ⇒ A and treat it as the original implication.

B. Assume A is false and derive a contradiction.

C. Assume A is true and deduce that B is true.

D. Assume B is false and deduce that A is false.

Answer: (C)

Explanation

A direct proof of A ⇒ B starts by assuming the hypothesis A and then deduces the conclusion B. Assuming ¬B and deriving ¬A is a proof by contraposition, a different method.

9. To prove P(n) for every integer n ≥ k by induction, which pair of steps is required?

A. Prove P(t) implies P(t+1) for every t ≥ k, without establishing a starting case.

B. Prove P(k), then prove P(t) directly for one selected t greater than k.

C. Prove P(k+1), then prove P(t+1) implies P(t) for every t ≥ k.

D. Prove P(k), then prove P(t) implies P(t+1) for every t ≥ k.

Answer: (D)

Explanation

Induction from k requires a base case P(k) and an inductive step showing that P(t) implies P(t+1) for every t ≥ k. The inductive step alone does not establish the initial case needed to begin the chain.

10. Which description captures what makes a collection a set?

A. Membership can be determined, and the collection is not an element of itself.

B. Its members must themselves be sets, and the collection must contain itself.

C. Every object must satisfy a shared property, and the collection must be finite.

D. Its elements must be listed, and the collection must contain at least one object.

Answer: (A)

Explanation

A set is a collection whose membership is determinable and which is not an element of itself. A set need not have its elements listed or be nonempty.

11. Which statement correctly distinguishes the empty set from the set containing it?

A. Both sets have one element, because each is represented by a set symbol.

B. Both sets have no elements, because the empty set contributes no membership.

C. The empty set has one element, while the set containing it has no elements.

D. The empty set has no elements, while the set containing it has the empty set as one element.

Answer: (D)

Explanation

The empty set has no elements, whereas {∅} has one element: ∅. Treating both sets as empty confuses a set with the set whose member is that set.

12. A property is satisfied by at least one element of a domain but not by every element; which quantifier correctly expresses this?

A. The universal quantifier ∀, because one successful example represents the domain.

B. The existential quantifier ∃, because the property holds for at least one element.

C. The existential quantifier ∃, because the property holds for every element.

D. The universal quantifier ∀, because the property is tested across the domain.

Answer: (B)

Explanation

The existential quantifier ∃ asserts that at least one element satisfies the property. The universal quantifier ∀ instead asserts that every element does.

13. If every element of F is also an element of E, what relationship holds between the sets?

A. E is a subset of F, written E ⊆ F.

B. F is a subset of E, written F ⊆ E.

C. F is a proper subset of E, because the sets are distinct.

D. F and E are equal, because one inclusion has been established.

Answer: (B)

Explanation

F ⊆ E means precisely that every element of F belongs to E. This inclusion alone does not establish equality, which requires inclusion in both directions.

14. Which statement holds for every set E, including when E has no elements?

A. The empty set is a subset of E, and E is a subset of itself.

B. The empty set is an element of E, and E is an element of itself.

C. The empty set is a subset of E, but E is not a subset of itself.

D. E is a proper subset of itself, and the empty set is a proper subset of E.

Answer: (A)

Explanation

Every set contains ∅ as a subset and is a subset of itself. These facts concern subset relationships, not whether ∅ is an element of E.

15. What must be true to conclude that two sets E and F are equal?

A. Every element of E belongs to F, and every element of F belongs to E.

B. E and F have the same number of elements, regardless of their members.

C. E and F share at least one element, and neither set is empty.

D. Every element of E belongs to F, whether or not F has extra elements.

Answer: (A)

Explanation

Set equality requires inclusion in both directions: each set's elements must belong to the other. A single inclusion can hold even when the other set has additional elements.

16. What kinds of objects are the members of the power set P(E)?

A. All sets that contain E, including E and its supersets.

B. All elements of E, including any elements that are themselves sets.

C. All proper subsets of E, excluding ∅ and E itself.

D. All subsets of E, including ∅ and E itself.

Answer: (D)

Explanation

P(E) consists of every subset of E, including the empty set and E itself. Its members are subsets of E, not simply the elements that belong to E.

17. An object belongs to E but not to F; which set must contain that object?

A. The union E ∪ F, because membership in both sets is required.

B. The intersection E ∩ F, because membership in neither set is required.

C. The union E ∪ F, because membership in either set is sufficient.

D. The intersection E ∩ F, because membership in one set is sufficient.

Answer: (C)

Explanation

The union contains elements that belong to E or F, so membership in E alone is enough. The intersection requires membership in both sets.

18. A student is in both group E and group F; in which set is the student included?

A. The union E ∪ F, because membership in neither group is required.

B. The intersection E ∩ F, because membership in either group is sufficient.

C. The union E ∪ F, because membership in both groups is required.

D. The intersection E ∩ F, because membership in both groups is required.

Answer: (D)

Explanation

The intersection contains elements that belong to both E and F. The union requires membership in at least one of the sets, rather than both.

19. If an element belongs to E but not to F, in which set does it belong?

A. F − E

B. E ∪ F

C. E ∩ F

D. E − F

Answer: (D)

Explanation

E − F contains elements that are in E and not in F. F − E reverses those roles, requiring membership in F instead.

20. Given F ⊆ E, which elements make up the complement of F in E?

A. Elements outside E that do not belong to F

B. Elements of F that do not belong to E

C. Elements belonging to either E or F

D. Elements of E that do not belong to F

Answer: (D)

Explanation

The complement of F in E consists of elements in E that are not in F. Elements outside E are not included, even if they are also outside F.

21. For subsets A and B of E, what is the complement in E of A ∪ B?

A. The union of A and the complement of B

B. The intersection of A and the complement of B

C. The intersection of the complements of A and B

D. The union of the complements of A and B

Answer: (C)

Explanation

An element is outside A ∪ B precisely when it is outside both A and B, so it belongs to both complements. The union of the complements instead describes the complement of A ∩ B.

22. When are two ordered n-tuples equal?

A. When they contain the same components in any order

B. When their components match in every corresponding position

C. When they have the same number of distinct components

D. When their first and last components match

Answer: (B)

Explanation

Ordered tuples are equal exactly when each component matches the component in the same position. Having the same components in a different order is not sufficient.

23. If one factor in E₁ × ⋯ × Eₙ is empty, what is the Cartesian product?

A. The set containing the empty tuple

B. The union of the remaining factors

C. The empty set

D. The product of the nonempty factors

Answer: (C)

Explanation

The Cartesian product contains tuples with a component from every factor, so an empty factor makes such tuples impossible. The product of the remaining factors does not meet that requirement.

24. For sets A and B, under what condition does (x, y) belong to A × B?

A. When x belongs to A and y belongs to B

B. When x belongs to A or y belongs to B

C. When x belongs to B and y belongs to A

D. When x and y both belong to A

Answer: (A)

Explanation

Membership in A × B requires the first coordinate to belong to A and the second to belong to B. Having just one coordinate satisfy its condition is insufficient.

25. What does a family of sets indexed by a nonempty set I specify?

A. A set Aᵢ associated with each index i in I

B. An index i associated with each element of one set A

C. A set Aᵢ associated with each pair of indices in I

D. A single set formed by combining all indices in I

Answer: (A)

Explanation

An indexed family assigns a set Aᵢ to each element i of the nonempty index set I. Associating sets with pairs of indices describes a different indexing scheme.

26. When does an element x belong to the union of an indexed family (Aᵢ)ᵢ∈I?

A. When x belongs to at least one set Aᵢ

B. When x belongs to every set Aᵢ

C. When x belongs to the index set I

D. When x belongs to exactly one set Aᵢ

Answer: (A)

Explanation

Membership in the union requires x to belong to Aᵢ for at least one index i. Requiring membership in every indexed set is the condition for the intersection.

27. When does an element x belong to the intersection of an indexed family (Aᵢ)ᵢ∈I?

A. When x belongs to every set Aᵢ

B. When x belongs to the index set I

C. When x belongs to exactly one set Aᵢ

D. When x belongs to at least one set Aᵢ

Answer: (A)

Explanation

Membership in the intersection requires x to belong to Aᵢ for every index i. Belonging to at least one indexed set is the condition for the union.

28. For a nonempty family of nonempty pairwise disjoint sets, what does the axiom of choice guarantee?

A. A set E whose intersection with each family member is a singleton

B. A set E whose intersection with each family member is empty

C. A set E that equals the union of all family members

D. A set E that contains every member of the family

Answer: (A)

Explanation

The axiom of choice guarantees a set E that intersects each set in the family in exactly one element. A set with empty intersection would select no element from each member.