Logic Inference Challenge

Question

I read some logic course recently, would you please anyone say my inference is True?

$\forall x S(x) \to \exists y(R(y)) \Rightarrow \forall x \exists y(S(x) \to R(y))$.

Answer 1

Before we talk about the validity of the formula, we must define a notion of the validity. In the case of propositional logic, a given formula $\varphi$ is valid iff $\varphi$ is true for each truth assignment.

But then, how to define the notion of validity in predicate logic? Unlike propositional logic, predicate logic has quantifiers so we do not use the definition of validity in propositional logic just as it is. So, we use structures to define that. That is, validity of a formula $\varphi$ of predicate logic is defined like as: $\varphi$ is valid iff $\varphi$ is true in each structure $\mathfrak{A}$.

Therefore, if we want to refute the formula $\varphi$, it is sufficient to find a structure $\mathfrak{A}$ which makes $\varphi$ false. If the formula $$[∀xS(x)→∃yR(y)]→[∀x∃y(S(x)→R(y))]$$ is not valid, then there is a structure $\mathfrak{A}$ satisfies the negation of above formula. (Note that if $\varphi$ has no free variables, then $\varphi$ is true or false in a structure.)

I will propose the structure satisfies the negation of this formula. Before suggest it, we take notice that $\lnot [[∀xS(x)→∃yR(y)]→[∀x∃y(S(x)→R(y))]]$ is true in $\mathfrak{A}$ if and only if

1. $\forall x S(x)\to\exists y R(y)$ is true in $\mathfrak{A}$ and

2. $∀x∃y(S(x)→R(y))$ is false in $\mathfrak{A}$.

Let define

1. underlying set of $\mathfrak{A}$ is $\{1,2\}$,

2. $S(x)$ holds iff $x=1$ and

3. no $x$ satisfies $R(x)$.

Since both $\forall x S(x)$ and $\exists y R(y)$ are false so $\forall x S(x)\to\exists y R(y)$ is true in $\mathfrak{A}$. On the other hand, if $∀x∃y(S(x)→R(y))$ is true then $\exists y S(1)\to R(y)$ is also true. Since $S(1)$ is true, there is $y$ that is satisfying $R(y)$. It contradicts the definition of $R$ so $∀x∃y(S(x)→R(y))$ is false in $\mathfrak{A}$.

Answer 2

Tetori gave a great technical answer. I just wanted to contribute an alternative approach:

In $[∀xS(x)→∃yR(y)]→[∀x∃y(S(x)→R(y))]$, the antecedent is saying:

"If all x are Sx then there is y that is Ry". The consequent is saying:"If an x is Sx, then a y is Ry".

Note that the antecedent is a sub-theorem of the consequent: In the case where all x are Sx, we have the repeated deduction that there is a y that is Ry. Thus, the consequent is much less restricted/more general than the antecedent. Hence, you are trying to say that a specific theorem implies a more general theorem, which is backwards.