logic questions redux Flashcards
Explain why ∅ ⊆ A holds for every set A.
If every member of a set A is also a member of set B we say that A is a subset of B.
But there is no element which is a member of ∅, the precondition of the definition is false, so the conditional in whole holds vacuously.
That is, for every set A, ∅ ⊆ A.
Explain the difference between ∅ and {∅}.
Set {∅} is a set with a member ∅, but ∅ is a set containing no member
What is the composition of {(n, n + 2) | n ∈ N} with itself?
It is {(n, n + 4) | n ∈ N}
Show that it follows from Rˇ⊆ R that R = Rˇ
We need to show R ⊆ Rˇ.
For every x, y, (x, y) ∈ R, (y, x) ∈ Rˇ.
Then (y, x) ∈ R since Rˇ⊆ R.
It follows that (x, y) ∈ Rˇ, as required.
Which of the following relations are transitive?
(1) {(1, 2),(2, 3),(3, 4)}
(2) {(1, 2),(2, 3),(3, 4),(1, 3),(2, 4)}
(3) {(1, 2),(2, 3),(3, 4),(1, 3),(2, 4),(1, 4)}
(4) {(1, 2),(2, 1)}
(5) {(1, 1),(2, 2)}
(3) and (5)
Check that a relation R is transitive if and only if it holds that R ◦ R ⊆ R
First check the direction from left to right.
Suppose R is transitive and for arbitrary x, y, (x, y) ∈ R ◦ R.
It means that there exists some z such that (x, z) ∈ R and (z, y) ∈ R.
Since R is transitive, we can have that (x, y) ∈ R as well. Next check the direction from right to left.
Suppose R ◦ R ⊆ R and for arbitrary x, y, z, (x, y) ∈ R and (y, z) ∈ R.
Then (x, z) ∈ R ◦ R.
It follows that (x, z) ∈ R since R ◦ R ⊆ R, as required.
Can you give an example of a transitive relation R for which R ◦ R = R does not hold?
Yes.
Please see the relation < on N.
It is clear that this relation is transitive but < ◦ <=< (over N) does not hold.
Show that any asymmetric relation has to be irreflexive. (Hint: assume that a relation is asymmetric, and suppose it contains a loop (x, x). Why is this impossible?)
Assume that a relation R is asymmetric, and suppose it contains a loop (x, x).
But by the definition of asymmetric, for every x, y, (x, y) ∈ R → (y, x) ∈/ R.
It follows (x, x) ∈/ R since (x, x) ∈ R, a contradiction.
So any asymmetric has to be irreflexive.
Consider the three predicate logical sentences (A.1), (A.3) and (A.6), These sentences together express that a certain binary relation R is an equivalence relation: symmetric, transitive and reflexive.
Show that none of these sentences is semantically entailed by the other ones by choosing for each pair of sentences a model (situation) that makes these two sentences true but makes the third sentence false.
In other words: find three examples of binary relations,
each satisfying just two of the properties in the list (A.1), (A.3) and (A.6).
This shows, essentially, that the definition of being an equivalence cannot be simplified (why?).
(/R)TS = {(2, 1),(1, 2)};
R(/T)S = {(1, 1),(2, 2),(3, 3),(1, 2),(2, 1),(2, 3),(3, 2)};
RT(/S) = {(1, 1),(2, 2),(1, 2)}.
What these examples show is that reflexivity does not follow from transitivity and symmetry, that transitivity does not follow from reflexivity and symmetry, and that symmetry does not follow from reflexivity and transitivity.
Consider the following predicate logical formulas:
• ∀x∀y(Rxy → ¬Ryx) (R is asymmetric)
• ∀x∃yRxy (R is serial)
• ∀x∀y∀z((Rxy ∧ Ryz) → Rxz) (R is transitive).
Take any situation with a non-empty domain of discourse, with a binary relation on it.
Show: if the three formulas are true of this situation, then the domain of discourse must be infinite.
(Hint: start with a domain consisting of a single individual d1.
Then by seriality there has to be an R successor to d1. Suppose we take d1 as its own R-successor. Then this would get us in conflict with we are in conflict with asymmetry.
So there has to be a d2 with (d1, d2) in R.
And so on . . . )
Base case: Proved in the text.
Induction Hypothesis: If |M| < n then ∃x∃y(Rxy ∧ Ryx) or ∃x∀y¬Rxy or ∃x∃y∃z(Rxy ∧ Ryx ∧ ¬Rxz).
Induction step:
take an arbitrary model such that |M| = n − 1
and build M0 with dom(M0) = dom(M) ∪ {a}, such that R0 = R ∪ Ra
where Ra ⊆ RA
with RA = {(x, y) | x ∈ dom(M), y = a} ∪ {(x, y) | y ∈ dom(M), x = a} ∪ {(x, y) | x = a, y = a}.
If ∃x∃y∃z(Rxy ∧ Ryx ∧ ¬Rxz)
then ∃x∃y∃z(R’xy∧R’yx∧¬R’xz) and we are done.
If ∃x∃y(Rxy∧Ryx) then ∃x∃y(R’xy∧R’yx) and we are done.
If ¬∃x∃y(Rxy ∧ Ryx) and ¬∃x∃y∃z(Rxy ∧ Ryx ∧ ¬Rxz) and ∃x∀y¬Rxy then if for some x ∈ M that has no successor we have ¬R’xa we are done.
Suppose that for all x ∈ M that have no successors we have R’xa, then in order for M’ to be serial we need to have R’ay for some y ∈ M’.
If Raa then asymmetry is violated and we are done.
Take an arbitrary z ∈ M’
such that R’za and z (/=) a then if we have R’az, asymmetry is again violated and we are
done. If, for arbitrary z, y ∈ M’ we have R’za, R’ay and y (/=) z we have to consider two cases.
If ¬Ryz then transitivity is violated and we are done. In case Ryz then we have R’ay, R’yz, and R’za.
If we satisfy transitivity of R’ then we must also have R’aa which in turn violates the asymmetry condition.
The successor function s : N ↦ N on the natural numbers is given by n ↦ n + 1.
What is the composition of s with itself?
n ↦ n + 2
≤ is a binary relation on the natural numbers.
What is the corresponding characteristic function?
The corresponding characteristic function is f : N² → {True, False}.
For every pair (m, n) ∈ N²,
if m ≤ n
then f((m, n)) = True,
otherwise, f((m, n)) = false.Let f : A → B be a function. Show that the relation R ⊆ A² given by (x, y) ∈ R if and only if f(x) = f(y) is an equivalence relation (reflexive, transitive and symmetric) on A.
Let f : A → B be a function. Show that the relation R ⊆ AN² given by (x, y) ∈ R if and only if f(x) = f(y) is an equivalence relation (reflexive, transitive and symmetric) on A.
Suppose relation R ⊆ AN² given by (x, y) ∈ R if and only if f(x) = f(y).
We need to show that R is an equivalence relation.
First check reflexivity:
for every x ∈ A, we havef(x) = f(x) since f is a function. It follows that (x, x) ∈ R, as required.
Next check symmetry:
for every pair (x, y) ∈ R, we have x, y ∈ A and then f(x) = f(y).
It’s clear f(y) = f(x) meaning that (y, x) ∈ R.
Similarly we can check transitivity: for every x, y, zA, (x, y) ∈ R and (y, z) ∈ R, it follows that f(x) = f(y) and f(y) = f(z) by the premise.
Then we have f(x) = f(z).
It follows by the same reason that (x, z) ∈ R, as required.
Consider the case where there are three facts that you are interested in.
You wake up, you open your eyes, and you ask yourself three things:
“Have I overslept?”,
“Is it raining?”,
“Are there traffic jams on the road to work?”.
To find out about the first question, you have to check your alarm clock, to find out about the second you have to look out of the window, and to find out about the third you have to listen to the traffic info on the radio.
We can represent these possible facts with three basic propositions, p, q and r, with p expressing “I have overslept”, q expressing “It is raining”, and r expressing “There are traffic jams.”
Suppose you know nothing yet about the truth of your three facts.
What is the space of possibilities?
_
p q r p q r
_ _ _
p q r p q r
_ _ _
p q r p q r
_ _ _ _ _
p q r p q rWrite in propositional logic:
• I will only go to school if I get a cookie now.
• John and Mary are running.
• A foreign national is entitled to social security if he has legal employment or if he has had such less than three years ago, unless he is currently also employed abroad.
• I will only go to school if I get a cookie now:
(p → q) ∧ (q → p)
where p =“I get a cooky now” and q =“I will go to school”.
• John and Mary are running:
p ∧ q
where p =“John is running” and q =“Mary is running”.
• A foreign national is entitled to social security if he has legal employment or if he
has had such less than three years ago, unless he is currently also employed abroad:
((p ∨ q) ∧ ¬r) → s
where p =“A foreign national has legal employment”, q =“A foreign national has
had legal employment less then three years ago”, r =“A foreign national is currently
also employed abroad” and s =“A foreign national is entitled to social security”.
Which of the following are formulas in propositional logic:
• p → ¬q
• ¬¬ ∧ q ∨ p
• p¬q
Only the first one
Construct truth tables for the following formula:
• (p → q) ∨ (q → p),
(p → q) ∨ (q → p)
0 1 0 1 0 1 0
0 1 1 1 1 0 0
1 0 0 1 0 1 1
1 1 1 1 1 1 1
Construct truth tables for the following formulas:
• ((p ∨ ¬q) ∧ r) ↔ (¬(p ∧ r) ∨ q).
((p ∨ ¬ q) ∧ r) ↔ (¬ (p ∧ r) ∨ q)
0 1 1 0 0 0 0 1 0 0 0 1 0 0 1 1 0 1 1 1 1 0 0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 0 1 1 1 1 1 1 0 0 0 0 1 1 0 0 1 0 1 1 1 0 1 1 0 0 1 1 1 0 0 1 1 0 1 0 0 0 1 1 0 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1
Using truth tables, investigate all formulas that can be readings of
¬p → q ∨ r
(by inserting brackets in appropriate places), and show that they are not equivalent
e.g.
¬p → q) ∨ r and ¬(p → (q ∨ r)
Using a truth table, determine if the two formulas
¬p → (q ∨ r), ¬q
together logically imply
(1) p ∧ r.
(2) p ∨ r.
Display the complete truth table, and use it to justify your answers to (1) and (2).
p q r ¬p ¬q q ∨ r ¬p →
(q ∨ r)
p ∧ r p ∨ r
0 0 0 1 1 0 0 0 0
0 0 1 1 1 1 1 0 1
0 1 0 1 0 1 1 0 0
0 1 1 1 0 1 1 0 1
1 0 0 0 1 0 1 0 1
1 0 1 0 1 1 1 1 1
1 1 0 0 0 1 1 0 1
1 1 1 0 0 1 1 1 1
You can check by inspecting the rows of the table that p ∧ r is not a valid consequence
and p ∨ r is.
Which of the following pairs are logically equivalent? Confirm your answer using truth tables: (1) ϕ → ψ and ψ → ϕ (2) ϕ → ψ and ¬ψ → ¬ϕ (3) ¬(ϕ → ψ) and ϕ ∨ ¬ψ (4) ¬(ϕ → ψ) and ϕ ∧ ¬ψ (5) ¬(ϕ ↔ ψ) and ¬ϕ ↔ ¬ψ (6) ¬(ϕ ↔ ψ) and ¬ϕ ↔ ψ (7) (ϕ ∧ ψ) ↔ (ϕ ∨ ψ) and ϕ ↔ ψ
By comparing the first and the second tables below you can determine that the equivalence does not hold for item (3)
while by comparing the first and the third tables below you can determine that the equivalence does hold for item (4).
The other items are similar.
¬ (p → q) 0 0 1 0 0 0 1 1 1 1 0 0 0 1 1 1
p ∨ ¬ q 0 1 1 0 0 0 0 1 1 1 1 0 1 1 0 1
p ∧ ¬ q 0 0 1 0 0 0 0 1 1 1 1 0 1 0 0 1
Check if the following is a valid consequence:
¬(q ∧ r), q |= ¬r
¬(q ∧ r)
=⇒
q
q r
_ _
q r q r
_ _
q r q r
_ _ _ _ _
q r q r q rCheck if the following is a valid consequence:
¬p ∨ ¬q ∨ r, q ∨ r, p |= r
¬p ∨ ¬q ∨ r
q ∨ r
p
p q r _ p q r p q r _ _ p q r p q r _ _ _ _ p q r p q r p q r _ _ _ p q r p q r p q r _ _ _ _ _ p q r p q r p q r _ _ _ _ _ _ p q r p q r p q r p q r _ _ _ _ _ _ _ _ _ p q r p q r p q r p q r
Give truth tables for the following formula:
(p ∨ q) ∨ ¬(p ∨ (q ∧ r))
(p ∨ q) ∨ ¬ (p ∨ (q ∧ r)) 0 0 0 1 1 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 1 0 1 1 1 1 0 0 1 0 0 1 0 1 1 1 0 0 1 1 1 1 1 1 1 0 1 0 1 1 0 0 0 1 1 1 0 1 0 1 1 0 0 1 1 1 1 1 1 0 1 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1
Give truth tables for the following formula:
¬((¬p ∨ ¬(q ∧ r)) ∨ (p ∧ r))
¬ ((¬ p ∨ ¬ (q ∧ r)) ∨ (p ∧ r)) 0 1 0 1 1 0 0 0 1 0 0 0 0 0 1 0 1 1 0 0 1 1 0 0 1 0 0 1 0 1 1 1 0 0 1 0 0 0 0 0 1 0 1 0 1 1 1 1 0 0 1 0 0 0 1 1 1 0 0 0 1 1 0 0 0 0 0 1 1 1 0 0 1 1 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 0 0 0 1 0 0 1 1 1 1 1 1 1 0
Give truth tables for the following formula:
p → (q → r)) → ((p → q) → (p → r)
(p → (q → r)) → ((p → q) → (p → r)) 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0 1 1 0 0 1 0 1 1 1 0 1 0 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 0 1 0 1 1 0 0 1 1 0 0 1 1 1 0 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Give truth tables for the following formula:
p ↔ (q → r)) ↔ ((p ↔ q) → r
(p ↔ (q → r)) ↔ ((p ↔ q) → r) 0 0 0 1 0 1 0 1 0 0 0 1 0 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 0 1 0 0 1 1 0 1 0 0 1 1 1 0 0 0 1 1 1 0 1 1 0 1 0 1 1 0 0 1 0 1 1 1 0 1 1 1 1 0 0 1 1 1 1 0 1 0 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1
Give truth tables for the following formula:
(p ↔ q) ∧ (¬q → r)) ↔ (¬(p ↔ r) → q
((p ↔ q) ∧ (¬ q → r)) ↔ (¬ (p ↔ r) → q) 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 1 0 1 1 0 1 0 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 1 0 1 1 0 0 0 1 0 0 1 1 1 0 1 0 0 1 1 1 0 1 0 0 0 1 0 0 0 1 1 1 0 0 0 0 1 1 0 0 0 1 0 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 1 1 0 1 1 1 0 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1
Define all connectives in terms of ¬ and ∧.
ϕ ∨ ψ ≡ ¬(¬ϕ ∧ ¬ψ) ϕ → ψ ≡ ¬ϕ ∨ ψ ϕ ↔ ψ ≡ (ϕ → ψ) ∧ (ψ → ϕ) ϕ ⊕ ψ ≡ ¬(ϕ ↔ ψ) ϕ | ψ ≡ ¬(ϕ ∧ ψ)
Define all connectives in terms of ¬ and →
ϕ ∧ ψ ≡ ϕ → ¬ψ ϕ ∨ ψ ≡ ¬(¬ϕ ∧ ¬ψ) ϕ ↔ ψ ≡ (ϕ → ψ) ∧ (ψ → ϕ) ϕ ⊕ ψ ≡ ¬(ϕ ↔ ψ) ϕ | ψ ≡ ¬(ϕ ∧ ψ)
Prove that all propositional connectives are definable with the ‘Sheffer stroke’
ϕ | ψ,
defined by ¬ϕ ∨ ¬ψ
p q s1: ¬P = P|P s2: P∧Q = p | q s3: (?) q | q s4: True = p | s1 s5: (?) p | s2 s6: p→q q | s1 s7: p^q = s1 | s3 s2 | s4 s2 | s7 1 1 0 0 0 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1 0 0 0 1 1 1 0 1 1 0 1 0 0 0 0 1 1 1 1 1 1 0 0 1
Give an example of a formula φ and a Kripke model M, with the following properties:
(i) M |= φ, and (ii) M | φ 6|= φ. In other words, public announcement of φ has the
effect that φ becomes false.
The simplest example is a model where p is true but agent a does not know
that. Then publicly announcing ‘p is true, but you don’t know it’ will result in a
situation where what gets announced is falsified by the announcement itself. The
formula for this is p ∧ ¬Kap.
Prove that lfp (λS.S ∪ (Sˇ ◦ S)) R is the euclidean closure of R.
similar to the reasoning in the previous exercise. Let f = λS.S ∪ (Sˇ ◦ S),
and let E = lfp f R.
Then f is monotone, i.e., for all arguments X, X ⊆ f(X). In particular, R ⊆
f(R) ⊆ . . . ⊆ E. This shows that R ⊆ E.
We show that E is euclidean. Since E is a fixpoint, E = f(E), i.e., E = E∪(Eˇ◦E).
In other words, Eˇ◦E ⊆ E. It follows from this that E is euclidean by an argument
given in the course slides.
Finally, we show that E is the smallest euclidean relation that includes R. Let S be
an arbitrary euclidean relation with R ⊆ S. From euclideanness of S it follows that
Sˇ ◦ S ⊆ S. Therefore, S = f(S), i.e., S is a fixpoint. Since E is the least fixpoint
it follows that E ⊆ S.
Prove that lfp (λS.S ∪(S ◦ S)) R is the transitive closure of R. (lfp f c is the least fixpoint of the operation f, starting from c.)
Let f = λS.S ∪ (S ◦ S), and let T = lfp f R.
Then f is monotone, i.e., for all arguments X, X ⊆ f(X). In particular, R ⊆ f(R) ⊆ . . . ⊆ T. This shows that R ⊆ T.
We show that T is transitive. Since T is a fixpoint, T = f(T), i.e., T = T ∪(T ◦ T).
In other words, T ◦ T ⊆ T. It follows from this that T is transitive by the result of the first exercise
Finally, we show that T is the smallest transitive relation that includes R. Let S be an arbitrary transitive relation with R ⊆ S. From transitivity of S it follows that S ◦ S ⊆ S. Therefore, S = f(S), i.e., S is a fixpoint. Since T is the least fixpoint it follows that T ⊆ S.
Prove that
R ∪ (Rˇ ◦ (R ∪ Rˇ)∗ ◦ R)
is the euclidean closure of R.
Let E be the relation R ∪ (Rˇ ◦ (R ∪ Rˇ)∗ ◦ R). Clearly, R ⊆ E.
We show that E is euclidean. Let (x, y) ∈ E,(x, z) ∈ E. Then there are three cases to consider.
Case 1. (x, y) ∈ R,(x, z) ∈ R. Then (y, z) ∈ Rˇ ◦ R. Since Rˇ ◦ R ⊆ E, it follows that (y, z) ∈ E.
Case 2. (x, y) ∈ R, (x, z) ∈ Rˇ ◦ (R ∪ Rˇ)m ◦ R, for some m ∈ N.
From the givens, (y, z) ∈ Rˇ ◦ Rˇ ◦ (R ∪ Rˇ)m ◦ R.
It follows that (y, z) ∈ Rˇ ◦ (R ∪ Rˇ)m+1 ◦ R, and therefore (y, z) ∈ E.
Case 3. (x, y) ∈ Rˇ ◦ (R ∪ Rˇ)∗ ◦ R, (x, z) ∈ Rˇ ◦ (R ∪ Rˇ)∗ ◦ R. Now we get from the euclideanness of Rˇ ◦ (R ∪ Rˇ)∗ ◦ R (proved in a previous exercise) that (y, z) ∈ Rˇ ◦ (R ∪ Rˇ)∗ ◦ R, and therefore (y, z) ∈ E.
Finally, we have to prove that E is the smallest relation with the required properties.
Let S be an arbitrary euclidean relation that includes R. We must show that E ⊆ S.
Since S is euclidean, we know from the previous exercise that Sˇ◦ (S ∪Sˇ)∗ ◦S ⊆ S.
Since R ⊆ S we also have
Rˇ ◦ (R ∪ Rˇ)∗
◦ R ⊆ Sˇ ◦ (S ∪ Sˇ)∗
◦ S ⊆ S.
From this, together with R ⊆ S, it follows that E ⊆ S.
Prove by induction that if R is an euclidean relation, then Rˇ ◦ (R ∪ Rˇ)∗ ◦ R ⊆ R.
Basis: Rˇ ◦ R ⊆ R. This follows from the euclideanness of R.
Induction step. The induction hypothesis is that Rˇ◦ (R ∪ Rˇ)n ◦ R ⊆ R. We must prove that Rˇ ◦ (R ∪ Rˇ)n+1 ◦ R ⊆ R.
We are done if we can prove the following two facts: (i) Rˇ◦ R ◦ (R ∪ Rˇ)n ◦ R ⊆ R, and (ii) Rˇ ◦ Rˇ ◦ (R ∪ Rˇ)n ◦ R ⊆ R.
(i) Assume (x, y) ∈ Rˇ ◦ R ◦ (R ∪ Rˇ)n ◦ R. Then there is a z with (x, z) ∈ Rˇ ◦ R and (z, y) ∈ (R ∪ Rˇ)n ◦ R.
By the fact that Rˇ◦R is symmetric, (z, x) ∈ Rˇ◦R. From this and euclideanness of R, (z, x) ∈ R, and therefore (x, z) ∈ Rˇ. Combining this with (z, y) ∈ (R ∪ Rˇ)n ◦ R
we get that (x, y) ∈ Rˇ ◦ (R ∪ Rˇ)n ◦ R, from which it follows by the induction hypothesis that (x, y) ∈ R.
(ii) Assume (x, y) ∈ Rˇ◦ Rˇ◦ (R ∪ Rˇ)n ◦ R. Then there is a z with (x, z) ∈ Rˇ and (z, y) ∈ Rˇ ◦ (R ∪ Rˇ)n ◦ R. From the first of these, (z, x) ∈ R. From the second of these, by induction hypothesis, (z, y) ∈ R. From (z, x) ∈ R and (z, y) ∈ R by euclideanness of R, (x, y) ∈ R
Show that for any relation R, the relation Rˇ◦ (R∪Rˇ)∗ ◦R is symmetric, transitive and euclidean.
Use E for Rˇ◦(R∪Rˇ)∗ ◦R. For symmetry of E, let (x, y) ∈ E. Then there is some m ∈ N with (x, y) ∈ Rˇ ◦ (R ∪ Rˇ)m ◦ R. So there are z, u with (x, z) ∈ Rˇ, (z, u) ∈ (R ∪ Rˇ)m, (u, y) ∈ R. But then (y, u) ∈ Rˇ, (u, z) ∈ (R ∪ Rˇ)m, (z, x) ∈ R.
It follows that (y, x) ∈ Rˇ ◦ (R ∪ Rˇ)m ◦ R. and therefore (y, x) ∈ E.
For transitivity, assume (x, y) ∈ E, (y, z) ∈ E. Then there are m, k ∈ N with (x, y) ∈ Rˇ ◦ (R ∪ Rˇ)m ◦ R. (y, z) ∈ Rˇ ◦ (R ∪ Rˇ)k ◦ R. It follows that (x, z) ∈ Rˇ ◦ (R ∪ Rˇ)m+k+2 ◦ R, and therefore (x, z) ∈ E.
Euclideanness: any transitive and symmetric relation is euclidean.
Give the euclidean closure of the relation {(1, 2),(2, 3)}.
the relation {(1, 2),(2, 2),(2, 3),(3, 2),(3, 3)}.
A partition P of a set A is a set of subsets of A with the following properties:
(a) every member of P is non-empty.
(b) every element of A belongs to some member of P.
(c) different members of P are disjoint.
If R is an equivalence relation on A and a ∈ A then |a|R, the R-class of a, is the set
{b ∈ A | bRa}. Show that the set of R-classes
{|a|R | a ∈ A}
of an equivalence relation R on A forms a partition of A.
We have to check the three properties of partitions.
Since R is a reflexive relation on A, we have that for each a ∈ A it holds that a ∈ |a|R. This takes care of (a) and (b).
Let |a|R and |b|R be two R-classes, and assume that they are not disjoint. Then we have c ∈ |a|R ∩ |b|R.
This means that we have both aRc and bRc. Since R is symmetric, we have cRb, and by transitivity of R, aRb, and again by symmetry of R, bRa.
We can show now that |a|R = |b|R, as follows:
Assume d ∈ |a|R. Then dRa. From this and aRb, by transitivity of R, dRb, i.e., d ∈ |b|R. This shows: |a|R ⊆ |b|R.
Assume d ∈ |b|R. Then dRb. From this and bRa, by transitivity of R, dRa, i.e., d ∈ |a|R. This shows: |b|R ⊆ |a|R.
So if two R-classes |a|R and |b|R are not disjoint, then they are in fact equal. This takes care of (c).
Prove that R ∪ Rˇ is the symmetric closure of R
Clearly, R ∪ Rˇ is symmetric, and R ⊆ R ∪ Rˇ.
Let S be any symmetric relation that includes R. By symmetry of S and by the fact that R ⊆ S it follows that Rˇ ⊆ S. Thus R ∪ Rˇ ⊆ S.
Let R be a binary relation on a set A. Prove that R∪{(x, x) | x ∈ A} is the reflexive closure of R.
Let I = {(x, x) | x ∈ A}. It is clear that R ∪ I is reflexive, and that
R ⊆ R ∪ I.
To show that R ∪ I is the smallest relation with these two properties, suppose S is reflexive and R ⊆ S. Then by reflexivity of S, I ⊆ S. It follows that R ∪ I ⊆ S.
