Formal Proofs of Logic

Question

I need to give Fitch-style formal proofs for the following:

1) Premises:

1. ∀x∀y∀z((R(x, y) ∧ R(y, z)) → R(x, z))
2. ∀x∀y(R(x, y) → R(y, x))

To prove: ∀x∀y(R(x, y) → R(x, x))

2) Premises:

1. ∀x(P(x) → Q(a))
2. ∃x(P(x) ∧ Q(x))

To prove: Q(a)

For question 1 I tried something, but it became one big mess with a lot of subproofs. The amount of different variables is throwing me a bit off. For question 2 I can't even see why the goal sentence follows from the premises.

Appreciating all input.

Answer 1

Without delving into proper Fitchean formalism, you can proceed as follows.

1)

The premises say that $R$ is transitive and $R$ is symmetric. The conclusion says that (for all $x$) if $x$ bears $R$ to anything than it bears $R$ to itself.

• Suppose $x, y$ are such that $R(x,y)$
• By 2., $R(x,y) \to R(y,x)$, hence modus ponens applied to this with the previous step yields:
• $R(y,x)$
• By 1., $R(x,y) \wedge R(y,x) \to R(x,x)$, so
• $R(x,x)$

Because $x,y$ were arbitrary,

• $\forall x R(x,x)$

2)

Given 1. and 2.

• By 2. there is something $b$ such that $P(b) \wedge Q(b)$, so
• $P(b)$
• In 1. taking $x = b$, we get $P(b) \to Q(a)$; thus, by modus ponens,
• $Q(a)$

Answer 2

1) Premises:

1. ∀x∀y∀z((R(x, y) ∧ R(y, z)) → R(x, z))
2. ∀x∀y(R(x, y) → R(y, x))

To prove: ∀x∀y(R(x, y) → R(x, x))

I tried something, but it became one big mess with a lot of subproofs. The amount of different variables is throwing me a bit off.

Hint: $\forall x\forall y\forall z \; P(x,y,z) \vdash P(a,b,a)$ by universal instantiation. They don't have to be three arbitrary variables, you can weaken it as needed.

Essentially: apply universal instantiation on the premises to obtain predicates of two arbitrary witnesses, $a,b$, then demonstrate using these results that assuming $R(a,b)$ concludes $R(a,a)$ by modus ponens (twice), and then apply universal generalisation to that result.

---

2) Premises:

1. ∀x(P(x) → Q(a))
2. ∃x(P(x) ∧ Q(x))

To prove: Q(a)

Use existential generalisation then conjunctive elimination on the second premise to obtain the witness $P(c)$, then use universal generalisation on the first premise to show $P(c)\to Q(a)$ and put them together using modus ponens to conclude $Q(a)$.

Answer 3

Using hints from the other answers here are Fitch-style proofs in a proof checker to show the details:

---

Kevin Klement's JavaScript/PHP Fitch-style natural deduction proof editor and checker http://proofs.openlogicproject.org/