4.6: Counterexamples (reprise)

We have been discussing proofs in this chapter, but you should keep in mind that counterexamples are also an important part of logic:

To show that a deduction is valid, provide a proof.
To show that a deduction is not valid, provide a counterexample.

Example \(4.6.1\).

Show that the following deduction is not valid: \[\exists x,(x \in A), \quad \therefore \forall x,(x \in A).\]

Scratchwork. To get the idea of what is going on, it may be helpful to translate the deduction into English. For example, we could use the symbolization key

\(\mathcal{U}\): things on the kitchen table

\(A\): applies on the kitchen table

In this setting, the deduction becomes:

There is an apple on the kitchen table. .˙. Everything on the kitchen table is an apple.

This deduction is obviously not valid: it is easy to imagine a situation in which one thing on the kitchen table is an apple, but something else on the kitchen table is not an apple.

To find the official solution, we will do something analogous, but using the notation of First-Order Logic, instead of talking about apples and tabletops. In order to construct a counterexample, we want the hypothesis of the deduction to be true and the conclusion to be false.

• To make the hypothesis \(\exists x,(x \in A)\) true, we need something to be an element of \(A\). For example, we could let \(1 \in A\).
• To make the the conclusion \(\forall x,(x \in A)\) false, we want its negation to be true: we want \(\exists x,(x \notin A)\) to be true. For example, we could arrange that \(2 \notin A \text {. }\).

To satisfy the above two conditions, we let \(A =\{1\}\). Since 1 and 2 are the only elements mentioned in the discussion, we can let \(\mathcal{U}=\{1,2\}\). This results in the counterexample we were hoping to find.

Solution

We provide a counterexample. Let \[\mathcal{U}=\{1,2\} \text { and } A=\{1\}\]
Then: \[1 \in A \text { is true, so } \exists x,(x \in A) \text { is true, so the hypothesis is true, }\]
but \[2 \notin A, \text { so } \forall x,(x \in A) \text { is false, so the conclusion is false. }\]
Since we have a situation in which the hypothesis is true, but the conclusion is false, the deduction is not valid.

Example \(4.6.2\).

Show that the following deduction is not valid:

Hypotheses:

1. \(\forall x,((x \in A) \vee(x \in B))\)
2. \(A \neq \varnothing\)
3. \(B \neq \varnothing\)

Conclusion: \(\exists x,((x \in A) \&(x \in B)) .\)

Scratchwork. In order to construct a counterexample, we want all of the hypotheses of the deduction to be true and the negation of the conclusion to be true. The negation of the conclusion is \[\forall x,((x \notin A) \vee(x \notin B)) ,\]
which is logically equivalent to \(4.6.3\) \[\forall x,((x \in A) \Rightarrow(x \notin B))\]
Now:

• To make Hypothesis 2 true, we may let \(1 \in A\).
• To make Hypothesis 3 true, we must put something in the set \(B\). However, it is important to note that (\(4.6.3\)) tells us \(1 \notin B\), so we must put something else into \(B\). For example, we may let \(2 \in B\).
• Now, after \(A\) and \(B\) have been constructed, we can make Hypothesis 1 true by letting \(\mathcal{U} = A \cup B\).

To satisfy all three of these conditions, we may let \(A=\{1\}, B=\{2\}, \text { and } \mathcal{U}=A \cup B=\{1,2\}\).

Solution

We provide a counterexample. Let \[\mathcal{U}=\{1,2\}, \quad A=\{1\}, \quad \text { and } \quad B=\{2\}\]
Then:

1. We have
   • \(1 \in A\) is true, so \((1 \in A) \vee(1 \in B)\) is true, and
   • \(2 \in B\) is true, so \((2 \in A) \vee(2 \in B)\) is true.
     Since 1 and 2 are the only elements of \(\mathcal{U}\), this implies, for every \(x\), that \((x \in A) \vee(x \in B)\) is true. So Hypothesis 1 is true.
2. \(1 \in A\), so \(A \neq \varnothing\). Hence, Hypothesis 2 is true.
3. \(2 \in B\), so \(B \neq \varnothing\). Hence, Hypothesis 3 is true.

However:

• \(1 \notin B\), so \((1 \in A) \& (1 \in B)\) is false, and
• \(2 \notin A\), so \((2 \in A) \&(2 \in B)\) is false.

Since 1 and 2 are the only elements of \(\mathcal{U}\), this implies there is no \(x\) for which the assertion \((x \in A) \&(x \in B)\) is true. Hence, the assertion \(\exists x,((x \in A) \&(x \in B))\) is false; in other words, the conclusion of the deduction is false. Since we have a situation in which the hypothesis is true, but the conclusion is false, the deduction is not valid.

Example \(4.6.4\).

Explain how you know the following deduction is not valid: \[X \cap Y \subset D, \quad \therefore X \subset Y \cup D .\]

Solution

We provide a counterexample. Let \(X=\{1\}, Y=\{2\}, \text { and } D=\{3\}\). Then \(X \cap Y=\{1\} \cap\{2\}=\varnothing\), so \(X \cap Y \subset D\), because the empty set is a subset of every set. This means the hypothesis is true.

However, \(Y \cup D=\{2\} \cup\{3\}=\{2,3\} .\). Therefore \[1 \in\{1\}=X \text { and } 1 \notin\{2,3\}=Y \cup D, \text { so } X \not \subset Y \cup D .\]
This means the conclusion is false.

Since we have a situation in which the hypothesis is true, but the conclusion is false, the deduction is not valid.

Exercise \(4.6.5\).

Explain how you know that each of the following deductions is not valid.

1. \(\exists x,(x \in A), \quad \exists x,(x \in B), \quad \therefore \exists x,((x \in A) \&(x \in B))\)
2. \(\forall a \in A, \exists b \in B,(a \neq b), \quad A \neq \varnothing, \quad \therefore \forall b \in B, \exists a \in A,(a \neq b)\)
3. \(A \neq B, \therefore A \cup B \neq A\)
4. \(\forall x \in A,(x \notin B), \quad \forall x \in B,(x \notin A), \therefore A \neq B \text {. }\)

Exercise \(4.6.6\).

Explain how you know that each of these deductions is not valid.

1. \(A \cup B \subset E \cup F, \quad \therefore A \cap B \subset E \cap F\)
2. \(A \subset B, X \subset Y, \quad \therefore A \backslash X \subset B \backslash Y\)
3. \(A \cap B \neq \varnothing, B \subset C, \quad \therefore A \subset C\)
4. \(\exists x,((x \in P) \&(x \notin Q)), \quad \therefore \forall x,((x \in P) \Rightarrow(x \notin Q))\)
5. \(\forall x \in X,(x R x), \quad \therefore \forall x_{1} \in X, \forall x_{2} \in X,\left(\left(x_{1} R x_{2}\right) \Rightarrow\left(x_{2} R x_{1}\right)\right)\)

Exercise \(4.6.7\).

Determine whether each of the following deductions is valid, and justify your answer by giving a proof or a counterexample.

1. \(\exists u \in U,(u \notin V), \quad \therefore \forall u \in U,(u \notin V)\)
2. \(\forall x,((x \in S) \Rightarrow(1 \in T)), \quad S \neq \varnothing, \quad \therefore 1 \in T\)
3. \(\forall a \in A,(a \in B), \quad \forall b \in B,(b \in C), \quad \therefore \forall a \in A,(a \in C) .\)
4. \(D \cup E \neq \varnothing, \quad D \subset F, \quad \therefore D \cap F \neq \varnothing\)
5. \(\forall a_{1} \in A, \forall a_{2} \in A,\left(\left(a_{1} R a_{2}\right) \vee\left(a_{2} R a_{1}\right)\right), \quad 2 \in A, \quad \therefore 2 R 2 .\)