EDB — 05Z

[05Z]We want to rewrite the tautologies seen in [00N]↺↻ in the form of set relations.

Let \(X\) be a set and let \(𝛼,𝛽,𝛾⊆ X\) be subsets. Let \(x∈ X\). If we define \(A=(x∈ 𝛼)\), \(B=(x∈ 𝛽)\), \(C=(x∈ 𝛾)\) in the tautologies, we can then rewrite each tautology as a formula between sets \(𝛼,𝛽,𝛾,X,∅\), that use connectives \(=,∩,∪\) and the complement.

Surprisingly, rewriting can be done algorithmically and in a purely syntactic manner. Pick a tautology seen in [00N]↺↻. In the following \(𝜑,𝜓\) indicate subparts of tautology that are well-formed formulas.

• Replace \(((𝜑) ⇒ (𝜓))\) with \(((¬(𝜑)) ∨ (𝜓))\) (you will get another tautology).

• Then syntactically replace \(¬ (𝜑)\) with \((𝜑)^ c\), \(∨\) with \(∪\) and \(∧\) with \(∩\); replace \(A\) with \(𝛼\), \(B\) with \(𝛽\), \(C\) with \(𝛾\), \(V\) with \(X\), and \(F\) with \(∅\).

• Finally, if the formula contains at least one ”\(\iff \)”, transform them all in ”\(=\)”; otherwise add ”\(=X\)” at the end.

Check that this ”algorithm” really works!