$\alpha \to\beta$ is valid, where $\alpha$, $\beta$ share no common atomic proposition; then $\alpha$ is unsatisfiable or $\beta$ is valid, or both

Question

Assume $\alpha\to\beta$ is valid such that $\alpha$ and $\beta$ do not share a common atomic proposition. Show that either $\alpha$ is unsatisfiable or $\beta$ is valid (or both). Show that the assumption about not sharing atomic propositions is necessary.

Looking at the question it feels obvious because when $\alpha$ is unsatisfiable we don't need to check for $\beta$ because the expression is always valid. Similarly if $\beta$ is valid then we don't need to check what $\alpha$ and expression will be always valid. For proving it two techniques comes to mind. First being Induction: The base step is easy to prove for two atomic propositions but how do I prove the statement using inductive step? Particularly, how do I use the "not sharing atomic propositions condition"? The other technique that I thought of using was Frege's Propositional calculus, but again I am getting stuck in the same part.

Answer 1

Edit: I released I misread the problem and have revised my answer in light of that.

Consider the example in Mauro’s comment: $p\rightarrow p$. What I (and presumably you) thought was “oh, either p is true or it’s false. In the former case the second clause is true and in the later case the first clause is false. So the result holds for this statement.”

The issue with this reasoning is that the problem asks about validity which is different from truth. Consider $x > 7$. For some $x$ it is true and for other $x$ it is not true. Valid means that the statement is tautological, that is, it’s true for all $x$. Invalid means that the statement is contradictory, that is, it’s true for no $x$.

So now, let’s get back to your problem. Induction seems like a pretty good bet here. The base case is easy. $\alpha\rightarrow\beta$ is valid if and only if there is a deduction from $\alpha$ to $\beta$. However, if we have both $\alpha$ and $\beta$ as atomic symbols, there is only three ways that can happen

1. $\alpha$ is a invalid (proof by explosion)
2. $\beta$ is a valid (since the empty set proves all tautologies)
3. $\alpha$ and $\beta$ are the same statement (since $p\rightarrow p$ is a tautology)

Notice that they key idea here is that two distinct $\alpha$ and $\beta$ “can’t interact” if they are two different atomic sentences. The first two items in my list proves $\alpha\rightarrow\beta$ while only appealing to one of them, and the third requires that $\alpha$ and $\beta$ be the same sentence.

For the inductive step, the key again is this idea of non-interacting. Given a sentence $\alpha’$ of length $n$, we can write it as $\gamma C\delta$ where $\gamma$ has length $n-1$, $C$ is a logical combiner, and $\delta$ is an atomic sentence. By breaking it up like this, you can then do casework based on the combiner function.

It will likely make the inductive step easy to break this into a double induction. Fix the length of the predicate and induct on the length of the consequent, then fix the length of the consequent and induct on the length of the predicate.

Answer 2

Hint

Assume that $\alpha$ is satisfiable, and prove that $\beta$ must be valid.

$\alpha$ satisfiable means that, for some truth assignment $v$ for the atomic propositions of $\alpha$, we have : $v(\alpha)= \text T$.

Now, show that we must extend $v$ to the atomic propositions of $\beta$ such that $v(\beta)= \text T$ : here we need the proviso.