Help to prove that $ \Gamma \equiv\Gamma \setminus \{P\mid \models P\} $

27 Views Asked by At

Im supposed to prove that
$$ \Gamma \equiv \Gamma \setminus \{P\mid \models P\} $$
where $\Gamma$ is set of propositions and $\{P\mid \models P\}$ is a set of tautologies.

My thoughts were that because all the subgroups $\Gamma' \subseteq \Gamma$ have the same model, the equivalence would hold without the tautologies on the RHS set.

But for example if $\Gamma = \{ \neg A\lor A \}$ (which is a tautology), then the equivalence would become $\{ \neg A\lor A \}\equiv \emptyset $ which is incorrect?

Think I have misunderstood a bit. Help will be appreciated.

1

There are 1 best solutions below

0
On

all the subgroups $\Gamma'\subseteq\Gamma$ have the same model

First of all, I think you mean "subsets." More importantly, I don't know what this means - certainly in general $\Gamma$ will have subsets with strictly more models. (Remember, losing axioms means possibly gaining models.)

the equivalence would become $\{\neg A\vee A\}\equiv\emptyset$ which is incorrect

Actually, that's correct! Let's think about why. The expression "$\Sigma\equiv \Pi$" means "the models of $\Sigma$ are exactly the models of $\Pi$." Now we have:

  • The models of $\emptyset$ are, well, all the structures: "satisfies every sentence in $\emptyset$" is a vacuous condition, so every structure satisfies $\emptyset$.

  • Now $\{\neg A\vee A\}$ looks a bit more complicated, but I claim that since $\neg A\vee A$ is a tautology, every structure satisfies it. Think about what it means to be a tautology ...

Once you understand this example, I think you'll see how to solve the problem.