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.
