37 KiB
| title | TARGET DECK | FILE TAGS | tags | |
|---|---|---|---|---|
| Set | Obsidian::STEM | set |
|
Overview
Set theory begins with two primitive notions of sets and membership. Other axioms are defined relative to these concepts.
%%ANKI Basic What are the two primitive notions of set theory? Back: Sets and membership. Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI Basic How does Enderton describe a primitive notion? Back: An undefined concept other concepts are defined with. Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI Basic Axioms can be thought of as doing what to primitive notions? Back: Divulging partial information about their meaning. Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI Basic How does Knuth define a dynamic set? Back: As a set that can change over time. Reference: Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022). Tags: adt::dynamic_set
END%%
%%ANKI Basic How does Knuth distinguish mathematical sets from dynamic sets? Back: The former is assumed to be unchanging. Reference: Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022). Tags: adt::dynamic_set
END%%
%%ANKI Basic How does Knuth define a dictionary? Back: As a dynamic set that allows insertions, deletions, and membership tests. Reference: Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022). Tags: adt::dynamic_set
END%%
%%ANKI Basic Which of dynamic sets and dictionaries are more general? Back: The dynamic set. Reference: Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022). Tags: adt::dynamic_set
END%%
%%ANKI Basic Is a dynamic set a dictionary? Back: Not necessarily. Reference: Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022). Tags: adt::dynamic_set
END%%
%%ANKI Basic Is a dictionary a dynamic set? Back: Yes. Reference: Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022). Tags: adt::dynamic_set
END%%
%%ANKI Cloze A dictionary supports {insertions}, {deletions}, and {membership testing}. Reference: Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022). Tags: adt::dynamic_set
END%%
Sets are often denoted using roster notation in which members are specified explicitly in a comma-delimited list surrounded by curly braces. Alternatively, abstraction (or set-builder notation) defines sets using an entrance requirement. Examples of the set of prime numbers less than 10:
- Roster notation:
\{2, 3, 5, 7\} - Set-builder notation:
\{x \mid x < 10 \land x \text{ is prime}\}
%%ANKI
Basic
Define the set of prime numbers less than 10 using abstraction.
Back: \{x \mid x < 10 \land x \text{ is prime}\}
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
Define the set of prime numbers less than 5 using set-builder notation.
Back: \{x \mid x < 5 \land x \text{ is prime}\}
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
Define the set of prime numbers less than 5 using roster notation.
Back: \{2, 3\}
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
Define the set of prime numbers less than 5 using abstraction.
Back: \{x \mid x < 5 \land x \text{ is prime}\}
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
What term describes the expression to the right of \mid in set-builder notation?
Back: The entrance requirement.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
What term refers to \_\_\; x\; \_\_ in \{x \mid \_\_\; x\; \_\_\}?
Back: The entrance requirement.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI Basic The term "entrance requirement" refers to what kind of set notation? Back: Set-builder/abstraction. Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI Basic What name is given to set notation in which members are explicitly listed? Back: Roster notation. Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI Basic What does an atom refer to in set theory? Back: Any entity that is not a set but can exist in one. Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI Basic What German term is used alternatively for "atoms"? Back: Urelements. Reference: Simon Hewitt, “A Cardinal Worry for Permissive Metaontology,” Metaphysica 16, no. 2 (September 18, 2015): 159–65, https://doi.org/10.1515/mp-2015-0009.
END%%
%%ANKI Basic Can sets be members of urelements? Back: No. Reference: Simon Hewitt, “A Cardinal Worry for Permissive Metaontology,” Metaphysica 16, no. 2 (September 18, 2015): 159–65, https://doi.org/10.1515/mp-2015-0009.
END%%
%%ANKI Basic Can urelements be members of sets? Back: Yes. Reference: Simon Hewitt, “A Cardinal Worry for Permissive Metaontology,” Metaphysica 16, no. 2 (September 18, 2015): 159–65, https://doi.org/10.1515/mp-2015-0009.
END%%
%%ANKI Basic Can urelements be members of urelements? Back: No. Reference: Simon Hewitt, “A Cardinal Worry for Permissive Metaontology,” Metaphysica 16, no. 2 (September 18, 2015): 159–65, https://doi.org/10.1515/mp-2015-0009.
END%%
%%ANKI Basic Can sets be members of sets? Back: Yes. Reference: Simon Hewitt, “A Cardinal Worry for Permissive Metaontology,” Metaphysica 16, no. 2 (September 18, 2015): 159–65, https://doi.org/10.1515/mp-2015-0009.
END%%
%%ANKI Cloze An {atom} is to set theory as an {atomic} logical statement is to propositional logic. Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI Cloze A {set} is to set theory as a {2:molecular} logical statement is to propositional logic. Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI Basic What distinguishes a set from an atom? Back: An atom cannot contain other entitites. Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI Basic What intuition is broken when a box is viewed as an atom? Back: When viewed as an atom, the box is no longer a container. Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI Basic Enderton's exposition makes what assumption about the set of all atoms? Back: It is the empty set. Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
How are members of the following set defined using extensionality and first-order logic? $B = \{P(x) \mid \phi(x)\}$
Back: \forall x, P(x) \in B \Leftrightarrow \phi(x)
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
How are members of the following set defined using extensionality and first-order logic? $B = \{x \mid x < 5 \land x \text{ is prime}\}$
Back: \forall x, x \in B \Leftrightarrow (x < 5 \land x \text{ is prime})
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Cloze
P(x) = T is equivalently written as x \in {\{v \mid P(v)\}}.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Cloze
\exists u \in A, uFx is equivalently written as x \in {F[\![A]\!]}.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
How is set \{P(y) \mid y \in B\} interpreted?
Back: As the set of P(y) for all y \in B.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
Given function P, how is set \{P(y) \mid y \in B\} more compactly denoted?
Back: P[\![B]\!]
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
How is set \{P(y) \mid \exists y \in B\} interpreted?
Back: If B is empty, the empty set. Otherwise as singleton \{P(y)\}.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
How many members are in set \{P(y) \mid \exists y \in B\}?
Back: At most 1.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
In set-builder notation, the left side of \{\ldots \mid \ldots\} denotes what?
Back: The members of the set.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
In set-builder notation, the right side of \{\ldots \mid \ldots\} denotes what?
Back: The entrance requirement.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
How is set \{v \mid \exists A \in B, v = A\} written more compactly?
Back: B
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
How is set \{v \mid \exists A \in B, v \in A\} written more compactly?
Back: \bigcup B
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
How is \{A \mid A \in B\} rewritten with an existential in the entrance requirement?
Back: \{v \mid \exists A \in B \land v = A\}
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
Extensionality
If two sets have exactly the same members, then they are equal: \forall A, \forall B, (\forall x, x \in A \Leftrightarrow x \in B) \Rightarrow A = B$$
%%ANKI
Basic
What does the extensionality axiom state?
Back: If two sets have exactly the same members, then they are equal.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
How is the extensionality axiom expressed using first-order logic?
Back: \forall A, \forall B, (\forall x, x \in A \Leftrightarrow x \in B) \Rightarrow A = B$$
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
The following encodes which set theory axiom? \forall A, \forall B, (\forall x, x \in A \Leftrightarrow x \in B) \Rightarrow A = B$$
Back: The extensionality axiom.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI Basic How many sets exist with no members? Back: Exactly one. Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
Which set theory axiom proves uniqueness of \varnothing?
Back: The extensionality axiom.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI Basic What axiom is used to prove two sets are equal to one another? Back: Extensionality. Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
Let A and B be sets. Proving the following is equivalent to showing what class is a set? \exists C, \forall y, (y \in C \Leftrightarrow y = {x} \times B \text{ for some } x \in A)
Back: \{\{x\} \times B \mid x \in A\}
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
Empty Set Axiom
There exists a set having no members: \exists B, \forall x, x \not\in B$$
%%ANKI Basic What does the empty set axiom state? Back: There exists a set having no members. Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
How is the empty set axiom expressed using first-order logic?
Back: \exists B, \forall x, x \not\in B$$
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
The following encodes which set theory axiom? \exists B, \forall x, x \not\in B$$
Back: The empty set axiom.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
Which set theory axiom proves existence of \varnothing?
Back: The empty set axiom.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
What two properties ensures definition \varnothing is well-defined?
Back: Existence and uniqueness.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
How is the empty set defined using set-builder notation?
Back: \{x \mid x \neq x\}
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
Pairing Axiom
For any sets u and v, there exists a set having as members just u and v: \forall u, \forall v, \exists B, \forall x, (x \in B \Leftrightarrow x = u \lor x = v)
%%ANKI
Basic
What does the pairing axiom state?
Back: For any sets u and v, there exists a set having as members just u and v.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
How is the pairing axiom expressed using first-order logic?
Back: \forall u, \forall v, \exists B, \forall x, (x \in B \Leftrightarrow x = u \lor x = v)
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
The following encodes which set theory axiom? \forall u, \forall v, \exists B, \forall x, (x \in B \Leftrightarrow x = u \lor x = v)
Back: The pairing axiom.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
Which set theory axiom proves existence of set \{x, y\} where x \neq y?
Back: The pairing axiom.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
Which set theory axiom proves existence of set \{x\}?
Back: The pairing axiom.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
For sets u and v, what name is given to set \{u, v\}?
Back: The pair set of u and v.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI Basic In set theory, what does a singleton refer to? Back: A set with exactly one member. Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI Basic What set theory axiom is used to prove existence of singletons? Back: The pairing axiom. Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
How is the pair set \{u, v\} defined using set-builder notation?
Back: \{x \mid x = u \lor x = v\}
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
Union Axiom
Preliminary Form
For any sets a and b, there exists a set whose members are those sets belonging either to a or to b (or both): \forall a, \forall b, \exists B, \forall x, (x \in B \Leftrightarrow x \in a \lor x \in b)
%%ANKI
Basic
What does the union axiom (preliminary form) state?
Back: For any sets a and b, there exists a set whose members are all in either a or b (or both).
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
How is the union axiom (preliminary form) expressed using first-order logic?
Back: \forall a, \forall b, \exists B, \forall x, (x \in B \Leftrightarrow x \in a \lor x \in b)
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
The following encodes which set theory axiom? \forall a, \forall b, \exists B, \forall x, (x \in B \Leftrightarrow x \in a \lor x \in b)
Back: The union axiom (preliminary form).
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
How is the union of sets a and b denoted?
Back: a \cup b
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
What two set theory axioms prove existence of e.g. \{x_1, x_2, x_3\}?
Back: The pairing axiom and union axiom.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
How is the union of set a and b defined using set-builder notation?
Back: \{x \mid x \in a \lor x \in b\}
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
What set operation is shaded green in the following venn diagram?
!
Back: A \cup B
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
What does \bigcup\,\{x\} evaluate to?
Back: x
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
General Form
For any set A, there exists a set B whose elements are exactly the members of the members of A: \forall A, \exists B, \forall x, x \in B \Leftrightarrow (\exists b \in B, x \in b)
%%ANKI
Basic
What does the union axiom (general form) state?
Back: For any set A, there exists a set B whose elements are exactly the members of the members of A.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
How is the union axiom (general form) expressed using first-order logic?
Back: \forall A, \exists B, \forall x, x \in B \Leftrightarrow (\exists a \in A, x \in a)
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI Basic What advantage does the general form of the union axiom have over its preliminary form? Back: The general form can handle infinite sets. Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
How is the preliminary form of the union axiom proven using the general form?
Back: For any sets a and b, \bigcup \{a, b\} = a \cup b.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
What is the result of \bigcup \{\{2, 4, 6\}, \{6, 16, 26\}, \{0\}\}?
Back: \{2, 4, 6, 16, 26, 0\}
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
What is the result of \bigcup \varnothing?
Back: \varnothing
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
How is \bigcup A represented in first-order logic?
Back: \{x \mid \exists a \in A, x \in a\}
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
Roughly speaking, how does \bigcup A adjust as A gets larger?
Back: \bigcup A gets larger.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
If A \subseteq B, how do \bigcup A and \bigcup B relate?
Back: \bigcup A \subseteq \bigcup B
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
What kind of mathematical object is the absolute complement of set A?
Back: A class.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
What kind of mathematical object is the relative complement of set B in A?
Back: A set.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI Cloze {1:Classes} are to {2:absolute} complements whereas {2:sets} are to {1:relative} complements. Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
What contradiction arises when arguing the absolute complement of set A is a set?
Back: The union of the complement with A is the class of all sets.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI Basic Why is the absolute complement of sets rarely useful in set theory? Back: The absolute complement of a set isn't a set. Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
What set operation is shaded green in the following venn diagram?
!
Back: The absolute complement of A.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
Power Set Axiom
For any set a, there is a set whose members are exactly the subsets of a: \forall a, \exists B, \forall x, (x \in B \Leftrightarrow x \subseteq a)
%%ANKI
Basic
What does the power set axiom state?
Back: For any set a, there exists a set whose members are exactly the subsets of a.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
How is the power set axiom expressed using first-order logic?
Back: \forall a, \exists B, \forall x, (x \in B \Leftrightarrow x \subseteq a)
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
The following encodes which set theory axiom? \forall a, \exists B, \forall x, (x \in B \Leftrightarrow x \subseteq a)
Back: The power set axiom.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
How is x \subseteq a rewritten using first-order logic and \in?
Back: \forall t, t \in x \Rightarrow t \in a
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
How is the power set of set a denoted?
Back: \mathscr{P}{a}
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
How is the power set of set a defined using set-builder notation?
Back: \{x \mid x \subseteq a\}
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
Subset Axioms
For each formula \_\_\_ not containing B, the following is an axiom: \forall t_1, \cdots, \forall t_k, \forall c, \exists B, \forall x, (x \in B \Leftrightarrow x \in c \land ___)
%%ANKI
Basic
What do the subset axioms state?
Back: For each formula \_\_\_ not containing B, the following is an axiom: \forall t_1, \cdots, \forall t_k, \forall c, \exists B, \forall x, (x \in B \Leftrightarrow x \in c \land ___)
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
Let \_\_\_ be a wff excluding B. How is its subset axiom stated in first-order logic?
Back: \forall t_1, \cdots, \forall t_k, \forall c, \exists B, \forall x, (x \in B \Leftrightarrow x \in c \land ___)
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
The following encodes which set theory axiom(s)? \forall t_1, \cdots, \forall t_k, \forall c, \exists B, \forall x, (x \in B \Leftrightarrow x \in c \land ___)
Back: The subset axioms.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI Basic Which axioms prove the existence of the union of two sets? Back: The union axiom. Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI Basic Which axioms prove the existence of the intersection of two sets? Back: The subset axioms. Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
How is the intersection of sets A and B denoted?
Back: A \cap B
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
How is the intersection of sets a and b defined using set-builder notation?
Back: \{x \mid x \in a \land x \in b\}
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI Basic Which axioms prove the existence of the relative complement of two sets? Back: The subset axioms. Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
Given sets A and B, what does A - B denote?
Back: The relative complement of B in A.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
How is the relative complement of set B in A denoted?
Back: A - B
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
How is the relative complement of set b in a defined using set-builder notation?
Back: \{x \mid x \in a \land x \not\in b\}
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI Cloze Union is to the {union axiom} whereas intersection is to the {subset axioms}. Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI Basic The subset axioms ensure we do not construct what kind of mathematical object? Back: Classes. Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
How is \bigcap A represented in first-order logic?
Back: \{x \mid \forall b \in A, x \in b\}
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Cloze
{1:\forall} is to {2:\bigcap} whereas {2:\exists} is to {1:\bigcup}.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
What is the result of \bigcap \{\{2, 4, 6\}, \{6, 16, 26\}, \{6\}\}?
Back: \{6\}
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
How does \bigcap A adjust as A gets larger?
Back: \bigcap A gets smaller.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
If A \subseteq B, how do \bigcap A and \bigcap B relate?
Back: \bigcap B \subseteq \bigcap A
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
What class does \bigcap \varnothing correspond to?
Back: The class of all sets.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
Why does \bigcap \varnothing present a problem?
Back: Every set is a member of every member of \varnothing (vacuously).
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Cloze
{\bigcap \varnothing} is to set theory as {division by zero} is to arithmetic.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
What set operation is shaded green in the following venn diagram?
!
Back: A \cap B
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
What set operation is shaded green in the following venn diagram?
!
Back: A - B
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
What set operation is shaded green in the following venn diagram?
!
Back: A \mathop{\triangle} B
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI Basic The "subset axioms" are more accurately classified as what? Back: An axiom schema. Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI Basic What is an axiom schema? Back: An infinite bundle of axioms. Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI Basic Which of the set theory axioms are more accurately described as an axiom schema? Back: The subset axioms. Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
What does \bigcap\,\{x\} evaluate to?
Back: x
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
Axiom of Choice
This axiom assumes the existence of some choice function capable of selecting some element from a nonempty set. Note this axiom is controversial because it is non-constructive: there is no procedure we can follow to decide which element was chosen.
%%ANKI Basic Why is the Axiom of Choice named the way it is? Back: It assumes the existence of some choice function. Reference: “Axiom of Choice,” in Wikipedia, July 8, 2024, https://en.wikipedia.org/w/index.php?title=Axiom_of_choice&oldid=1233242262.
END%%
%%ANKI Basic In Russell's analogy, why is AoC unnecessary to pick left shoes from an infinite set of shoe pairs? Back: The choice function can be defined directly, i.e. as "pick left shoe". Reference: “Axiom of Choice,” in Wikipedia, July 8, 2024, https://en.wikipedia.org/w/index.php?title=Axiom_of_choice&oldid=1233242262.
END%%
%%ANKI Basic In Russell's analogy, why is AoC necessary to pick socks from an infinite set of sock pairs? Back: There is no choice function to choose/prefer one sock from/over the other. Reference: “Axiom of Choice,” in Wikipedia, July 8, 2024, https://en.wikipedia.org/w/index.php?title=Axiom_of_choice&oldid=1233242262.
END%%
%%ANKI Basic What objects does Russell's analogy use when explaining AoC? Back: Pairs of shoes vs. pairs of (indistinguishable) socks. Reference: “Axiom of Choice,” in Wikipedia, July 8, 2024, https://en.wikipedia.org/w/index.php?title=Axiom_of_choice&oldid=1233242262.
END%%
Relation Form
For any relation R there exists a function F \subseteq R with \mathop{\text{dom}}F = \mathop{\text{dom}}R.
%%ANKI Basic What is AoC an acronym for? Back: The Axiom of Choice. Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
What does the Axiom of Choice (relation form) state?
Back: For any relation R there exists a function F \subseteq R with \mathop{\text{dom}}F = \mathop{\text{dom}}R.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI Basic AoC (relation form) posits the existence of what mathematical object? Back: A function. Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
Given relation R, AoC implies existence of function F. How does F relate to R?
Back: F \subseteq R and \mathop{\text{dom}} F = \mathop{\text{dom}} R.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
Infinite Cartesian Product Form
For any set I and function H with domain I, if H(i) \neq \varnothing for all i \in I, then \bigtimes_{i \in I} H(i) \neq \varnothing.
%%ANKI
Basic
What does the Axiom of Choice (infinite Cartesian product form) state?
Back: For any set I and function H with domain I, if H(i) \neq \varnothing for all i \in I, then \bigtimes_{i \in I} H(i) \neq \varnothing.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
What is the antecedent used in AoC (infinite Cartesian product form)?
Back: H(i) \neq \varnothing for all i \in I.
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
What is the consequent used in AoC (infinite Cartesian product form)?
Back: \bigtimes_{i \in I} H(i) \neq \varnothing
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
Infinity Axiom
There exists an natural-numbers#Inductive Sets set: \exists A, [\varnothing \in A \land (\forall a \in A, a^+ \in A)]
%%ANKI Basic What does the infinity axiom state? Back: There exists an inductive set. Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI Cloze The {infinity} axiom asserts the existence of an {inductive set}. Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
%%ANKI
Basic
State the infinity axiom in FOL.
Back: \exists A, [\varnothing \in A \land (\forall a \in A, a^+ \in A)]
Reference: Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
END%%
Bibliography
- “Axiom of Choice,” in Wikipedia, July 8, 2024, https://en.wikipedia.org/w/index.php?title=Axiom_of_choice&oldid=1233242262.
- Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
- “Russell’s Paradox,” in Wikipedia, April 18, 2024, https://en.wikipedia.org/w/index.php?title=Russell%27s_paradox&oldid=1219576437.
- Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).