Set Theory and Formal Logic

Set Notation and Definitions

Sets are one of the basic ways mathematicians organize information. A set is a collection of objects, called elements or members. In mathematics, sets help us describe groups of numbers, letters, shapes, or any other objects in a precise way.

In this lesson, you will learn how to write sets using proper notation, how to describe sets in two common forms, and how to identify important types of sets such as finite sets, infinite sets, the universal set, and the empty set.

1. Basic Set Notation

Sets are usually named with capital letters such as \(A\), \(B\), or \(S\). The elements of a set are written inside curly braces \(\{\}\).

For example, if set \(A\) contains the numbers 1, 3, and 5, we write:

\(A = \{1,3,5\}\)

If an object belongs to a set, we use the symbol \(\in\), which means “is an element of.” For example:

\(3 \in A\)

If an object does not belong to a set, we use \(\notin\). For example:

\(2 \notin A\)

Important idea: In a set, the order of elements does not matter, and repeated elements are not listed more than once.

• \(\{1,2,3\} = \{3,2,1\}\)
• \(\{1,1,2,2,3\} = \{1,2,3\}\)

2. Ways to Describe a Set

There are two main ways you will write sets in this topic:

• Roster method
• Set-builder notation

Roster Method

In the roster method, you list all the elements of the set inside curly braces.

Example:

\(B = \{2,4,6,8\}\)

This tells us exactly which elements are in the set.

The roster method works best when the set is small or when its elements are easy to list.

Set-Builder Notation

In set-builder notation, instead of listing every element, you describe a rule that tells which elements belong to the set.

A general form is:

$$\{x \mid \text{x satisfies a certain rule}\}$$

The symbol \(\mid\) means “such that.” Sometimes a colon is used instead, but the meaning is the same.

Example:

$$\{x \mid x \text{ is an even number and } 2 \le x \le 8\}$$

This set can also be written in roster form as \(\{2,4,6,8\}\).

3. Finite and Infinite Sets

A finite set is a set with a limited number of elements. You can count how many elements it has, even if there are many.

Examples of finite sets:

• \(\{a,e,i,o,u\}\)
• \(\{1,2,3,4,5\}\)
• Months of the year

An infinite set is a set that continues without end. Its elements cannot all be completely listed.

Examples of infinite sets:

• The natural numbers: \(\{1,2,3,4,5,\dots\}\)
• All even numbers: \(\{2,4,6,8,\dots\}\)
• All integers: \(\{\dots,-2,-1,0,1,2,\dots\}\)

When writing an infinite set in roster form, we often use dots \(\dots\) to show that the pattern continues.

4. Universal Set

The universal set is the set of all elements being considered in a particular discussion. It is often given the symbol \(U\).

The universal set depends on context. For example, if we are talking about whole numbers from 1 to 10, then the universal set might be:

\(U = \{1,2,3,4,5,6,7,8,9,10\}\)

If we are discussing letters in the English alphabet, then the universal set would be all 26 letters.

This means that when you describe a set, you are usually choosing elements from the universal set.

For example, if

\(U = \{1,2,3,4,5,6,7,8,9,10\}\)

then a set \(C\) of multiples of 3 in \(U\) is:

\(C = \{3,6,9\}\)

5. Empty Set

The empty set is the set with no elements. It is written as \(\{\}\) or \(\varnothing\).

Example:

Suppose \(D\) is the set of odd numbers between 2 and 4. There are no odd whole numbers between 2 and 4, so:

\(D = \varnothing\)

It is important to understand that the empty set is still a set. It just has zero elements.

Common mistake: Do not confuse \(\varnothing\) with \(\{\varnothing\}\).

• \(\varnothing\) means no elements
• \(\{\varnothing\}\) means a set containing one element, and that element is the empty set

6. Translating Between Roster and Set-Builder Notation

Being able to move between these two forms is an important skill.

If a set is given in roster form, look for the pattern or rule. If it is given in set-builder notation, determine which elements satisfy the rule.

Worked Example 1: Write a set in roster form

Write the set of whole numbers less than 6 in roster form.

Step 1: Identify the numbers that fit the description.

Whole numbers less than 6 are \(0,1,2,3,4,5\).

Answer:

\(\{0,1,2,3,4,5\}\)

This is a finite set because it has only 6 elements.

Worked Example 2: Write a set in set-builder notation

Write the set \(\{2,4,6,8,10\}\) in set-builder notation.

Step 1: Look for a pattern.

These are even numbers from 2 to 10.

Answer:

$$\{x \mid x \text{ is an even whole number and } 2 \le x \le 10\}$$

This set is also finite.

Worked Example 3: Identify the type of set

Consider the set

\(E = \{5,10,15,20,25,\dots\}\)

Step 1: Notice the dots at the end.

The pattern continues by adding 5 each time.

Step 2: Decide whether it ends.

It does not end, so it has infinitely many elements.

Answer: \(E\) is an infinite set.

In set-builder notation, it could be written as:

$$E = \{x \mid x \text{ is a positive multiple of } 5\}$$

Worked Example 4: Find an empty set

Let \(U = \{1,2,3,4,5,6,7,8\}\). Write the set of numbers in \(U\) that are greater than 10.

Step 1: Check whether any elements in \(U\) are greater than 10.

There are none.

Answer:

\(\varnothing\)

This is the empty set.

7. Key Symbols to Know

• \(\{ \}\): used to write a set
• \(\in\): is an element of
• \(\notin\): is not an element of
• \(\varnothing\): empty set
• \(U\): universal set
• \(\mid\): such that, used in set-builder notation

8. Tips for Success

• Use curly braces, not parentheses, when writing sets.
• Do not repeat elements in a set.
• Remember that order does not matter in a set.
• Use roster form when the elements are easy to list.
• Use set-builder notation when the set follows a clear rule or is too large to list fully.
• Always pay attention to the universal set if one is given.

Summary

A set is a collection of elements written inside curly braces. Sets can be written using the roster method, where elements are listed, or set-builder notation, where a rule describes the elements. A finite set has a limited number of elements, while an infinite set continues without end. The universal set contains all objects under discussion, and the empty set contains no elements.

Set Inclusion and Power Sets

In set theory, a set is a collection of distinct objects, called elements. We often use capital letters such as \(A\), \(B\), and \(C\) to name sets, and lowercase letters such as \(x\) to represent elements.

This lesson focuses on two important ideas: set inclusion and power sets. These ideas help us compare sets, count subsets, and understand how sets are built from smaller parts.

By the end of this lesson, you should be able to:

• decide whether one set is a subset of another,
• tell the difference between a subset and a proper subset,
• identify supersets,
• find the number of subsets of a set, and
• write the power set of a small set.

1. Set Inclusion

Set inclusion tells us whether all elements of one set are contained in another set.

If every element of set \(A\) is also an element of set \(B\), then \(A\) is called a subset of \(B\). We write:

$$A \subseteq B$$

This means:

$$\text{If } x \in A, \text{ then } x \in B$$

For example, if \(A = \{1,2\}\) and \(B = \{1,2,3,4\}\), then every element of \(A\) is in \(B\). So:

$$\{1,2\} \subseteq \{1,2,3,4\}$$

Important: To check whether \(A \subseteq B\), do not ask whether the sets are equal in size. Only ask: Is every element of \(A\) in \(B\)?

2. Proper Subsets

A set \(A\) is a proper subset of \(B\) if every element of \(A\) is in \(B\), but the two sets are not equal.

We write:

$$A \subset B$$

So, \(A \subset B\) means:

• \(A \subseteq B\), and
• \(A \ne B\)

For example:

$$\{1,2\} \subset \{1,2,3\}$$

This is true because \(1\) and \(2\) are both in the larger set, and the two sets are not the same.

However, if \(A = \{a,b\}\) and \(B = \{a,b\}\), then:

$$A \subseteq B \text{ is true, but } A \subset B \text{ is false}$$

This is because every set is a subset of itself, but no set is a proper subset of itself.

3. Supersets

If \(A \subseteq B\), then \(B\) is called a superset of \(A\). We write:

$$B \supseteq A$$

If \(A\) is a proper subset of \(B\), then \(B\) is a proper superset of \(A\):

$$B \supset A$$

For example, if \(A = \{2,4\}\) and \(B = \{1,2,3,4,5\}\), then:

$$A \subseteq B \quad \text{and} \quad B \supseteq A$$

4. The Empty Set and Inclusion

The empty set is the set with no elements. It is written as \(\varnothing\) or \(\{\}\).

A very important fact is:

$$\varnothing \subseteq A$$

for every set \(A\).

This is true because the empty set has no elements that could break the subset rule. Since there are no elements in \(\varnothing\), it is automatically a subset of every set.

Also, every set is a subset of itself:

$$A \subseteq A$$

These two facts are important when listing all subsets of a set.

5. Cardinality of a Set

The cardinality of a set is the number of elements in the set. We often write cardinality as \(|A|\).

For example, if \(A = \{3,5,7,9\}\), then:

$$|A| = 4$$

Remember that sets do not count repeated elements more than once. For example:

$$\{1,1,2,2,3\} = \{1,2,3\}$$

So the cardinality is:

$$|\{1,1,2,2,3\}| = 3$$

6. What Is a Power Set?

The power set of a set \(A\) is the set of all subsets of \(A\). It is written as:

$$\mathcal{P}(A)$$

This means that every subset of \(A\) becomes an element of \(\mathcal{P}(A)\).

For example, if \(A = \{1,2\}\), then the subsets of \(A\) are:

• \(\varnothing\)
• \(\{1\}\)
• \(\{2\}\)
• \(\{1,2\}\)

So the power set is:

$$\mathcal{P}(\{1,2\}) = \{\varnothing, \{1\}, \{2\}, \{1,2\}\}$$

Notice something important: the elements of a power set are themselves sets.

For example, in \(\mathcal{P}(\{1,2\})\), the element \(\{1\}\) is a set, not just the number \(1\).

7. Number of Elements in a Power Set

If a set has \(n\) elements, then its power set has:

$$2^n$$

subsets.

So if \(|A| = n\), then:

$$|\mathcal{P}(A)| = 2^n$$

Why? Because for each element of \(A\), there are two choices when forming a subset:

• include it, or
• do not include it.

If there are \(n\) elements, that gives \(2 \times 2 \times \cdots \times 2 = 2^n\) possible subsets.

For example:

• If \(|A| = 1\), then \(|\mathcal{P}(A)| = 2^1 = 2\)
• If \(|A| = 2\), then \(|\mathcal{P}(A)| = 2^2 = 4\)
• If \(|A| = 3\), then \(|\mathcal{P}(A)| = 2^3 = 8\)
• If \(|A| = 4\), then \(|\mathcal{P}(A)| = 2^4 = 16\)

8. How to List a Power Set Systematically

When listing a power set, it helps to organize subsets by size:

• the empty set,
• subsets with 1 element,
• subsets with 2 elements,
• subsets with 3 elements, and so on,
• the full set.

This makes it easier to avoid missing any subsets.

For a 3-element set \(\{a,b,c\}\), the subsets are:

• 0 elements: \(\varnothing\)
• 1 element: \(\{a\}, \{b\}, \{c\}\)
• 2 elements: \(\{a,b\}, \{a,c\}, \{b,c\}\)
• 3 elements: \(\{a,b,c\}\)

That gives 8 subsets in total, which matches \(2^3 = 8\).

Worked Example 1: Deciding Whether One Set Is a Subset of Another

Let \(A = \{2,4\}\) and \(B = \{1,2,3,4,5\}\). Determine whether \(A \subseteq B\).

Step 1: Check each element of \(A\).

• \(2 \in B\)
• \(4 \in B\)

Step 2: Since every element of \(A\) is in \(B\), we conclude:

$$A \subseteq B$$

Answer: Yes, \(A\) is a subset of \(B\).

Worked Example 2: Subset or Not a Subset?

Let \(C = \{a,c,d\}\) and \(D = \{a,b,c\}\). Is \(C \subseteq D\)?

Step 1: Check the elements of \(C\).

• \(a \in D\)
• \(c \in D\)
• \(d \notin D\)

Step 2: Since \(d\) is not in \(D\), not every element of \(C\) is in \(D\).

So:

$$C \nsubseteq D$$

Answer: No, \(C\) is not a subset of \(D\).

Worked Example 3: Writing a Power Set

Find the power set of \(A = \{x,y\}\).

Step 1: List all subsets of \(A\).

• The empty set: \(\varnothing\)
• Subsets with 1 element: \(\{x\}\), \(\{y\}\)
• Subset with 2 elements: \(\{x,y\}\)

Step 2: Put these subsets into one set.

$$\mathcal{P}(A) = \{\varnothing, \{x\}, \{y\}, \{x,y\}\}$$

Step 3: Check the number of subsets.

Since \(|A| = 2\), we expect:

$$|\mathcal{P}(A)| = 2^2 = 4$$

We found 4 subsets, so the answer is complete.

Worked Example 4: Power Set and Cardinality

Let \(B = \{1,2,3\}\). Find \(\mathcal{P}(B)\) and its cardinality.

Step 1: List subsets by size.

• 0 elements: \(\varnothing\)
• 1 element: \(\{1\}, \{2\}, \{3\}\)
• 2 elements: \(\{1,2\}, \{1,3\}, \{2,3\}\)
• 3 elements: \(\{1,2,3\}\)

Step 2: Write the power set.

$$\mathcal{P}(B) = \{\varnothing, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\}$$

Step 3: Find the cardinality.

There are 8 subsets, so:

$$|\mathcal{P}(B)| = 8$$

This also matches the formula:

$$|\mathcal{P}(B)| = 2^3 = 8$$

9. Common Mistakes to Avoid

• Confusing an element with a subset: \(1\) is not the same as \(\{1\}\).
• Forgetting the empty set: \(\varnothing\) is always a subset, so it must be in every power set.
• Forgetting the set itself: every set is a subset of itself, so the original set must be in its own power set.
• Missing subsets when listing a power set: organize by number of elements.
• Thinking order matters: \(\{1,2\} = \{2,1\}\). In sets, order does not matter.

10. Quick Check Ideas

When you are solving problems about inclusion and power sets, ask yourself these questions:

• Have I checked every element of the smaller set?
• Am I looking at elements, or at sets of elements?
• Did I include \(\varnothing\)?
• Did I include the full set?
• Does my number of subsets match \(2^n\)?

Summary

A set \(A\) is a subset of \(B\) if every element of \(A\) is also in \(B\). If \(A\) is a subset of \(B\) and \(A \ne B\), then \(A\) is a proper subset of \(B\). If \(A \subseteq B\), then \(B\) is a superset of \(A\).

The power set \(\mathcal{P}(A)\) is the set of all subsets of \(A\). If a set has \(n\) elements, then its power set has \(2^n\) elements. To list a power set correctly, include the empty set, all smaller subsets, and the full set itself.

Set Operations and De Morgan's Laws

Sets are one of the basic languages of mathematics. A set is a collection of objects, called elements. In set theory, we often compare sets, combine them, and describe relationships between them.

In this lesson, you will learn the main set operations: union, intersection, difference, and complement. You will also learn De Morgan's Laws, which help us rewrite set expressions and prove that two sets are equal.

These ideas are important because they connect directly to logic, Venn diagrams, and proof. If you can understand what each set operation means in words, the symbols become much easier to use correctly.

1. Basic set notation

If an object is in a set, we write the symbol belongs to:

$$x \in A$$

If an object is not in a set, we write:

$$x \notin A$$

Two sets are equal if they have exactly the same elements:

$$A = B$$

This means every element of \(A\) is in \(B\), and every element of \(B\) is in \(A\).

We often work inside a larger set called the universal set, written as \(U\). The universal set contains all objects being discussed in that situation.

For example, if we are talking about whole numbers from 1 to 10, then we might define

$$U = \{1,2,3,4,5,6,7,8,9,10\}$$

2. Main set operations

Union

The union of two sets \(A\) and \(B\), written \(A \cup B\), is the set of all elements that are in \(A\), or in \(B\), or in both.

$$A \cup B = \{x \mid x \in A \text{ or } x \in B\}$$

Intersection

The intersection of \(A\) and \(B\), written \(A \cap B\), is the set of all elements that are in both sets.

$$A \cap B = \{x \mid x \in A \text{ and } x \in B\}$$

Difference

The difference of \(A\) and \(B\), written \(A - B\) or sometimes \(A \setminus B\), is the set of all elements that are in \(A\) but not in \(B\).

$$A - B = \{x \mid x \in A \text{ and } x \notin B\}$$

Complement

The complement of a set \(A\), written \(A^c\) or sometimes \(A'\), is the set of all elements in the universal set that are not in \(A\).

$$A^c = \{x \in U \mid x \notin A\}$$

The complement always depends on the universal set. If the universal set changes, the complement can change too.

3. Understanding the operations in words

• Union: combine everything from both sets.
• Intersection: keep only the common elements.
• Difference: remove from the first set anything that is in the second set.
• Complement: take everything outside the set, but still inside the universal set.

These word meanings are very important. Many mistakes happen when students try to memorize symbols without connecting them to the meaning.

4. Worked Example 1: Finding unions, intersections, and differences

Let

$$A = \{1,2,3,4,5\}, \qquad B = \{3,4,5,6,7\}$$

Find \(A \cup B\), \(A \cap B\), \(A - B\), and \(B - A\).

Step 1: Find the union

The union contains all elements that appear in either set:

$$A \cup B = \{1,2,3,4,5,6,7\}$$

Step 2: Find the intersection

The intersection contains only elements in both sets:

$$A \cap B = \{3,4,5\}$$

Step 3: Find \(A - B\)

Take elements in \(A\) that are not in \(B\):

$$A - B = \{1,2\}$$

Step 4: Find \(B - A\)

Take elements in \(B\) that are not in \(A\):

$$B - A = \{6,7\}$$

Important note: Difference is not commutative. Usually, \(A - B \ne B - A\).

5. Worked Example 2: Complements using a universal set

Let

$$U = \{1,2,3,4,5,6,7,8,9,10\}$$

$$A = \{2,4,6,8,10\}, \qquad B = \{1,2,3,4,5\}$$

Find \(A^c\), \(B^c\), and \(A \cap B\).

Step 1: Find \(A^c\)

\(A\) contains the even numbers in \(U\). So the complement is everything in \(U\) that is not in \(A\):

$$A^c = \{1,3,5,7,9\}$$

Step 2: Find \(B^c\)

\(B\) contains \(1\) through \(5\). So:

$$B^c = \{6,7,8,9,10\}$$

Step 3: Find \(A \cap B\)

We want the numbers that are both even and in the set \(\{1,2,3,4,5\}\):

$$A \cap B = \{2,4\}$$

6. Venn diagram meaning

Venn diagrams are pictures that help show set relationships. Each set is usually drawn as a circle inside a rectangle representing the universal set.

• The whole area covered by two circles shows the union.
• The overlap of the circles shows the intersection.
• The part of one circle outside the other shows the difference.
• The area outside a circle but inside the rectangle shows the complement.

Even when you are not asked to draw a Venn diagram, imagining one can help you decide which operation is needed.

7. De Morgan's Laws

De Morgan's Laws tell us how complements interact with unions and intersections. These laws are very useful in simplifying set expressions and proving set equivalences.

The two laws are:

$$\left(A \cup B\right)^c = A^c \cap B^c$$

$$\left(A \cap B\right)^c = A^c \cup B^c$$

Meaning of the first law: If an element is not in \(A \cup B\), then it is not in \(A\) and also not in \(B\). So it must be in both complements.

Meaning of the second law: If an element is not in \(A \cap B\), then it is not in both sets at the same time. So it must fail to be in \(A\), or fail to be in \(B\), or both. That means it belongs to \(A^c \cup B^c\).

A simple way to remember them is:

• The complement of a union becomes an intersection of complements.
• The complement of an intersection becomes a union of complements.

8. Worked Example 3: Verifying a De Morgan's Law with actual sets

Let

$$U = \{1,2,3,4,5,6,7,8\}$$

$$A = \{1,2,3,4\}, \qquad B = \{3,4,5,6\}$$

Verify that

$$\left(A \cup B\right)^c = A^c \cap B^c$$

Step 1: Find \(A \cup B\)

$$A \cup B = \{1,2,3,4,5,6\}$$

Step 2: Find its complement

Everything in \(U\) not in \(A \cup B\) is:

$$\left(A \cup B\right)^c = \{7,8\}$$

Step 3: Find \(A^c\) and \(B^c\)

$$A^c = \{5,6,7,8\}$$

$$B^c = \{1,2,7,8\}$$

Step 4: Find the intersection of the complements

$$A^c \cap B^c = \{7,8\}$$

Since both sides give the same set, the law is verified:

$$\left(A \cup B\right)^c = A^c \cap B^c$$

9. Proving set equivalence using element reasoning

To prove two sets are equal, we usually show that any element of the first set must be in the second set, and any element of the second set must be in the first set.

This is called proving double inclusion.

For example, to prove

$$\left(A \cap B\right)^c = A^c \cup B^c$$

we can use an arbitrary element \(x\).

Proof:

Assume \(x \in (A \cap B)^c\). That means \(x \notin A \cap B\).

So \(x\) is not in both \(A\) and \(B\) at the same time. Therefore, either \(x \notin A\) or \(x \notin B\).

This means either \(x \in A^c\) or \(x \in B^c\). So:

$$x \in A^c \cup B^c$$

Now assume \(x \in A^c \cup B^c\). Then \(x \in A^c\) or \(x \in B^c\).

So \(x \notin A\) or \(x \notin B\). Therefore \(x\) cannot be in both \(A\) and \(B\) at the same time.

So:

$$x \notin A \cap B$$

which means

$$x \in (A \cap B)^c$$

Since each set is contained in the other, we conclude:

$$\left(A \cap B\right)^c = A^c \cup B^c$$

10. Worked Example 4: Simplifying a set expression

Simplify

$$\left(A \cap B\right)^c \cap A$$

Step 1: Use De Morgan's Law

$$\left(A \cap B\right)^c = A^c \cup B^c$$

So the expression becomes:

$$\left(A^c \cup B^c\right) \cap A$$

Step 2: Think about what must be true

We are looking for elements that are in \(A\), and also in \(A^c \cup B^c\).

An element cannot be in both \(A\) and \(A^c\). So the only possible part comes from being in \(A\) and in \(B^c\).

Therefore:

$$\left(A^c \cup B^c\right) \cap A = A \cap B^c$$

This is the set of elements in \(A\) but not in \(B\). So we can also write it as:

$$A - B$$

Thus,

$$\left(A \cap B\right)^c \cap A = A - B$$

11. Common mistakes to avoid

• Confusing union and intersection: union means “in at least one,” intersection means “in both.”
• Forgetting the universal set when finding complements: complements are taken relative to \(U\).
• Mixing up \(A-B\) and \(B-A\): order matters in difference.
• Using De Morgan's Laws incorrectly: when taking the complement of a union or intersection, change both the operation and each set.

For example,

$$\left(A \cup B\right)^c \neq A^c \cup B^c$$

The correct form is

$$\left(A \cup B\right)^c = A^c \cap B^c$$

12. Quick check questions

1. If \(A = \{1,2,3\}\) and \(B = \{3,4,5\}\), what is \(A \cap B\)?
2. If \(U = \{1,2,3,4,5,6\}\) and \(A = \{2,4,6\}\), what is \(A^c\)?
3. In words, what does \((A \cup B)^c\) mean?
4. Which De Morgan's Law matches \((A \cap B)^c\)?

Answers:

1. \(\{3\}\)
2. \(\{1,3,5\}\)
3. Elements not in \(A\) and not in \(B\)
4. \((A \cap B)^c = A^c \cup B^c\)

Summary

Set operations describe ways to combine or compare sets. The union \(A \cup B\) includes everything in either set, the intersection \(A \cap B\) includes only common elements, the difference \(A-B\) includes elements in \(A\) but not \(B\), and the complement \(A^c\) includes everything in the universal set not in \(A\).

De Morgan's Laws are:

$$\left(A \cup B\right)^c = A^c \cap B^c$$

$$\left(A \cap B\right)^c = A^c \cup B^c$$

These laws are powerful tools for simplifying expressions and proving set equivalence. If you remember the meaning of each operation in words, you will be much more confident when solving set theory problems.

Venn Diagrams and Categorical Syllogisms

In set theory and logic, we often need to describe groups of objects and the relationships between those groups. Venn diagrams help us picture how sets overlap, while categorical syllogisms help us test whether a logical conclusion follows from given statements.

These ideas are closely connected. A categorical statement such as “All cats are mammals” can be represented with sets. Then a Venn diagram can show whether another statement logically follows from it.

In this lesson, you will learn how to read and draw Venn diagrams, how to use them to count elements in overlapping sets, and how to test categorical syllogisms using set relationships.

1. Review: What is a set?

A set is a collection of objects. We usually name sets with capital letters, such as \(A\), \(B\), and \(C\). The objects inside the set are called elements.

For example, if \(A\) is the set of students who play soccer, and \(B\) is the set of students who play basketball, then a student who plays both sports belongs to both sets.

2. What is a Venn diagram?

A Venn diagram is a picture that uses circles to show relationships between sets. The rectangle around the circles represents the universal set, which is the full group being considered.

If two sets overlap, the shared region represents elements that belong to both sets. This overlap is called the intersection.

• \(A \cup B\): the union, meaning elements in \(A\) or \(B\) or both
• \(A \cap B\): the intersection, meaning elements in both \(A\) and \(B\)
• \(A'\) or \(A^c\): the complement, meaning elements not in \(A\)
• \(A \subseteq B\): \(A\) is a subset of \(B\), meaning every element of \(A\) is also in \(B\)

3. How to read overlapping sets

Suppose \(A\) is the set of students who study French, and \(B\) is the set of students who study Spanish. The overlap \(A \cap B\) represents students who study both languages.

If a student is in \(A\) but not in \(B\), then that student is in the part of circle \(A\) outside the overlap. This is written as \(A \setminus B\), which means “in \(A\), but not in \(B\).”

Venn diagrams are useful because they turn words into pictures. That makes it easier to understand complex set relationships and avoid counting the same elements twice.

4. Counting with Venn diagrams

When two sets overlap, we must be careful when counting the total number of elements in either set. If we simply add the sizes of the sets, the overlap gets counted twice.

For two sets, the correct formula is:

$$n(A \cup B) = n(A) + n(B) - n(A \cap B)$$

Here, \(n(A)\) means the number of elements in set \(A\).

For three sets, the counting is a little more involved:

$$n(A \cup B \cup C) = n(A)+n(B)+n(C)-n(A\cap B)-n(A\cap C)-n(B\cap C)+n(A\cap B\cap C)$$

We subtract the pair overlaps because they were counted twice, then add back the triple overlap because it was subtracted too many times.

Worked Example 1: Two-set counting

In a class of 30 students, 18 study art, 14 study music, and 6 study both. How many study art or music?

Let \(A\) be the set of art students and \(M\) be the set of music students.

Use the formula:

$$n(A \cup M) = n(A) + n(M) - n(A \cap M)$$

Substitute the values:

$$n(A \cup M) = 18 + 14 - 6 = 26$$

So, 26 students study art or music.

If the class has 30 students total, then the number who study neither subject is:

$$30 - 26 = 4$$

So, 4 students study neither art nor music.

5. Three-set Venn diagrams

With three sets, the diagram has three overlapping circles. The center region is especially important because it represents elements in all three sets at once.

When filling in a three-set Venn diagram, it is usually best to start with the middle, the region representing \(A \cap B \cap C\). Then work outward to the pair overlaps, then the single-set-only regions.

This step-by-step approach helps avoid mistakes.

Worked Example 2: Three-set counting

At a school, students may play soccer \((S)\), basketball \((B)\), or tennis \((T)\). Suppose:

• \(n(S)=20\)
• \(n(B)=18\)
• \(n(T)=12\)
• \(n(S\cap B)=7\)
• \(n(S\cap T)=5\)
• \(n(B\cap T)=4\)
• \(n(S\cap B\cap T)=2\)

Find \(n(S\cup B\cup T)\).

Use the three-set formula:

$$n(S\cup B\cup T)=20+18+12-7-5-4+2$$ $$=50-16+2=36$$

So, 36 students play at least one of the three sports.

6. What is a categorical statement?

A categorical statement is a statement about categories or classes of things. These statements often use words like all, some, or no.

Common forms are:

• All \(A\) are \(B\)
• No \(A\) are \(B\)
• Some \(A\) are \(B\)
• Some \(A\) are not \(B\)

These can be understood using sets:

• All \(A\) are \(B\) means \(A \subseteq B\)
• No \(A\) are \(B\) means \(A \cap B = \varnothing\)
• Some \(A\) are \(B\) means there is at least one element in \(A \cap B\)
• Some \(A\) are not \(B\) means there is at least one element in \(A\) outside \(B\)

7. What is a categorical syllogism?

A categorical syllogism is an argument made of two premises and a conclusion, where each statement is categorical.

For example:

• Premise 1: All dogs are mammals.
• Premise 2: All mammals are animals.
• Conclusion: All dogs are animals.

This argument is valid because if every dog is inside the set of mammals, and every mammal is inside the set of animals, then every dog must also be inside the set of animals.

Venn diagrams help us check whether a conclusion must be true based on the premises.

8. Using Venn diagrams for categorical syllogisms

To test a syllogism with a Venn diagram, we represent the sets involved and mark the regions that must be empty or occupied.

Here is the basic idea:

• If a statement says all, then part of the diagram is excluded or shaded.
• If a statement says no, then the overlap is shaded.
• If a statement says some, then we place an X in the region that must contain at least one element.

Important shading rule: shading means “this region is empty.” An X means “at least one element is here.”

9. How to represent common categorical statements

All \(A\) are \(B\)

This means there are no elements in \(A\) that are outside \(B\). So we shade the part of \(A\) that lies outside \(B\).

No \(A\) are \(B\)

This means the overlap \(A \cap B\) is empty. So we shade the intersection.

Some \(A\) are \(B\)

This means at least one element belongs to both sets. So we place an X in the overlap.

Some \(A\) are not \(B\)

This means at least one element is in \(A\) but outside \(B\). So we place an X in the part of \(A\) outside \(B\).

10. Testing validity of syllogisms

A syllogism is valid if the conclusion must be true whenever the premises are true. A Venn diagram does not ask whether the statements are realistic. It only asks whether the conclusion logically follows.

If the conclusion matches what is forced by the diagram, the argument is valid. If the conclusion could be false even when the premises are true, the argument is invalid.

Worked Example 3: A valid syllogism

Test the argument:

• Premise 1: All poets are writers.
• Premise 2: All writers are readers.
• Conclusion: All poets are readers.

Let \(P\) = poets, \(W\) = writers, and \(R\) = readers.

Premise 1 says all poets are writers, so shade the part of \(P\) outside \(W\).

Premise 2 says all writers are readers, so shade the part of \(W\) outside \(R\).

After shading these regions, every part of \(P\) outside \(R\) is forced to be empty. That means all poets are readers.

So the conclusion follows, and the syllogism is valid.

Worked Example 4: An invalid syllogism

Test the argument:

• Premise 1: Some athletes are musicians.
• Premise 2: Some musicians are artists.
• Conclusion: Some athletes are artists.

Let \(A\) = athletes, \(M\) = musicians, and \(R\) = artists.

Premise 1 places an X in the overlap of athletes and musicians.

Premise 2 places an X in the overlap of musicians and artists.

But these two X's do not have to represent the same person. One musician could be an athlete, and a different musician could be an artist.

So the conclusion “Some athletes are artists” is not forced by the premises.

Therefore, the syllogism is invalid.

11. A useful strategy for solving problems

1. Identify the sets clearly.
2. Translate words into set relationships.
3. Draw the Venn diagram carefully.
4. For counting problems, fill in known overlaps first.
5. For syllogisms, shade empty regions and place X's where elements must exist.
6. Check whether the conclusion is definitely true, not just possibly true.

12. Common mistakes to avoid

• Double-counting overlaps when adding set totals
• Confusing union and intersection
• Assuming “some” means “all”
• Thinking a conclusion is valid because it sounds reasonable
• Forgetting that two X's may represent different elements

13. Quick comparison of key ideas

• Venn diagrams are visual tools for sets.
• Set operations describe how groups combine or overlap.
• Categorical statements describe relationships between groups.
• Categorical syllogisms test whether a conclusion follows from those relationships.

Summary

Venn diagrams help us visualize sets, overlaps, and complements. They are especially useful for solving counting problems involving unions and intersections.

Categorical syllogisms are logical arguments built from statements like “all,” “some,” and “no.” By translating these statements into set relationships and using Venn diagrams, we can decide whether a conclusion is logically valid.

If you remember to read each statement carefully, shade empty regions, place X's for existing elements, and avoid double-counting, you will be able to solve both set problems and logic problems with confidence.

Lesson: Propositional Logic and Truth Values

In mathematics, we need a clear way to decide whether statements are true or false. Propositional logic is the part of mathematics that studies statements, their truth values, and how they can be combined to make new statements.

This topic is important because it helps students read mathematical arguments carefully, test whether reasoning is valid, and write clear proofs. It is also closely connected to set theory, algebra, and computer science.

1. What is a proposition?

A proposition is a statement that is either true or false. It must have exactly one truth value.

• "7 is a prime number" is a proposition. It is true.
• "10 is an odd number" is a proposition. It is false.
• "Close the door" is not a proposition because it is a command, not a statement.
• "What time is it?" is not a proposition because it is a question.

The truth value of a proposition is simply whether it is true (T) or false (F).

2. Simple and compound propositions

A simple proposition is a single statement.

Examples:

• \(p\): "12 is divisible by 3"
• \(q\): "12 is a prime number"

A compound proposition is formed by joining simple propositions using logical words such as and, or, not, and if...then.

These logical words are called connectives.

3. Common logical connectives

We usually use letters like \(p\) and \(q\) to represent propositions.

• Negation: "not \(p\)" is written as \(\neg p\).
• Conjunction: "\(p\) and \(q\)" is written as \(p \land q\).
• Disjunction: "\(p\) or \(q\)" is written as \(p \lor q\).
• Implication: "if \(p\), then \(q\)" is written as \(p \to q\).

Each connective has rules for deciding the truth value of the compound statement.

4. Negation

The negation of a proposition changes its truth value to the opposite.

If \(p\) is true, then \(\neg p\) is false. If \(p\) is false, then \(\neg p\) is true.

Example:

• \(p\): "9 is even" is false.
• \(\neg p\): "9 is not even" is true.

Truth table for negation:

$$ \begin{array}{c|c} p & \neg p \\\hline T & F \\ F & T \end{array} $$

5. Conjunction: and

A conjunction \(p \land q\) means both statements must be true.

The compound statement is true only when both \(p\) and \(q\) are true.

Truth table for conjunction:

$$ \begin{array}{c|c|c} p & q & p \land q \\\hline T & T & T \\ T & F & F \\ F & T & F \\ F & F & F \end{array} $$

Example:

• \(p\): "8 is even" is true.
• \(q\): "8 is greater than 10" is false.
• Therefore, \(p \land q\) is false.

6. Disjunction: or

A disjunction \(p \lor q\) means at least one of the statements is true.

In mathematics, "or" usually means inclusive or. That means:

• \(p \lor q\) is true if only \(p\) is true,
• or only \(q\) is true,
• or both are true.

It is false only when both statements are false.

Truth table for disjunction:

$$ \begin{array}{c|c|c} p & q & p \lor q \\\hline T & T & T \\ T & F & T \\ F & T & T \\ F & F & F \end{array} $$

Example:

• \(p\): "15 is divisible by 3" is true.
• \(q\): "15 is divisible by 4" is false.
• Therefore, \(p \lor q\) is true.

7. Implication: if...then

An implication has the form \(p \to q\), which is read as "if \(p\), then \(q\)."

Here, \(p\) is called the hypothesis and \(q\) is called the conclusion.

The only time an implication is false is when the hypothesis is true and the conclusion is false.

Truth table for implication:

$$ \begin{array}{c|c|c} p & q & p \to q \\\hline T & T & T \\ T & F & F \\ F & T & T \\ F & F & T \end{array} $$

This often feels unusual at first. Why is \(p \to q\) true when \(p\) is false? In logic, the statement only makes a promise about what happens when \(p\) is true. If \(p\) never happens, the statement is not broken.

Example:

• \(p\): "A number is divisible by 4"
• \(q\): "The number is even"

The implication "If a number is divisible by 4, then it is even" is true, because every number divisible by 4 is even.

8. Building truth tables

A truth table lists all possible truth values of the simple propositions and then shows the truth value of the compound proposition.

If there are:

• 1 proposition, there are \(2\) rows,
• 2 propositions, there are \(4\) rows,
• 3 propositions, there are \(8\) rows.

In general, for \(n\) propositions, there are \(2^n\) rows.

9. Worked Example 1: Identify propositions and truth values

Decide which of the following are propositions, and give the truth value if possible.

1. "5 + 7 = 12"
2. "Please sit down."
3. "\(10 < 3\)"
4. "Is 9 a square number?"

Solution:

1. "5 + 7 = 12" is a proposition. It is true.
2. "Please sit down." is not a proposition because it is a command.
3. "\(10 < 3\)" is a proposition. It is false.
4. "Is 9 a square number?" is not a proposition because it is a question.

Worked Example 2: Evaluate conjunction and disjunction

Let

• \(p\): "6 is even"
• \(q\): "6 is greater than 10"

Find the truth values of \(p\), \(q\), \(p \land q\), and \(p \lor q\).

Solution:

• \(p\) is true, because 6 is even.
• \(q\) is false, because 6 is not greater than 10.
• \(p \land q\) means "6 is even and 6 is greater than 10." Since both are not true, this is false.
• \(p \lor q\) means "6 is even or 6 is greater than 10." At least one part is true, so this is true.

Worked Example 3: Evaluate an implication

Let

• \(p\): "\(x = 4\)"
• \(q\): "\(x^2 = 16\)"

Consider the implication \(p \to q\): "If \(x = 4\), then \(x^2 = 16\)."

Solution:

If \(x = 4\), then

$$ x^2 = 4^2 = 16 $$

So the implication is true.

Now think about the reverse statement: "If \(x^2 = 16\), then \(x = 4\)." This is not always true, because \(x\) could also be \(-4\). This shows that the direction of an implication matters.

Worked Example 4: Complete a truth table

Construct the truth table for \((p \land q) \to p\).

Step 1: List all possible truth values of \(p\) and \(q\).

$$ \begin{array}{c|c} p & q \\\hline T & T \\ T & F \\ F & T \\ F & F \end{array} $$

Step 2: Find \(p \land q\).

Step 3: Find \((p \land q) \to p\).

$$ \begin{array}{c|c|c|c} p & q & p \land q & (p \land q) \to p \\\hline T & T & T & T \\ T & F & F & T \\ F & T & F & T \\ F & F & F & T \end{array} $$

This compound statement is true in every row. A statement that is always true is called a tautology.

10. Important ideas to remember

• A proposition must be a statement with a definite truth value.
• Negation reverses truth value.
• Conjunction \(p \land q\) is true only if both parts are true.
• Disjunction \(p \lor q\) is true if at least one part is true.
• Implication \(p \to q\) is false only when \(p\) is true and \(q\) is false.
• Truth tables help us test and understand compound statements.

11. Common mistakes

• Mistake 1: Thinking that "or" means only one statement can be true. In mathematics, \(p \lor q\) is still true when both are true.
• Mistake 2: Thinking an implication is false whenever \(p\) is false. Actually, if \(p\) is false, then \(p \to q\) is true in propositional logic.
• Mistake 3: Confusing a statement with its converse. "If \(p\), then \(q\)" does not automatically mean "If \(q\), then \(p\)."
• Mistake 4: Calling commands or questions propositions. Only statements that can be true or false are propositions.

12. Quick practice questions

1. Is the sentence "\(2 + 2 = 5\)" a proposition? What is its truth value?
2. If \(p\) is false, what is the truth value of \(\neg p\)?
3. If \(p\) is true and \(q\) is false, find the truth value of \(p \land q\).
4. If \(p\) is false and \(q\) is true, find the truth value of \(p \lor q\).
5. If \(p\) is true and \(q\) is false, find the truth value of \(p \to q\).

Answers:

1. Yes, it is a proposition. It is false.
2. True.
3. False.
4. True.
5. False.

Summary

Propositional logic studies statements that are either true or false. These statements can be combined using connectives such as not, and, or, and if...then.

By using truth values and truth tables, we can decide whether compound statements are true or false in every possible case. This is an important skill for understanding mathematical reasoning and writing correct proofs.

Truth Tables and Logical Equivalence

In formal logic, we study statements that can be either true or false. These statements are called propositions. Truth tables help us organize all possible truth values of propositions and determine whether more complicated statements are true or false.

This lesson explains how to build and read truth tables, how to identify tautologies and contradictions, and how to decide whether two statements are logically equivalent.

1. Basic logical symbols

We usually use letters such as \(p\), \(q\), and \(r\) to represent propositions.

• Negation: \(\neg p\) means “not \(p\)”
• Conjunction: \(p \land q\) means “\(p\) and \(q\)”
• Disjunction: \(p \lor q\) means “\(p\) or \(q\)”
• Conditional: \(p \to q\) means “if \(p\), then \(q\)”
• Biconditional: \(p \leftrightarrow q\) means “\(p\) if and only if \(q\)”

Each of these has rules for when it is true or false.

2. Truth values for the main connectives

The truth values of the basic connectives are:

• \(\neg p\) is true when \(p\) is false, and false when \(p\) is true.
• \(p \land q\) is true only when both \(p\) and \(q\) are true.
• \(p \lor q\) is true when at least one of \(p\) or \(q\) is true.
• \(p \to q\) is false only when \(p\) is true and \(q\) is false.
• \(p \leftrightarrow q\) is true when \(p\) and \(q\) have the same truth value.

A quick way to remember the conditional \(p \to q\): it only fails when the “if” part happens but the “then” part does not.

3. How to build a truth table

If a statement has:

• 1 variable, there are \(2\) rows
• 2 variables, there are \(4\) rows
• 3 variables, there are \(8\) rows

In general, for \(n\) variables, there are \(2^n\) rows.

To make a truth table:

1. List all possible truth values for the variables.
2. Create columns for simpler parts of the statement first.
3. Use those columns to find the truth values of the full statement.

4. Standard truth table for two variables

For propositions \(p\) and \(q\), the four possible combinations are:

$$ \begin{array}{c|c} p & q \\\hline T & T \\ T & F \\ F & T \\ F & F \end{array} $$

This pattern is the starting point for many truth tables.

5. Worked Example 1: Finding the truth table of a compound statement

Construct a truth table for \(\neg p \lor q\).

We need columns for \(p\), \(q\), \(\neg p\), and then \(\neg p \lor q\).

$$ \begin{array}{c|c|c|c} p & q & \neg p & \neg p \lor q \\\hline T & T & F & T \\ T & F & F & F \\ F & T & T & T \\ F & F & T & T \end{array} $$

Look at the last column. The statement \(\neg p \lor q\) is false only in one case: when \(p\) is true and \(q\) is false.

This is important because it matches the truth values of \(p \to q\). So we already have a hint that:

$$ \neg p \lor q \equiv p \to q $$

Here, the symbol \(\equiv\) means “is logically equivalent to.”

6. Tautology, contradiction, and contingency

After making a truth table, we can classify a statement by looking at the final column.

• Tautology: always true
• Contradiction: always false
• Contingency: sometimes true and sometimes false

Examples:

• \(p \lor \neg p\) is a tautology
• \(p \land \neg p\) is a contradiction
• \(p \land q\) is a contingency

7. Worked Example 2: Identifying a tautology

Show that \(p \lor \neg p\) is a tautology.

$$ \begin{array}{c|c|c} p & \neg p & p \lor \neg p \\\hline T & F & T \\ F & T & T \end{array} $$

The final column is all true, so \(p \lor \neg p\) is a tautology.

This statement is called the law of excluded middle: either a proposition is true, or it is not true.

8. Worked Example 3: Identifying a contradiction

Show that \(p \land \neg p\) is a contradiction.

$$ \begin{array}{c|c|c} p & \neg p & p \land \neg p \\\hline T & F & F \\ F & T & F \end{array} $$

The final column is all false, so \(p \land \neg p\) is a contradiction.

This makes sense because a proposition cannot be both true and false at the same time.

9. Logical equivalence

Two statements are logically equivalent if they have exactly the same truth values in every possible case.

To test this, make a truth table for both statements and compare their final columns.

If the final columns match row by row, then the statements are logically equivalent.

10. Worked Example 4: Proving logical equivalence

Show that \(p \to q\) is logically equivalent to \(\neg p \lor q\).

We build one table including both expressions.

$$ \begin{array}{c|c|c|c|c} p & q & \neg p & p \to q & \neg p \lor q \\\hline T & T & F & T & T \\ T & F & F & F & F \\ F & T & T & T & T \\ F & F & T & T & T \end{array} $$

The last two columns are identical. Therefore,

$$ p \to q \equiv \neg p \lor q $$

This is one of the most useful logical equivalences in mathematics.

11. Common logical equivalences to know

Truth tables can be used to verify many important equivalences.

• \(p \to q \equiv \neg p \lor q\)
• \(\neg(\neg p) \equiv p\)
• \(\neg(p \land q) \equiv \neg p \lor \neg q\)
• \(\neg(p \lor q) \equiv \neg p \land \neg q\)
• \(p \leftrightarrow q \equiv (p \to q) \land (q \to p)\)

The third and fourth rules are called De Morgan’s Laws. They are especially useful when simplifying logical statements.

12. Tips for avoiding mistakes

• Do not confuse \(p \lor q\) with everyday “either/or.” In logic, \(p \lor q\) is true if one or both are true.
• Be careful with conditionals. \(p \to q\) is true in three out of four cases.
• Add intermediate columns. For a complicated statement, compute one part at a time.
• Compare final columns exactly when checking equivalence.
• Count rows correctly. Two variables need 4 rows, three variables need 8 rows.

13. Strategy for complex propositions

For a statement such as \((p \land q) \to \neg r\), do not try to evaluate it all at once.

Instead, build columns in this order:

1. \(p\), \(q\), \(r\)
2. \(p \land q\)
3. \(\neg r\)
4. \((p \land q) \to \neg r\)

This step-by-step method reduces errors and makes your reasoning easier to follow.

14. Why truth tables matter

Truth tables are useful because they let us check whether a statement is always true, always false, or equivalent to another statement. In set theory, proofs, and algebraic reasoning, this helps us justify each step clearly and correctly.

They are also an important foundation for mathematical proof, computer science, and logical reasoning in general.

Summary

• A proposition is a statement that is either true or false.
• A truth table lists all possible truth values of propositions and compound statements.
• Use logical symbols such as \(\neg\), \(\land\), \(\lor\), \(\to\), and \(\leftrightarrow\).
• A tautology is always true.
• A contradiction is always false.
• A contingency is sometimes true and sometimes false.
• Two statements are logically equivalent if their final truth table columns are identical.
• One key equivalence is $$p \to q \equiv \neg p \lor q$$

If you can build a truth table carefully and compare the final columns, you can analyze almost any logical statement at this level.

Conditional Statements and Contraposition are an important part of formal logic. They help us understand how mathematical statements are built and how to test whether an argument is logically correct.

In mathematics, many statements are written in the form “if ... then ...”. Learning how to rewrite and analyze these statements helps students read proofs, write proofs, and avoid common logic mistakes.

In this lesson, we will learn what a conditional statement is, how to identify its related forms, and why the contrapositive is especially important in mathematics.

1. Conditional Statements

A conditional statement has the form:

$$\text{If } p, \text{ then } q$$

We also write this as:

$$p \to q$$

Here:

• p is the hypothesis or condition.
• q is the conclusion.

Example: “If a number is divisible by 4, then it is even.”

• Hypothesis: the number is divisible by 4
• Conclusion: the number is even

This statement is true because every number divisible by 4 must also be even.

Important idea: A conditional statement does not say that every even number is divisible by 4. It only tells us what happens when the hypothesis is true.

2. Related Statements

From a conditional statement, we can make three related statements:

• Converse: If \(q\), then \(p\)
• Inverse: If not \(p\), then not \(q\)
• Contrapositive: If not \(q\), then not \(p\)

Starting with:

$$p \to q$$

we get:

• Converse: $$q \to p$$
• Inverse: $$\neg p \to \neg q$$
• Contrapositive: $$\neg q \to \neg p$$

Here, the symbol \(\neg\) means “not.”

3. Which Statements Have the Same Truth Value?

This is the key fact of the lesson:

• A conditional statement and its contrapositive are always logically equivalent.
• The converse and inverse are also logically equivalent to each other.
• But the conditional is not always logically equivalent to its converse or inverse.

That means:

$$p \to q \quad \text{has the same truth value as} \quad \neg q \to \neg p$$

and

$$q \to p \quad \text{has the same truth value as} \quad \neg p \to \neg q$$

4. Why Contraposition Matters

Sometimes a direct statement is hard to prove. In those cases, it can be easier to prove the contrapositive instead.

If we can prove

$$\neg q \to \neg p$$

then we have also proved

$$p \to q$$

This method is called proof by contraposition.

For example, suppose we want to prove:

“If a number is odd, then its square is odd.”

Instead of proving this directly, we could prove the contrapositive:

“If a number’s square is not odd, then the number is not odd.”

Since “not odd” means even, this becomes:

“If a number’s square is even, then the number is even.”

This is often easier to work with.

5. Truth Values and Counterexamples

To decide whether a conditional statement is true, we ask: is there any case where the hypothesis is true but the conclusion is false?

If there is even one such case, the conditional is false.

So for \(p \to q\), the only way it is false is when:

• \(p\) is true, and
• \(q\) is false.

This is why a counterexample is enough to show a statement is false.

Example: “If a number is even, then it is divisible by 4.”

This is false because \(6\) is even, but \(6\) is not divisible by 4. One counterexample is enough.

6. Worked Example 1: Identifying the Related Statements

Original statement: “If an angle is a right angle, then it measures \(90^\circ\).”

Let

• \(p\): an angle is a right angle
• \(q\): the angle measures \(90^\circ\)

Then the statements are:

• Conditional: If an angle is a right angle, then it measures \(90^\circ\).
• Converse: If an angle measures \(90^\circ\), then it is a right angle.
• Inverse: If an angle is not a right angle, then it does not measure \(90^\circ\).
• Contrapositive: If an angle does not measure \(90^\circ\), then it is not a right angle.

In standard geometry, all four of these happen to be true. But that does not mean this always happens. In many situations, the converse and inverse can be false even when the original statement is true.

7. Worked Example 2: A Case Where the Converse Is False

Original statement: “If a number is divisible by 6, then it is divisible by 3.”

Let

• \(p\): the number is divisible by 6
• \(q\): the number is divisible by 3

Conditional: If a number is divisible by 6, then it is divisible by 3.

This is true.

Converse: If a number is divisible by 3, then it is divisible by 6.

This is false. For example, \(9\) is divisible by 3, but not by 6.

Inverse: If a number is not divisible by 6, then it is not divisible by 3.

This is also false. For example, \(9\) is not divisible by 6, but it is divisible by 3.

Contrapositive: If a number is not divisible by 3, then it is not divisible by 6.

This is true, and it matches the truth value of the original conditional.

This example shows the key pattern clearly:

• Conditional and contrapositive: both true
• Converse and inverse: both false

8. Worked Example 3: Writing a Contrapositive

Statement: “If a figure is a square, then it is a rectangle.”

First identify:

• \(p\): the figure is a square
• \(q\): the figure is a rectangle

The contrapositive is:

“If a figure is not a rectangle, then it is not a square.”

Notice what changed:

1. The parts switched places.
2. Both parts were negated.

That is the correct way to form a contrapositive.

A common mistake is to write “If a figure is not a square, then it is not a rectangle.” That is actually the inverse, not the contrapositive.

9. Worked Example 4: Using Contraposition in Reasoning

Consider the statement:

“If an integer ends in 0, then it is divisible by 10.”

The contrapositive is:

“If an integer is not divisible by 10, then it does not end in 0.”

Suppose we know that \(347\) is not divisible by 10. By the contrapositive, we can conclude that \(347\) does not end in 0.

This may seem obvious here, but in harder proofs this type of reasoning is very useful. Instead of proving the original statement directly, we use the logically equivalent contrapositive.

10. How to Form Each Type Correctly

Start with the statement:

$$\text{If } p, \text{ then } q$$

• Conditional: If \(p\), then \(q\)
• Converse: If \(q\), then \(p\)
• Inverse: If not \(p\), then not \(q\)
• Contrapositive: If not \(q\), then not \(p\)

A quick memory tip:

• Converse: switch
• Inverse: negate
• Contrapositive: switch and negate

11. Common Mistakes to Avoid

• Do not assume the converse is automatically true because the original statement is true.
• Do not confuse the inverse with the contrapositive.
• When negating a statement, make sure the meaning is correct. For example, the negation of “is even” is “is not even,” which for integers means “is odd.”
• Remember that only the contrapositive is always logically equivalent to the original conditional.

12. Why This Matters in Proofs

Mathematics depends on correct logical structure. When you read a theorem written as “If \(p\), then \(q\),” you must know that proving “If \(q\), then \(p\)” is not the same thing.

Many proof errors happen because students accidentally prove the converse instead of the original statement.

On the other hand, proving the contrapositive is completely valid, because it is logically equivalent to the original statement.

Brief Summary

A conditional statement has the form \(p \to q\), meaning “if \(p\), then \(q\).” From it, we can form the converse, inverse, and contrapositive.

The most important fact is that the conditional and contrapositive are logically equivalent, so they always have the same truth value. The converse and inverse are also equivalent to each other, but they are not necessarily equivalent to the original statement.

Understanding these relationships helps you test statements, find counterexamples, and write stronger mathematical proofs.

Quantifiers and Negation are important tools in mathematical logic. They help us write statements clearly and help us decide whether a statement is true or false.

In this lesson, you will learn what the quantifiers "for all" and "there exists" mean, how to read statements that use them, and how to correctly negate those statements.

This idea is especially important in proofs. A common mistake is to negate only part of a statement. In logic, when a statement contains a quantifier, the negation changes both the quantifier and the condition that follows it.

1. What is a quantifier?

A quantifier tells us how many elements in a set make a statement true.

• Universal quantifier: \(\forall\) means for all or for every.
• Existential quantifier: \(\exists\) means there exists or there is at least one.

For example:

• \(\forall x \in \mathbb{R},\ x+0=x\)
• Read as: For all real numbers \(x\), \(x+0=x\).

• \(\exists x \in \mathbb{R}\) such that \(x^2=4\)
• Read as: There exists a real number \(x\) such that \(x^2=4\).

The set being discussed is called the domain. It matters a lot. A statement could be true in one domain and false in another.

For instance, the statement "There exists \(x\) such that \(x^2=2\)" is:

• true if the domain is the real numbers,
• false if the domain is the integers.

2. What does negation mean?

To negate a statement means to write its opposite truth value. If the original statement is true, its negation is false. If the original statement is false, its negation is true.

For a simple statement \(P\), the negation is written as \(\neg P\), which means not \(P\).

Example:

• Statement: "\(x > 3\)"
• Negation: "\(x \leq 3\)"

Notice that the negation must include every possibility not covered by the original statement.

3. Negating quantified statements

When a statement has a quantifier, the negation follows two key rules:

1. Change the quantifier.
2. Negate the statement after it.

The two main rules are:

$$\neg(\forall x,\ P(x)) \equiv \exists x\text{ such that }\neg P(x)$$

In words: The negation of “for all \(x\), \(P(x)\)” is “there exists an \(x\) such that not \(P(x)\).”

Also,

$$\neg(\exists x,\ P(x)) \equiv \forall x,\ \neg P(x)$$

In words: The negation of “there exists an \(x\) such that \(P(x)\)” is “for all \(x\), not \(P(x)\).”

You can think of it this way:

• "Everyone passed" becomes "At least one person did not pass."
• "Someone passed" becomes "No one passed."

4. Why the quantifier must change

Suppose we say:

\(\forall x \in \mathbb{R},\ x^2 \geq 0\)

This means every real number has a square that is nonnegative.

If this were false, what would that mean? It would mean there is at least one real number whose square is negative. So the negation is:

\(\exists x \in \mathbb{R}\) such that \(x^2 < 0\)

That is why the quantifier changes from \(\forall\) to \(\exists\).

5. Common negations of conditions

When negating a quantified statement, you often need to negate an inequality or equation correctly.

• Negation of \(x > a\) is \(x \leq a\)
• Negation of \(x \geq a\) is \(x < a\)
• Negation of \(x = a\) is \(x \ne a\)
• Negation of \(x \ne a\) is \(x = a\)
• Negation of \(x < a\) is \(x \geq a\)
• Negation of \(x \leq a\) is \(x > a\)

Be careful: the negation of \(x > 2\) is not \(x < 2\). It is \(x \leq 2\), because \(2\) itself must be included.

6. Worked Example 1: Negating a universal statement

Statement:

\(\forall x \in \mathbb{R},\ x+1 > x\)

Step 1: Identify the quantifier.

The statement uses \(\forall\), meaning “for all.”

Step 2: Change the quantifier.

\(\forall\) changes to \(\exists\).

Step 3: Negate the condition.

The condition is \(x+1 > x\). Its negation is \(x+1 \leq x\).

Negation:

$$\exists x \in \mathbb{R}\text{ such that }x+1 \leq x$$

In words: There exists a real number \(x\) such that \(x+1\) is less than or equal to \(x\).

7. Worked Example 2: Negating an existential statement

Statement:

\(\exists n \in \mathbb{Z}\) such that \(n^2=10\)

Step 1: Identify the quantifier.

The statement uses \(\exists\), meaning “there exists.”

Step 2: Change the quantifier.

\(\exists\) changes to \(\forall\).

Step 3: Negate the condition.

The condition is \(n^2=10\). Its negation is \(n^2 \ne 10\).

Negation:

$$\forall n \in \mathbb{Z},\ n^2 \ne 10$$

In words: For every integer \(n\), \(n^2\) is not equal to 10.

8. Worked Example 3: A statement with two parts

Statement:

\(\forall x \in \mathbb{R},\ x>2 \Rightarrow x^2>4\)

This says: For every real number \(x\), if \(x\) is greater than 2, then \(x^2\) is greater than 4.

To negate this correctly, we need to remember that the negation of an implication

\(P \Rightarrow Q\)

is

\(P \text{ and } \neg Q\)

So the inside statement

\(x>2 \Rightarrow x^2>4\)

becomes

\(x>2\) and \(x^2 \leq 4\)

Now change the quantifier from \(\forall\) to \(\exists\).

Negation:

$$\exists x \in \mathbb{R}\text{ such that }x>2\text{ and }x^2 \leq 4$$

In words: There exists a real number greater than 2 whose square is less than or equal to 4.

9. Worked Example 4: Double quantifiers

Sometimes a statement contains more than one quantifier.

Statement:

\(\forall x \in \mathbb{R},\ \exists y \in \mathbb{R}\text{ such that } y>x\)

This means: For every real number \(x\), there exists a real number \(y\) that is greater than \(x\).

To negate this, work from the outside in.

• First, change \(\forall x\) to \(\exists x\).
• Then change \(\exists y\) to \(\forall y\).
• Then negate the condition \(y>x\), which becomes \(y \leq x\).

Negation:

$$\exists x \in \mathbb{R}\text{ such that }\forall y \in \mathbb{R},\ y \leq x$$

In words: There exists a real number \(x\) such that every real number \(y\) is less than or equal to \(x\).

This negation says there is a largest real number. Since there is no largest real number, the negation is false and the original statement is true.

10. A useful pattern to remember

Here are the two most important patterns:

• \(\forall\) becomes \(\exists\)
• \(\exists\) becomes \(\forall\)

Then negate the condition that follows.

You can summarize this as:

$$\neg(\forall x\, P(x)) = \exists x\, \neg P(x)$$

$$\neg(\exists x\, P(x)) = \forall x\, \neg P(x)$$

11. Common mistakes

• Forgetting to change the quantifier.
  Example: Negating \(\forall x, P(x)\) as \(\forall x, \neg P(x)\) is incorrect.
• Negating inequalities incorrectly.
  Example: Negation of \(x \geq 5\) is \(x < 5\), not \(x \leq 5\).
• Ignoring the domain.
  A statement over integers may have a different truth value than the same statement over real numbers.
• Negating only part of a statement.
  You must negate the entire condition after the quantifier.

12. Quick practice ideas

Try negating these on your own:

1. \(\forall x \in \mathbb{R},\ x^2 \geq 0\)
2. \(\exists x \in \mathbb{Z},\ x+3=0\)
3. \(\forall n \in \mathbb{N},\ n<10\)

Possible answers:

1. \(\exists x \in \mathbb{R}\) such that \(x^2 < 0\)
2. \(\forall x \in \mathbb{Z},\ x+3 \ne 0\)
3. \(\exists n \in \mathbb{N}\) such that \(n \geq 10\)

Summary

Quantifiers tell us whether a statement is about all elements or about at least one element. The universal quantifier is \(\forall\), and the existential quantifier is \(\exists\).

To negate a quantified statement, switch the quantifier and negate the condition. So, “for all” becomes “there exists,” and “there exists” becomes “for all.” Then carefully negate inequalities, equations, or other conditions inside the statement.

If you remember these rules and pay attention to the domain, you will be able to interpret and negate quantified statements accurately.

Direct Mathematical Proof is one of the most important methods used in mathematics. It is a way of showing that a statement is always true by starting from known facts and logically moving step by step to the conclusion.

In 11th Grade Maths, direct proof is often used with statements about parity (even and odd numbers), divisibility, and simple number theory ideas. Learning this method helps you write mathematics clearly and convincingly.

This lesson will show you what a direct proof is, when to use it, how to structure one, and how to write direct proofs involving even numbers, odd numbers, and divisibility.

1. What is a direct proof?

A direct proof is used to prove a statement of the form:

"If P, then Q."

In logic, this is written as:

\(P \to Q\)

To prove this directly, we assume the hypothesis \(P\) is true, and then use definitions, algebra, and known facts to show that the conclusion \(Q\) must also be true.

So the overall idea is:

1. Assume the starting condition is true.
2. Use definitions and logical steps.
3. Reach the required conclusion.

2. Why direct proof works

Many mathematical statements are built from definitions. For example:

• An integer is even if it can be written as \(2k\) for some integer \(k\).
• An integer is odd if it can be written as \(2k+1\) for some integer \(k\).
• An integer \(a\) is divisible by an integer \(b\) if there exists an integer \(k\) such that \(a=bk\).

These definitions are the foundation of many direct proofs. Once you rewrite a number using its definition, the proof often becomes much easier.

3. Important definitions to know

Before writing proofs, make sure you know these definitions clearly.

• Even integer: \(n\) is even if \(n=2k\) for some integer \(k\).
• Odd integer: \(n\) is odd if \(n=2k+1\) for some integer \(k\).
• Divisibility: \(a\) is divisible by \(b\) if \(a=bk\) for some integer \(k\).
• Multiple: \(a\) is a multiple of \(b\) if \(a=bk\) for some integer \(k\).

Notice that the phrase "for some integer \(k\)" is essential. In proofs, we usually introduce a new integer variable like \(k\), \(m\), or \(r\) when using one of these definitions.

4. The structure of a direct proof

A good direct proof usually follows a clear structure.

1. State what is given. Begin by assuming the hypothesis.
2. Use the definition. Rewrite the given information in algebraic form.
3. Work logically. Simplify or manipulate the expression.
4. Match the conclusion. Show that the final expression fits the definition you need.
5. Write a concluding sentence.

For example, if you want to prove a number is even, your goal is to write it in the form \(2(\text{integer})\). If you want to prove a number is odd, your goal is to write it in the form \(2(\text{integer})+1\).

5. Worked Example 1: The sum of two even integers is even

Statement: If \(a\) and \(b\) are even integers, then \(a+b\) is even.

Step 1: Assume the hypothesis.

Suppose \(a\) and \(b\) are even integers.

Step 2: Use the definition of even.

Then there exist integers \(m\) and \(n\) such that

\(a=2m\) and \(b=2n\).

Step 3: Add the numbers.

$$a+b=2m+2n=2(m+n)$$

Step 4: Use closure of integers.

Since \(m+n\) is an integer, let \(k=m+n\). Then

$$a+b=2k$$

Conclusion: Since \(a+b\) is written in the form \(2k\), it is even. Therefore, the sum of two even integers is even.

Why this proof works: The definition of even gave us a form to use. After substitution, the result still had a factor of 2, so the sum was even.

6. Worked Example 2: The sum of an even integer and an odd integer is odd

Statement: If \(a\) is even and \(b\) is odd, then \(a+b\) is odd.

Step 1: Assume the hypothesis.

Suppose \(a\) is even and \(b\) is odd.

Step 2: Use definitions.

Since \(a\) is even, there exists an integer \(m\) such that

\(a=2m\).

Since \(b\) is odd, there exists an integer \(n\) such that

\(b=2n+1\).

Step 3: Add the expressions.

$$a+b=2m+(2n+1)=2m+2n+1=2(m+n)+1$$

Step 4: Identify the required form.

Since \(m+n\) is an integer, let \(k=m+n\). Then

$$a+b=2k+1$$

Conclusion: This is the form of an odd integer, so \(a+b\) is odd.

Key idea: To prove a result is odd, your final line should look like \(2k+1\), where \(k\) is an integer.

7. Worked Example 3: The product of two odd integers is odd

Statement: If \(a\) and \(b\) are odd integers, then \(ab\) is odd.

Step 1: Assume the hypothesis.

Suppose \(a\) and \(b\) are odd integers.

Step 2: Write each odd integer in standard form.

Then there exist integers \(m\) and \(n\) such that

\(a=2m+1\) and \(b=2n+1\).

Step 3: Multiply.

$$ab=(2m+1)(2n+1)$$

Expand:

$$ab=4mn+2m+2n+1$$

Factor out 2 from the first three terms:

$$ab=2(2mn+m+n)+1$$

Step 4: Identify the integer.

Since \(2mn+m+n\) is an integer, let

$$k=2mn+m+n$$

Then

$$ab=2k+1$$

Conclusion: Therefore, \(ab\) is odd.

What to notice: In multiplication proofs, expanding carefully is important. After expanding, try to rearrange the result into either \(2k\) or \(2k+1\).

8. Worked Example 4: If an integer is divisible by 3, then its square is divisible by 3

Statement: If \(n\) is divisible by 3, then \(n^2\) is divisible by 3.

Step 1: Assume the hypothesis.

Suppose \(n\) is divisible by 3.

Step 2: Use the definition of divisibility.

Then there exists an integer \(k\) such that

$$n=3k$$

Step 3: Square both sides.

$$n^2=(3k)^2=9k^2=3(3k^2)$$

Step 4: Identify the integer.

Since \(3k^2\) is an integer, let \(m=3k^2\). Then

$$n^2=3m$$

Conclusion: Therefore, \(n^2\) is divisible by 3.

Main idea: To prove divisibility, your goal is to show the expression equals the divisor times an integer.

9. How to recognize when to use direct proof

Direct proof is a good choice when:

• The statement is in the form if ... then ....
• The hypothesis gives you useful algebraic information.
• The conclusion can be shown by applying a definition.
• You can move naturally from the assumption to the result.

For example, statements about even, odd, and divisible numbers often work well with direct proof because the definitions are simple and algebraic.

10. Common proof language

When writing direct proofs, it helps to use formal mathematical language. Here are some useful sentence starters:

• Suppose that ...
• Assume that ...
• Since \(n\) is even, there exists an integer \(k\) such that ...
• By the definition of divisibility, ...
• Therefore, ...
• Hence, ...
• This is of the form \(2k\), so ...
• This is of the form \(2k+1\), so ...

Good proof writing is not only about getting the right answer. It is also about communicating each step clearly.

11. Common mistakes to avoid

• Not starting from the assumption. In a direct proof, begin with what is given.
• Using examples instead of a general proof. Checking a few numbers does not prove a statement for all integers.
• Forgetting to say the variable is an integer. This matters because definitions of even, odd, and divisibility depend on integers.
• Stopping too early. You must clearly show the final expression matches the definition you need.
• Using unclear symbols. Make sure each variable is introduced properly.

For instance, if you end with \(a+b=2(m+n)\), you should also state that \(m+n\) is an integer. That is what allows you to conclude the sum is even.

12. A simple proof template

You can use this template for many direct proofs.

1. Suppose the hypothesis is true.
2. By the definition of the given property, write the number in algebraic form.
3. Simplify the expression.
4. Rewrite the result in the form needed for the conclusion.
5. State the conclusion clearly.

For parity proofs:

• Even goal: show the expression equals \(2k\).
• Odd goal: show the expression equals \(2k+1\).

For divisibility proofs:

• Divisible by \(d\): show the expression equals \(dk\) for some integer \(k\).

13. Quick check questions

Try thinking through these on your own:

• If \(n\) is even, why can we write \(n=2k\) for some integer \(k\)?
• If \(n\) is odd, what form should \(n^2\) have if it is also odd?
• If \(a\) is divisible by 5, what expression can you write for \(a\)?

These questions all focus on the same idea: use the definition first.

14. Final summary

A direct mathematical proof begins by assuming the given condition is true and then uses definitions, algebra, and logical reasoning to reach the conclusion.

For statements about even and odd integers, rewrite numbers using \(2k\) or \(2k+1\). For divisibility, rewrite numbers using the divisor times an integer. Then simplify until the conclusion appears in the required form.

If you remember to start with the assumption, use the correct definition, and clearly match the conclusion, you will be able to construct strong direct proofs in basic number theory.

Proof by Contradiction and Counterexamples are two important tools in mathematics. They help us decide whether a statement is true or false, and they are especially useful in set theory and formal logic.

In maths, a statement or conjecture is a claim that can be either true or false. For example, “All even numbers are divisible by 2” is a statement, and “All prime numbers are odd” is also a statement.

Sometimes we want to prove a statement is true. Other times, we want to show a statement is false. These two goals often use different methods:

• Proof by contradiction is used to prove that a statement is true.
• A counterexample is used to show that a statement is false.

Learning when to use each method is a key part of writing correct mathematical arguments.

1. What is a counterexample?

A counterexample is a specific example that shows a general statement is false.

If someone claims, “Every object in this box is red,” then finding just one blue object in the box is enough to prove the claim is false. In maths, the same idea applies.

If a statement says something is true for all numbers, sets, or cases, then only one example that does not work is needed to disprove it.

For example, consider the statement:

“All prime numbers are odd.”

This sounds almost true, because many prime numbers are odd: 3, 5, 7, 11, and so on. But the number 2 is prime and even. So 2 is a counterexample.

That means the statement is false.

Important idea: A counterexample must actually fit the situation being discussed. It must be relevant and precise.

• If the claim is about integers, your counterexample must be an integer.
• If the claim is about sets, your counterexample must involve sets.
• If the claim says “for all,” then one valid exception is enough.

2. What is proof by contradiction?

Proof by contradiction is a method of proving a statement by showing that its opposite leads to an impossible result.

The basic idea is:

1. Start by assuming the statement you want to prove is false.
2. Use logic and known facts to follow the consequences of that assumption.
3. If the assumption leads to a contradiction, then the assumption must be wrong.
4. So the original statement must be true.

A contradiction is something logically impossible, such as:

• getting both true and false at the same time,
• concluding that a number is both even and odd,
• reaching a result that disagrees with a known fact.

This method is based on a simple logic idea: if assuming “not true” leads to nonsense, then the original statement must be true.

3. When should you use each method?

Use a counterexample when you want to show a statement is false.

Use proof by contradiction when you believe a statement is true, but proving it directly is difficult. It is especially helpful for statements involving words like:

• no
• never
• cannot
• there is no
• irrational, infinite, or unique

4. Counterexamples and universal statements

Many false conjectures are written in the form “For all ... , something is true.” In logic, this is called a universal statement.

For example:

“For all real numbers \(x\), if \(x^2 = x\), then \(x = 1\).”

To test this, we look for a value of \(x\) that satisfies \(x^2 = x\) but does not satisfy \(x = 1\).

Solving:

$$x^2 = x$$ $$x^2 - x = 0$$ $$x(x-1)=0$$

So \(x=0\) or \(x=1\). Since \(x=0\) makes the condition true but does not give \(x=1\), the number \(0\) is a counterexample.

So the original statement is false.

5. Worked Example 1: Using a counterexample

Statement: If \(n\) is an integer, then \(n^2 > n\).

At first, this may seem true for many positive integers:

• if \(n=2\), then \(n^2=4>2\)
• if \(n=3\), then \(n^2=9>3\)

But the statement says this must happen for every integer.

Try \(n=1\):

$$1^2 = 1$$

This is not greater than 1, so \(n=1\) is a counterexample.

We could also use \(n=0\):

$$0^2 = 0$$

This is also not greater than 0.

Conclusion: The statement is false.

6. Worked Example 2: Counterexample with sets

Statement: For all sets \(A\) and \(B\), if \(A \subseteq B\), then \(B \subseteq A\).

This statement claims that whenever every element of \(A\) is in \(B\), then every element of \(B\) must also be in \(A\). That is not always true.

Choose:

$$A = \{1,2\}, \quad B = \{1,2,3\}$$

Now check the first part:

• Every element of \(A\) is in \(B\), so \(A \subseteq B\) is true.

Now check the conclusion:

• \(3 \in B\), but \(3 \notin A\), so \(B \subseteq A\) is false.

So these sets form a valid counterexample.

Conclusion: The statement is false.

7. Structure of a contradiction proof

When writing a proof by contradiction, it helps to follow a clear pattern:

1. State what you want to prove.
2. Assume the opposite is true.
3. Use definitions, algebra, and logic carefully.
4. Reach a contradiction.
5. Conclude that the original statement is true.

You should always make the contradiction clear. Do not stop too early. Explain exactly why the result is impossible.

8. Worked Example 3: Proof by contradiction with even and odd numbers

Statement: There is no integer that is both even and odd.

We will prove this by contradiction.

Step 1: Assume the opposite. Suppose there is an integer \(n\) that is both even and odd.

Step 2: Use the definitions.

If \(n\) is even, then

$$n=2a$$

for some integer \(a\).

If \(n\) is odd, then

$$n=2b+1$$

for some integer \(b\).

Since both expressions equal \(n\), we get

$$2a = 2b+1$$

Subtract \(2b\) from both sides:

$$2a-2b=1$$ $$2(a-b)=1$$

The left side is an even number, because it is 2 times an integer. But the right side is 1, which is odd.

This says an even number equals an odd number, which is impossible.

So our assumption was false.

Conclusion: No integer can be both even and odd.

9. Worked Example 4: Proof by contradiction that \(\sqrt{2}\) is irrational

This is a famous example of proof by contradiction.

Statement: \(\sqrt{2}\) is irrational.

Step 1: Assume the opposite. Suppose \(\sqrt{2}\) is rational.

Then it can be written as a fraction in simplest form:

$$\sqrt{2}=\frac{a}{b}$$

where \(a\) and \(b\) are integers, \(b \ne 0\), and the fraction is fully simplified. That means \(a\) and \(b\) have no common factor greater than 1.

Step 2: Square both sides.

$$2 = \frac{a^2}{b^2}$$ $$a^2 = 2b^2$$

This means \(a^2\) is even, since it equals 2 times an integer.

If \(a^2\) is even, then \(a\) must also be even. So let

$$a=2k$$

for some integer \(k\).

Substitute into the equation:

$$a^2 = 2b^2$$ $$(2k)^2 = 2b^2$$ $$4k^2 = 2b^2$$ $$2k^2 = b^2$$

So \(b^2\) is even, which means \(b\) is even too.

Now both \(a\) and \(b\) are even. That means they are both divisible by 2.

But this contradicts the fact that \(\frac{a}{b}\) was in simplest form.

So our assumption must be false.

Conclusion: \(\sqrt{2}\) is irrational.

10. How contradiction connects to logic

In formal logic, proof by contradiction often works with the idea of negation.

If you want to prove a statement \(P\), you assume \(\neg P\) and show that this leads to a contradiction. Symbolically, the pattern is:

$$\neg P \Rightarrow \text{contradiction}$$

Therefore, \(\neg P\) must be false, so \(P\) is true.

This is useful in set theory and logic because many mathematical statements are built from conditions such as:

• if ... then ...
• for all ...
• there exists ...
• there does not exist ...

Understanding the negation of a statement is important.

For example:

• The negation of “All elements of set \(A\) are in set \(B\)” is “There exists at least one element of \(A\) that is not in \(B\).”
• The negation of “There is no integer with property \(X\)” is “There exists an integer with property \(X\).”

11. Common mistakes to avoid

• Using examples instead of a proof: Checking many examples does not prove a universal statement is always true.
• Using an invalid counterexample: Make sure your example fits all parts of the original claim.
• Not stating the contradiction clearly: In a contradiction proof, explain exactly what impossible result was reached.
• Assuming what you are trying to prove: Do not accidentally use the conclusion as part of your reasoning.
• Confusing false statements with unproven statements: A statement is not false just because you have not proved it yet.

12. Quick comparison

• Counterexample: used to disprove a statement.
• Contradiction: used to prove a statement by showing its negation is impossible.

You can think of them this way:

• A counterexample says, “Here is one case where the claim fails.”
• A contradiction proof says, “If the claim were false, something impossible would happen.”

13. Final summary

A counterexample is a single valid example that shows a general statement is false. It is most useful when a statement claims something is true in every case.

Proof by contradiction is a method for proving a statement by assuming the opposite and then reaching a logical impossibility. This method is especially useful in formal logic, number theory, and set theory.

To use these methods well, focus on definitions, be precise, and always explain your reasoning clearly. In higher-level mathematics, strong arguments matter just as much as correct answers.