Sets And Proofs Flashcards
Set
A set is a collection of objects
a∈A
a belongs to the set A.
s ∈/ A
s does not belong to the set A
What makes two sets equal?
two sets are equal if they contain exactly the same elements
S ⊆ A.
S is a subset of A
Subset
If A is a set, we say S is a subset of A if every element of S also belongs to A.
P ⇒ Q
Statement P implies statement Q
The negation of a statement
The opposite statement
P ̄
“not P”
What does P ⇒ Q tell us about the negations
Q ̄ ⇒ P ̄.
Proof by contradiction process
- Negate the statement
- Assume the negation is true
- Manipulate the expression until you get something that is definitely false
- This is a contradiction so the negation of the statement is false
- Thus the statement must be true
How do we show that a statement is not true?
Come up with a single counter-example
What is the symbol ∃ called?
the existential quantifier
What does the symbol ∃ mean?
“there exists”
How do you prove a statement beginning with “there exists”?
find a single object that has the required property.
What is the symbol ∀ called?
the universal quantifier
What does the symbol ∀ mean?
“for all”
How do you prove a statement beginning with “for all”?
a general argument is required.
What is the negation of a statement beginning with “there exists”?
The statement beginning with “there does not exist”
OR
The statement beginning with “for all” with the negation of the conclusion
What is the negation of a statement beginning with “for all”?
the statement beginning with “not for all”
OR
the statement beginning with “there exists” with the negation of the conclusion
∅
The empty set
The empty set
the set with no elements in it
What can we say about a statement that begins with ∀ x ∈ ∅?
It is automatically true.
What can we say about a statement that begins with ∃ x ∈ ∅?
It is automatically false
