Proofs in Propositional Calculus

Question

$X \simeq Y$ reads as $X$ is equivalent to $Y$

If $X \simeq Y$, iff $X \leftrightarrow Y$ is a tautology.

Now given $X_1 \simeq X_2$, how do I prove,

1. $\tilde X_1 \simeq \tilde X_2$
2. $X_1 \cap Y\simeq X_2 \cap Y$
3. $X_1 \cup Y\simeq X_2 \cup Y$
4. $X_1 \rightarrow Y\simeq X_2 \rightarrow Y$

I know that I can write an algebraic proof by rewriting, $X \leftrightarrow Y$ as $( \tilde X \cup Y) \cap (\tilde Y \cup X)$, but is there a purely logical proof.

Update: I figured the solution for $(1)$ and it is. Is that a right proof?

if $X \rightarrow Y$ is a tautology $(X \rightarrow Y)\cap (Y \rightarrow X)$ is a tautology.

And $X \rightarrow Y$ is same as $\tilde Y \rightarrow \tilde X$. Rewriting the equation in $(1)$ proves it.

The Axioms that are available are the basic axioms of Propositional Calculus

1. Either $X$ or $\tilde X$ is true
2. If $X,Y$ is true, then so is $X\cap Y$ is true
3. If either $X$ or $Y$ is true, then $X\cup Y$ is true
4. If $X$ is not true or $Y$ is true, then $X\rightarrow Y$ is true

There was a mistake and I had confused between $\cup$ and $\cap$. Apologies. Thanks again

Answer 1

Once you are asking for proofs in propositional calculus, I will assume that the interpretation that you have in mind for the usual set-theoretic symbols '$\cap$' '$\cup$' and '$\overline{}$' are respectively standard propositional conjunction, disjunction and negation logical connectives. In this case we have the following proofs.

Let (i) $X_1 \simeq X_2$ and (ii) $\phi \simeq \psi \leftrightarrow (\phi \leftrightarrow \psi)$:

1. Proof of $\tilde X_1 \simeq \tilde X_2$: By our assumptions $X_1 \simeq X_2 \leftrightarrow (X_1 \leftrightarrow X_2)$ holds as an instance of (ii), and we have that $X_1 \leftrightarrow X_2$ holds too. Now $\tilde X_1 \simeq \tilde X_2$ follows from $\tilde X_1 \leftrightarrow \tilde X_2$ and the propositional theorem $(\phi \leftrightarrow \psi) \leftrightarrow (\neg \phi \leftrightarrow \neg \psi)$.

2. Proof of $X_1 \cap Y\simeq X_2 \cap Y$: First derive the biconditional, then apply (ii) to get your equivalence symbol: ($\rightarrow$) Let $X_1 \cap Y$. Then we conclude that $X_1$ holds and $Y$ holds. By (i) we have that $X_2$ holds too. But then we have derived $X_2 \cap Y$. ($\leftarrow$) Similar.

3. Proof of $X_1 \cup Y\simeq X_2 \cup Y$: First derive the biconditional, then apply (ii) to get your equivalence symbol: ($\rightarrow$) Let $X_1 \cup Y$. Suppose $X_1$. Then by (i) we conclude that $X_2$ holds too. By disjunction introduction, we derive $X_2 \cup Y$. Suppose $Y$. Again, we apply disjunction introduction to get $X_2 \cup Y$. ($\leftarrow$) Similar.

4. Proof of $X_1 \rightarrow Y\simeq X_2 \rightarrow Y$: First derive the biconditional, then apply (ii) to get your equivalence symbol: ($\rightarrow$) Let $X_1 \rightarrow Y$. Suppose $X_2$. Now by (i) we derive $X_1$, which gives us $Y$. This shows that $X_2 \rightarrow Y$. ($\leftarrow$) Similar.

Answer 2

A. $X_1 \simeq X_2$ is given. We also have that

B. $X_1 \simeq X_1$ also. Thus by replacing $X_1$ with $\tilde X_1$, ($X_1 \cap Y$), ($X_1 \cup Y$), and ($X_1 \rightarrow Y$) in B. we obtain:

1. $\tilde X_1 \simeq \tilde X_1$
2. ($X_1 \cap Y)\simeq (X_1 \cap Y)$
3. $(X_1 \cup Y)\simeq (X_1 \cup Y)$
4. $(X_1 \rightarrow Y)\simeq (X_1 \rightarrow Y)$.

Then since we have A., we can replace each instance of $X_1$ in 1. through 4 yielding

1.' $\tilde X_1 \simeq \tilde X_2$

2.' $(X_1 \cap Y)\simeq (X_2 \cap Y)$

3.' $(X_1 \cup Y)\simeq (X_2 \cup Y)$

4.' $(X_1 \rightarrow Y)\simeq (X_2 \rightarrow Y)$

as desired.