How to define membership relation from subset relation and power set operation In my talk at 2018 Chinese Mathematical Logic Conference, I asked if $$(V,\subset,P)$$ is epsilon-complete, namely if the membership relation can be recovered in the reduct. Professor Joseph S. Miller approached to me during the dinner and pointed out that it is epsilon-complete. Let me explain how.

Theorem

Let $$(V,\in)$$ be a structure of set theory, $$(V,\subset,P)$$ is the structure of the inclusion relation and the power set operation, which are defined in $$(V,\in)$$ as usual. Then $$\in$$ is definable in $$(V,\subset,P)$$.

Proof.

Fix a set $$x$$. Define $$y$$ to be the $$\subset$$-least such that

$\forall z \big((z\subset x\wedge z\neq x)\rightarrow P(z)\subset y\big).$

Actually, $$y=P(x)-\{x\}$$, so $$\{x\}= P(x) – y$$. Since set difference can be defined from subset relation and $$(V,\subset,\{x\})$$ can define $$\in$$, we are done.

$$\Box$$

Here is another argument figured out by Jialiang He and me after we heard Professor Miller’s Claim.

Proof.
Since $$\in$$ can be defined in $$(V,\subset,\bigcup)$$ (see the slides). Fix a set $$A$$, it suffices to show that we can define $$\bigcup A$$ from $$\subset$$ and $$P$$.

Let $$B$$ be the $$\subset$$-least set such that there is $$c$$, $$B=P(c)$$ and $$A\subset B$$. Note that
$\bigcap\big\{P(d)\bigm|A\subset P(d)\big\}= P\big(\bigcap\big\{d\bigm|A\subset P(d)\big\}\big).$
Therefore, $$B$$ is well-defined. Next, we show that
$\bigcap\big\{d\bigm|A\subset P(d)\big\}=\bigcup A.$
Clearly, $$A\subset P(\bigcup A)$$. This proves the direction from left to right. For the other direction, if $$x$$ is in an element of $$A$$, then it is in an element of $$P(d)$$ given $$A\subset P(d)$$, i.e. it is an element of such $$d$$.

Therefore $$\bigcup A$$ is the unique set whose power set is $$B$$.

$$\Box$$

Modal Logic 2018

Lecture: HGX205, M 18:30-21
Section: HGW2403, F 18:30-20

Syllabus

Exercise 01

1. Prove that $$\neg\Box(\Diamond\varphi\wedge\Diamond\neg\varphi)$$ is equivalent to $$\Box\Diamond\varphi\rightarrow\Diamond\Box\varphi$$. What you have assumed?
2. Define strategy and winning strategy for modal evaluation games. Prove Key Lemma: $$M,s\vDash\varphi$$ iff V has a winning strategy in $$G(M,s,\varphi)$$. Prove that modal evaluation games are determined, i.e. either V or F has a winning strategy.

And all exercises for Chapter 2 (see page 23, open minds)

Exercise 02

1. Let $$T$$ with root $$r$$ be the tree unraveling of some possible world model, and $$T’$$ be the tree unraveling of $$T,r$$. Show that $$T$$ and $$T’$$ are isomorphic.
2. Prove that the union of a set of bisimulations between $$M$$ and $$N$$ is a bisimulation between the two models.
3. We define the bisimulation contraction of a possible world model $$M$$ to be the “quotient model”. Prove that the relation links every world $$x$$ in $$M$$ to the equivalent class $$[x]$$ is a bisimulation between the original model and its bisimulation contraction.

And exercises for Chapter 3 (see page 35, open minds): 1 (a) (b), 2.

Exercise 03

1. Prove that modal formulas (under possible world semantics) have ‘Finite Depth Property’.

And exercises for Chapter 4 (see page 47, open minds): 1 – 3.

Exercise 04

1. Prove the principle of Replacement by Provable Equivalents: if $$\vdash\alpha\leftrightarrow\beta$$, then $$\vdash\varphi[\alpha]\leftrightarrow\varphi[\beta]$$.
2. Prove the following statements.
• “For each formula $$\varphi$$, $$\vdash\varphi$$ is equivalent to $$\vDash\varphi$$” is equivalent to “for each formula $$\varphi$$, $$\varphi$$ being consistent is equivalent to $$\varphi$$ being satisfiable”.
• “For every set of formulas $$\Sigma$$ and formula $$\varphi$$, $$\Sigma\vdash\varphi$$ is equivalent to $$\Sigma\vDash\varphi$$” is equivalent to “for every set of formulas $$\Sigma$$, $$\Sigma$$ being consistent is equivalent to $$\Sigma$$ being satisfiable”.
3. Prove that “for each formula $$\varphi$$, $$\varphi$$ being consistent is equivalent to $$\varphi$$ being satisfiable” using the finite version of Henkin model.

And exercises for Chapter 5 (see page 60, open minds): 1 – 5.

Exercise 05

Exercises for Chapter 6 (see page 69, open minds): 1 – 3.

Exercise 06

1. Show that “being equivalent to a modal formula” is not decidable for arbitrary first-order formulas.

Exercises for Chapter 7 (see page 88, open minds): 1 – 6. For exercise 2 (a) – (d), replace the existential modality E with the difference modality D. In the clause (b) of exercise 4, “completeness” should be “correctness”.

Exercise 07

1. Show that there are infinitely many non-equivalent modalities under T.
2. Show that GL + Id is inconsistent and Un proves GL.
3. Give a complete proof of the fact: In S5, Every formula is equivalent to one of modal depth $$\leq 1$$.

Exercises for Chapter 8 (see page 99, open minds): 1, 2, 4 – 6.

Exercise 08

1. Let $$\Sigma$$ be a set of modal formulas closed under substitution. Show that $(W,R,V),w\vDash\Sigma~\Leftrightarrow~ (W,R,V’),w\vDash\Sigma$ hold for any valuation $$V$$ and $$V’$$. Define a $$p$$-morphism between $$(W,R),w$$ and $$(W’,R’),w’$$ as a “functional bisimulation”, namely bisimulation regardless of valuation. Show that if there is a $$p$$-morphism between $$(W,R),w$$ and $$(W’,R’),w’$$, then for any valuation $$V$$ and $$V’$$, we have $(W,R,V),w\vDash\Sigma~\Leftrightarrow~ (W’,R’,V’),w\vDash\Sigma.$

Exercises for Chapter 9 (see page 99, open minds).

Exercise the last

Exercises for Chapter 10 and 11 (see page 117 and 125, open minds).