A set is a group of different items. For example a set of numbers consisting of 3, 6 and 9 can be represented by {3, 6, 9}. You can make two types of claims on a set, universal claims which make a claim about all the elements of a set and existential claims that make a claim about at least one of the elements of a set.
For example we can consider a set S = {1, 3, 5, 7, 9}. An example of a universal claim is 'All numbers in S are odd' which would evaluate to True. An example of an existential claim is 'Some numbers in S are greater than 10' which would evaluate to False.
Here is how to evaluate universal or existential claims:
- To verify a universal claim check that every element satisfies the claim.
- To falsify a universal claim just find one element that doesn't satisfy the claim.
- To verify an existential claim just find one element that satisfies the claim.
- To falsify an existential claim check that every element doesn't satisfy the claim.
Here is a list of symbols that can be used to express a claim:
- ∀: For all
- ∈: Set membership (is an element of)
- ∃: There exists
- ⇒: Implies
So for example if we consider O to be the set of odd numbers we can write a statement:
∀x ∈ S, O(x). which means 'for all numbers x in S, x is odd.'
An implication is a statement about the relationship between two sets and is expressed in the form 'If P, then Q' where P is called the antecedent and Q is called the consequent. For example lets consider this Implication 'If I work hard then I will succeed.' There are four possible scenarios presented by this statement:
- I work hard and I do succeed
- I work hard and I don't succeed
- I don't work hard and I do succeed
- I don't work hard and I don't succeed
Only one of these expressions falsifies the implication. 'I work hard and I don't succeed' is the only counterexample to the implication. More generally in the implication 'If P, then Q' if P is true and Q is false the implication is false, none of the other scenarios make the implication false.
If you reverse the direction you get the converse of the original implication. Lets define P(n): n is odd, and Q(n): 2n is even, and consider: ∀n ∈ ℕ, P(n) ⇒ Q(n). This implication states that 'if a number n is odd, then 2n is even'. The converse of this implication would be: ∀n ∈ ℕ, Q(n) ⇒ P(n). This states that 'if 2n is even, then n is odd'. The converse is false and a counterexample is when n=2, 2n is 4 which is even so P is true, but n is 2 which is not odd so Q is false which makes the converse false. If an implication and its converse are both true then they are both the same set consisting of the same elements.
Another symbol ¬ means not, so ¬P means not P. When you negate an implication and reverse it then you get its contrapositive. So using our last example the contrapositive would be:
∀n ∈ ℕ, ¬Q(n) ⇒ ¬P(n) which means 'if 2n is not even, then n is not odd'.
The only way to falsify an implication is to find a counterexample where P is true and Q is false. If you have an implication where the antecedent is always false, the implication is true. For example the implication 'Everyone more than 10ft tall can fly' is true as there are no counterexamples to it.
Here is a list of symbols that can be used to express a claim:
- ∀: For all
- ∈: Set membership (is an element of)
- ∃: There exists
- ⇒: Implies
So for example if we consider O to be the set of odd numbers we can write a statement:
∀x ∈ S, O(x). which means 'for all numbers x in S, x is odd.'
An implication is a statement about the relationship between two sets and is expressed in the form 'If P, then Q' where P is called the antecedent and Q is called the consequent. For example lets consider this Implication 'If I work hard then I will succeed.' There are four possible scenarios presented by this statement:
- I work hard and I do succeed
- I work hard and I don't succeed
- I don't work hard and I do succeed
- I don't work hard and I don't succeed
Only one of these expressions falsifies the implication. 'I work hard and I don't succeed' is the only counterexample to the implication. More generally in the implication 'If P, then Q' if P is true and Q is false the implication is false, none of the other scenarios make the implication false.
If you reverse the direction you get the converse of the original implication. Lets define P(n): n is odd, and Q(n): 2n is even, and consider: ∀n ∈ ℕ, P(n) ⇒ Q(n). This implication states that 'if a number n is odd, then 2n is even'. The converse of this implication would be: ∀n ∈ ℕ, Q(n) ⇒ P(n). This states that 'if 2n is even, then n is odd'. The converse is false and a counterexample is when n=2, 2n is 4 which is even so P is true, but n is 2 which is not odd so Q is false which makes the converse false. If an implication and its converse are both true then they are both the same set consisting of the same elements.
Another symbol ¬ means not, so ¬P means not P. When you negate an implication and reverse it then you get its contrapositive. So using our last example the contrapositive would be:
∀n ∈ ℕ, ¬Q(n) ⇒ ¬P(n) which means 'if 2n is not even, then n is not odd'.
The only way to falsify an implication is to find a counterexample where P is true and Q is false. If you have an implication where the antecedent is always false, the implication is true. For example the implication 'Everyone more than 10ft tall can fly' is true as there are no counterexamples to it.
