Set Theory Flashcards
What is a Set?
A set is a collection of distinguishable objects.
How are the objects contained in a set called?
They are called members or elements
How can you specify that an element is in a set?
x \in S
How can you specify that an element is not in a set?
x \notin S
Can the set contain an element more than one time?
No, it cannot
How is called the variation of the set that can contain an object multiple times?
Multiset
Are the elements (also called members) of a set ordered?
No, they are not
When two sets are equal?
When they contains the same elements.
What is an empty set?
A set that does not contain any element
What is a singleton set?
A set containing exclusively one element
What does it mean that the set A is a subset of B?
If all the elements of A are contained in a set B
What is a proper subset?
If all the elements of A are contained in a set B, but the two sets A and B are not equal
Is it true that any set is the subset of itself?
Yes
How can we mathematically indicate that two sets are equal?
A = B \iff A \subseteq B \land B \subseteq A
Is it true that for any set A, the empty set is included?
Yes, indeed: \forall A, \emptyset \subseteq A
Can we define sets in terms of other sets?
Yes
What are the set operations?
- Intersection
- Union
- Difference
What is the intersection operation?
A \cap B = { x : x \in A \land x \in B }
What is the union operation?
A \cup B = { x : x \in A \lor x \in B}
\lor indicates an inclusive or
What is the difference operation?
A - B = { x : x \in A \land x \notin B }
What is the intersection of the set A with the empty set?
The empty set
What is the union of the set A with an empty set?
The set A
How to name the laws describing?
- The intersection of the set A with the empty set
- The union of the set A with the empty set
Empty set laws
What are the idempotency laws?
A \cup A = A
A \cap A = A
Apply the commutative laws to the two given sets A and B
A \cup B = B \cup A
A \cap B = B \cap A
Apply the associative laws to the two given sets A and B
A \cap (B \cap C) = (A \cap B) \cap C
A \cup (B \cup C) = (A \cup B) \cup C
Apply the distributive laws to the two given sets A and B
A \cup (B \cap C) = (A \cup B) \cap (A \cup C)
A \cap (B \cup C) = (A \cap B) \cup (A \cap C)
Apply the absorption laws to the two given sets A and B
A \cap (A \cup B) = A
A \cup (A \cap B) = A
Apply the DeMorgan’s Laws to the two given sets A and B
A - (B \cap C) = (A - B) \cup (A - C)
A - (B \cup C) = (A - B) \cap (A - C)
When two sets are disjoint?
When they do not have any elements in common
It mathematically means: A \cap B = \emptyset
How a partition of the set S is defined?
A collection C of nonempty sets is defined a partition if:
- The sets are pairwise disjoint
- The unions of all the sets of the collection C compose the set S
How the cardinality (also called the size) of a set is defined?
The cardinality of a set is the number representing the number of elements (also called members) composing the set
What are the laws to which the set operations obey?
- Empty Sets laws
- Idempotency laws
- Commutative laws
- Associative laws
- Distributive laws
- Absorption laws
- DeMorgan’s laws
How to define the complement of the set A
A^c = U - A = { x : x \in U \land x \notin A }
How do we define a set whose cardinality is a natural number?
Finite set
How do we define a set whose cardinality is not a natural number?
Infinite
What types of infinite sets do exist?
- Countable infinite
- Uncountable infinite
What does it mean for a set to be countable finite?
The set could be put in a one-to-one correspondence with the \mathbb{N} or \mathbb{Z}
What does it mean for a set to be uncountable infinite?
The set could not be put in a one-to-one correspondence woth \mathbb{N} or \mathbb{Z}
What is the relationship of cardinality with union of two sets?
|A \cup B| = |A| + |B| - |A \cap B|
Is the triangle inequality applied to the cardinality of sets?
|A \cup B| \leq |A| + |B|
How is called a set of n elements?
n-set
How is called a set of 1 element?
Singleton
How is called a subset of k elements of a generic set?
k-subset
How do we call the set of all the subsets of a set S?
Power set
How many elements there are in a Power Set of a set S containing n elements?
2^n or 2^{|S|}
What will be the cardinality of a power set built over a set S having n elements?
2^n or 2^{|S|}
How to the define the ordered pair (a, b) according to the set theory?
(a, b) = { a, { a, b } }
How do we define the Cartesian product of two sets A and B?
The Cartesian Product of the two sets A and B is defined as the set of all the ordered pairs such that the first element of the pair is an element of A and the second element of the pair is an element of B
A \times B = { (a,b) : a \in A \land b \in B }
What is the cardinality of the cartesian product of two sets?
|A \times B| = |A| \cdot |B|
How the Cartesian Product of n sets is defined?
The Cartesian Product of n sets is the set of n-tuples
A_1 \times A_2 \times \ldots \times A_n = { (a_1, a_2, \ldots, a_n) : \forall a_i \in A_i, i = 1, 2, \ldots, n }
What is the cardinality of the Cartesian Product of n sets?
|A_1 \times A_2 \times \ldots \times A_n| = |A_1| \cdot |A_2| \cdot \ldots \cdot |A_n|
How is defined A^n?
A^n = A \times A \times \ldots \times A
How to define the cardinality of A^n
|A^n| = |A|^n, if A is finite
