Your cart is empty
Sets, statements, events
We have met sets and set operations in year \latex{9}, random events and operations that can be done on them in year \latex{10}, statements and logical operations in year \latex{12}. Now, as a summary, we would like to find connections between these ideas and observe the similarities of the operations and identities.
“Set” and “element of a set” are basic concepts. One can decide whether something belongs to a set or not. In a set, every element appears at most one time.
DEFINITION: Two sets are equal if their elements are the same. \latex{(A = B \leftrightarrow} for every \latex{x \in A} it follows that \latex{x \in B} as well and for every \latex{x \in B} it follows that \latex{x \in A} too.\latex{)}
DEFINITION: The empty set is which does not have any elements. It is denoted by \latex{\varnothing}.
DEFINITION: Set \latex{A} is a subset of set \latex{B} if every element of \latex{A} is also an element of \latex{B} \latex{(A \sube B \leftrightarrow} for every \latex{x \in A} it follows that \latex{x \in B} as well\latex{)}. Set \latex{A} is a real subset of \latex{B} \latex{(A \sub B)} if \latex{A \sube B} and there is an element in \latex{B} which does not belong to \latex{A}.
Every set is a subset of itself, \latex{A \sube A}.
The empty set is a subset of every set: \latex{\varnothing \sube A}.
DEFINITION: The fundamental set or universe is a set which every studied set is a subset of. It is denoted by \latex{U}.
When we are observing random events, we are said to conduct an experiment. In theory, the experiment can be repeated arbitrarily many times with the same conditions. We have to precisely define what we call the result of the experiment. For every result of the experiment there is an elementary event.
DEFINITION: The set of elementary events is the sample space.
DEFINITION: Subsets of the event space are called events. It is decidable whether an event occurs or not – that is, whether the elementary event belonging to the result of the experiment is an element of the subset of the event space which corresponds to the event.
DEFINITION: The certain event is an event that occurs no matter what. It is denoted by \latex{H}.
DEFINITION: The impossible event is an event that cannot occur. It is denoted by \latex{\varnothing}.
Example 1
A group of kids play with a regular die, for which they make the following cards
Ann: The rolled number is even.
Bill: The rolled number is odd.
Chris: The rolled number is a prime.
Dorothy: The rolled number is even and prime.
Edith: The rolled number is even or prime.
Fiona: The rolled number is odd or even.
Gabe: The rolled number is odd and even.
Bill: The rolled number is odd.
Chris: The rolled number is a prime.
Dorothy: The rolled number is even and prime.
Edith: The rolled number is even or prime.
Fiona: The rolled number is odd or even.
Gabe: The rolled number is odd and even.
Find the connection between the statements on the kids’ cards, the sets defined by the statements and the corresponding random events.
Solution
The set of numbers possibly rolled using a regular die is
\latex{U=\lbrace1;2;3;4;5;6\rbrace}.
After the roll, we observe the number rolled; this way we conduct an experiment with event space
\latex{H=\lbrace1;2;3;4;5;6\rbrace}.
Let us denote the statement from Ann's card by \latex{p_A}, the set of numbers satisfying the statement from the card by \latex{A}: \latex{A=\lbrace2;4;6\rbrace}, and the event corresponding to the card with \latex{E_A}.
We use similar notations for the other cards.
Bill's statement is the negation of Ann's statement: \latex{p_B = \neg p_A}.
The set of numbers corresponding Bill's card, \latex{B = \lbrace 1; 3; 5\rbrace}, is exactly the complement of set \latex{A: B = \overline{A}}.
The event corresponding to Bill's card will occur if the event corresponding to Ann's card will not occur, that is, \latex{E_B} is the complement of \latex{E_A: E_B = \overline{E_A}}.
The statement, set and event corresponding to Chris' card are denoted similarly: \latex{p_C, C = \lbrace 2; 3; 5\rbrace, E_C}.
Let us find the statement, set, event corresponding to Dorothy's card.
The statement on Dorothy's card is true exactly when those of Ann and Chris are both true: \latex{p_D = p_A \land p_C}.
The numbers satisfying Dorothy's card are exactly those which satisfiy Ann's and Chris' cards: \latex{D =\lbrace 2 \rbrace}, that is, \latex{D} equals the intersection of the sets \latex{A} and \latex{C}: \latex{D = A \cap C}.
The event corresponding to Dorothy's card occurs exactly when those belonging to Ann's and Chris' occur, that is, \latex{E_D} is the the product of the events \latex{E_A} and \latex{E_C}: \latex{E_D = E_A \times E_C}.
The statement on Edith's card is true exactly when at least one of those of Ann and Chris is true: \latex{p_E = p_A \lor p_C}.
The numbers satisfying Edith's card are those which elements of at least one of the sets satisfying either Ann's or Chris' card: \latex{E = \lbrace2; 3; 4; 5; 6\rbrace}, that is, set \latex{E} is the union of sets \latex{A} and \latex{C}: \latex{E = A \cup C}.
The event corresponding to Edith's card occurs exactly when at least one of the events corresponding to Ann's and Chris' cards occurs, that is, \latex{E_E} is the sum of the events \latex{E_A} and \latex{E_C}: \latex{E_E = E_A + E_C}.
The statement on Fiona's card is true for every number possibly rolled: \latex{p_F = p_A \lor p_B = t}, where \latex{t} denotes the statement which is true in each case. Since \latex{p_A = \neg p_B}, it follows that \latex{p_F = p_A \lor \neg p_A = t}.
The set corresponding to Fiona's card contains every number possibly rolled: \latex{F= \lbrace 1; 2; 3; 4; 5; 6 \rbrace}, \latex{F = A \cup B = U}, where \latex{U} is the fundamental set. Since \latex{B = \overline{A}}, it follows that \latex{F = A \cup \overline{A} = U}.
The event corresponding to Fiona's card occurs for every possible roll: \latex{E_F = E_A +E_B = H}, where \latex{H} denotes the certain event. Since \latex{E_B = \overline{E_A }}, it follows that \latex{E_F = E_A + \overline{E_A} = H}.
The statement corresponding to Gabe's card is not true for any of the numbers possibly rolled: \latex{p_G = p_A \land p_B = f}, where \latex{f} denotes the statement which is always false. Since \latex{p_A = \neg p_B}, it follows that \latex{p_G = p_A \land \neg p_A = f}.
The set corresponding to Gabe's card does not contain any elements, \latex{G = A\cap B = \varnothing}, where \latex{\varnothing} is the empty set. Since \latex{B = \overline{A}}, it follows that \latex{G = A \cap \overline{A} = \varnothing}.
The event corresponding to Gabe's card does not occur for any possible roll: \latex{E_G = E_A \times E_B = \varnothing}, where \latex{\varnothing} is the impossible event. Since \latex{E_B = \overline{E_A}} , it follows that \latex{E_G = E_ A \times \overline{E_A} = \varnothing}.
◆ ◆ ◆
Let us summarize the logical, set and event operations used in the previous example.
The negation of a state-
ment is the statement
which is true if the original
statement is false and
false if the original is true.
ment is the statement
which is true if the original
statement is false and
false if the original is true.
Negation
Conjuction
Disjunction
The conjunction of two
statements is true if and
only if both statements
are true, otherwise it is
false.
statements is true if and
only if both statements
are true, otherwise it is
false.
The disjunction of the
statements is true if and
only at least one state-
ment is true, otherwise
it is false.
statements is true if and
only at least one state-
ment is true, otherwise
it is false.
\latex{A}
\latex{\neg A}
\latex{A}
\latex{B}
\latex{A\land B}
\latex{A}
\latex{B}
\latex{A\land B}
\latex{t}
\latex{f}
\latex{f}
\latex{t}
\latex{t}
\latex{t}
\latex{f}
\latex{f}
\latex{t}
\latex{f}
\latex{t}
\latex{f}
\latex{t}
\latex{f}
\latex{f}
\latex{f}
\latex{t}
\latex{t}
\latex{f}
\latex{f}
\latex{t}
\latex{f}
\latex{t}
\latex{f}
\latex{t}
\latex{t}
\latex{f}
\latex{t}
The complement set of a set \latex{A} is the set of the elements of the fundamental set which are not in the set \latex{A}. (Figure 1)
The union of two sets is the set of the elements which are in at least one of the two sets. (Figure 2)
\latex{U}
\latex{A}
\latex{B}
Figure 1
The intersection of two sets is the set of the elements which are elements of both sets. (Figure 3)
The complement of an event \latex{A} is the event which occurs exactly when \latex{A} does not occur.
The product of two events is the event which occurs exactly when both events occur.
The sum of two events is the event which occurs exactly when at least one event occurs.
\latex{U}
\latex{A}
\latex{U}
\latex{B}
\latex{A}
\latex{B}
Figure 2
From these, one can see that there are many similarities between statements, sets and events, as well as between the possible operations on them. Logical statements, subsets of the base set and events are corresponding ideas. Negation corresponds to taking the complement, conjunction to taking the intersection or multiplying events, disjunction to taking the union or adding events.
Let us take a look at identities of operations in logic, between sets and between events at the same time:
\latex{U}
\latex{A}
\latex{B}
Figure 3
Statements
Sets
Events
Commutativity
Associativity
Element that does not
modify other elements
modify other elements
Taking the complement
Distributivity
Idempotency
Other equivalences
De Morgan’s laws
\latex{A \land B = B \land A}
\latex{A \lor B = B \lor A}
\latex{A \lor B = B \lor A}
\latex{A \land \left( B \land C \right) = \left(A \land B \right) \land C}
\latex{A \lor\left( B \lor C \right) = \left(A \lor B \right) \lor C}
\latex{A \lor\left( B \lor C \right) = \left(A \lor B \right) \lor C}
\latex{A \land t = A}
\latex{A \lor f = A}
\latex{A \lor f = A}
\latex{A \land \neg A = f}
\latex{A \lor \neg A = t}
\latex{A \lor \neg A = t}
\latex{A \land \left(B \lor C \right) = \left(A \land B \right)\lor \left(A \land C \right)}
\latex{A \lor \left(B \land C \right) = \left(A \lor B \right)\land \left(A \lor C \right)}
\latex{A \lor \left(B \land C \right) = \left(A \lor B \right)\land \left(A \lor C \right)}
\latex{A \land A = A}
\latex{A \lor A = A}
\latex{A \lor A = A}
\latex{A \land f = f}
\latex{A \lor t = t}
\latex{\neg \left(\neg A\right)= A}
\latex{A \lor t = t}
\latex{\neg \left(\neg A\right)= A}
\latex{\neg \left(A \land B\right) = \neg A \lor\neg B}
\latex{\neg \left(A \lor B\right) = \neg A \land\neg B}
\latex{\neg \left(A \lor B\right) = \neg A \land\neg B}
\latex{A \cap B = B \cap A}
\latex{A \cup B = B \cup A}
\latex{A \cup B = B \cup A}
\latex{A \cap\left( B \cap C \right) = \left(A \cap B \right) \cap C}
\latex{A \cup\left( B \cup C \right) = \left(A \cup B \right) \cup C}
\latex{A \cup\left( B \cup C \right) = \left(A \cup B \right) \cup C}
\latex{A \cap U = A}
\latex{A \cup \varnothing = A}
\latex{A \cup \varnothing = A}
\latex{A \cap \overline{A} = \varnothing}
\latex{A \cup \overline{A} = U}
\latex{A \cup \overline{A} = U}
\latex{A \cap \left(B \cup C \right) = \left(A \cap B \right)\cup \left(A \cap C \right)}
\latex{A \cup \left(B \cap C \right) = \left(A \cup B \right)\cap \left(A \cup C \right)}
\latex{A \cup \left(B \cap C \right) = \left(A \cup B \right)\cap \left(A \cup C \right)}
\latex{A \cap A = A}
\latex{A \cup A = A}
\latex{A \cup A = A}
\latex{A \cap \varnothing = f}
\latex{A \cup U = U}
\latex{\overline{\overline{A}} = A}
\latex{A \cup U = U}
\latex{\overline{\overline{A}} = A}
\latex{\overline{A \cap B} = \overline{A} \cup \overline{B}}
\latex{\overline{A \cup B} = \overline{A} \cap \overline{B}}
\latex{\overline{A \cup B} = \overline{A} \cap \overline{B}}
\latex{A \times B = B \times A}
\latex{A+ B = B + A}
\latex{A+ B = B + A}
\latex{A \times\left( B \times C \right) = \left(A \times B \right) \times C}
\latex{A +\left( B + C \right) = \left(A + B \right) + C}
\latex{A +\left( B + C \right) = \left(A + B \right) + C}
\latex{A \times U = A}
\latex{A + \varnothing = A}
\latex{A + \varnothing = A}
\latex{A \times \overline{A} = \varnothing}
\latex{A + \overline{A} = H}
\latex{A + \overline{A} = H}
\latex{A \times \left(B+C \right) = \left(A \times B \right)+\left(A \times C \right)}
\latex{A + \left(B \times C \right) = \left(A + B \right)\times \left(A + C \right)}
\latex{A + \left(B \times C \right) = \left(A + B \right)\times \left(A + C \right)}
\latex{A \times A = A}
\latex{A + A = A}
\latex{A + A = A}
\latex{A \times \varnothing = \varnothing}
\latex{A + H = H}
\latex{\overline{\overline{A}} = A}
\latex{A + H = H}
\latex{\overline{\overline{A}} = A}
\latex{\overline{A \times B} = \overline{A} + \overline{B}}
\latex{\overline{A + B} = \overline{A} \times \overline{B}}
\latex{\overline{A + B} = \overline{A} \times \overline{B}}
We can see that both the logical statements with the operations negation, conjunction, disjunction, the sets with the operations taking the complement, intersection, union, and the events with the operations taking the complement, product, sum form similar structures. This kind of structure is called Boolean algebra. Its advantage is that any proven equivalence will be true for statements, sets and events.
Example 2
Using the set diagram of parallelograms and kites (Figure 4) decide which of the following statements are true:
- Not every rhombus is a kite.
- There is no parallelogram which is kite.
- There is a rhombus which is not a parallelogram.
- Every kite is a parallelogram.
rhombuses
parallelograms
kites
Figure 4
Solution (a)
The statement is false since for the rhombus it is true that its neighboring sides are equal thus it is a kite.
The set of rhombuses is a subset of the set of kites, therefore the statement “every rhombus is a kite” is true.
Solution (b)
The statement is false since the intersection of the set of parallelograms and kites is nonempty, that is, there is a parallelogram which is also a kite since every rhombus have this property.
Solution (c)
The negation of the statement: “It is not true that there exists such a rhombus, which is not a parallelogram”, that is, “For every rhombus it is false that it is not a parallelogram, so any rhombus is a parallelogram”.
This statement is true since it is true for any rhombus that its neighboring sides are parallel, the set of rhombuses is a subset of the set of parallelograms. The negation of the original statement is true therefore the original statement is false.
Solution (d)
The negation of this statement is “It is not true that every kite is a parallelogram”, that is, “There exists some kite which is not a parallelogram”.
This statement is true since there exists some kite whose opposing sides are not parallel, thus the set of kites is not a subset of the set of parallelograms. The negation of the original statement is true, therefore the original statement is false.
Exercises
{{exercise_number}}. Alice invited a few of her classmates for lunch. Previously she had asked every classmate whether they like fish or not; like vegetables or not; like sweets or not. She noticed that she invited all of her classmates from the hatched regions of the diagram below and no one else (\latex{F} is the set of those who like fish, \latex{V} is the set of those who like vegetables and \latex{S} is the set of those who like sweets).
Define the set of guests using the set operations (and sets \latex{F, V, S}).
\latex{F}
\latex{V}
\latex{S}
Characterize the taste of the guests using logical operations (and statemets \latex{p_F, p_V, p_S})
Alice chooses guests at random from her classmates. Describe the event that someone gets an invitation using the events \latex{E_F, E_V, E_S} and operations.
Assemble a menu such that every guest can find something appropriate to their tastes.
{{exercise_number}}. Of the following conclusions which ones are true, which ones are false? Reason using a set diagram.
- Every weightlifter is strong.
There exists a footballer who is strong.
Therefore every ancient artifact is valuable.
- Every coin is valuable.
There exists an ancient coin.
Therefore there exists a footballer who is a weightlifter.
- Every fisherman is patient.
There exists a fisherman who is a liar.
Therefore there exists a liar who is not a fisherman.
- Every fisherman is patient.
Some historians are clever.
Therefore some mathematicians are historians.
{{exercise_number}}. During a whimsical April for every day it was recorded whether it was a rainy day or not; a windy day or not; a sunny day or not. After summarizing the data the following is known:
sunny and rainy
sunny and not rainy
not sunny and rainy
neither sunny nor rainy
windy
not windy
\latex{ 5 }
\latex{ 4 }
\latex{ 3 }
\latex{ 3 }
\latex{ 4 }
\latex{ 3 }
\latex{ 1 }
Unfortunately, the number in the bottom right corner of the table is blurred. What was that number?
If \latex{R} is the set of rainy days, \latex{W} is the set of windy days and \latex{S} is the set of sunny days, then formulate the properties of the days belonging to the following sets and give the number of days in each set!
- \latex{S};
- \latex{\overline{R}};
- \latex{\overline{R} \cap\overline{W} \cap \overline{S}};
- \latex{W \cup R};
- \latex{\overline{R} \cap\overline{W}};
- \latex{S \cap \left( W \cup R \right)}.
{{exercise_number}}. Draw a set diagram for the following sets and formulate true and false statements concerning them.
- Natural numbers divisible by \latex{2}, natural numbers divisible by \latex{10}, natural numbers divisible by \latex{3}, natural numbers divisible by \latex{5};
- isosceles triangles, right angled triangles, triangles with exactly one \latex{60º} angle.