How to read formal proofs

Question

I'm in discrete math and I see the following notation $\forall x (P(x) \implies Q(x))$ and I read it as "for all x, P of x therefore Q of x". I'm struggling to follow proofs with this kind of notation and building proofs involving this kind of notation, I think it's because of how I read it. Am I reading it correctly, when you see this notation how do you read it to yourself? For example "a student in discrete math has not read the textbook", Everyone has passed the first exam" prove "someone who passed the first exam has not read the textbook". So I need to show there exists a person who has passed the first exam and who has not read the book. How can I interpret these sentences as functions to add to formal proof notation?

Answer 1

You are reading it correctly. Another way of phrasing it is "For all $x$, if $P(x)$ is true, then $Q(x)$ is true".

For instance, consider that $x$ can be any integer, and that $P(x)$ is the statement "$4$ divides $x$" and that $Q(x)$ is the statement "$x$ is even".

Then the statement

$$\forall x (P(x)\Rightarrow Q(x))$$

is true.

What does it say? It says that for all integers $x$, if $4$ divides $x$, then $x$ is even.

The way to prove such a statement is to start out by leting $x$ be some arbitrary integer. Then you assume that $P(x)$ is true, and from this assumption, you prove $Q(x)$. To be specific, assume that $P(x)$ is true means that you assume that $x$ is some integer divisible by $4$. Is $x$ then even? (i.e. is $Q(x)$ true?)

It is, because if $x$ is divisible by $4$, then $x=4y$ for some integer $y$, and so $x = 2(2y)$, or $x=2z$, where $z=2y$. This means that $2$ divides $x$, which is the definition of being even.

In total, I have proven that if $P(x)$ is true, then $Q(x)$ is also true, no matter what $x$ I chose.

Answer 2

For example "a student in discrete math has not read the textbook", Everyone has passed the first exam" prove "someone who passed the first exam has not read the textbook".

Let $Q(x)$ mean, "$x$ has read the textbook." Then the first sentence is $\exists x\;\neg Q(x)$

Let $P(x)$ mean "$x$ has passed the first exam". Then the second sentence is $\forall x\;P(x)$

The last sentence is then $\exists x\;\big(P(x)\wedge \neg Q(x)\big)$ . We can show the first two entail the third in a variety of ways, including something like:

$$\begin{array}{l|l:l} 1. & \exists x\;\neg Q(x) & \text{Premise} \\ 2. & \forall x\; P(x) & \text{Premise} \\ 3. &\neg Q(c) & 1,\text{ Existential Instantiation to witness }c \\ 4. & P(c) & 2,\text{ Universal Instantiation at witness }c \\ 5. & P(c)\wedge\neg Q(c) & 3,4,\text{ Conjunction Introduction} \\ 6. & \exists x\; \big(P(x)\wedge \neg Q(x)\big) & 5, \text{ Existential Introduction at witness }c \\ \Box \end{array}$$