Ch 1 Sets, Relations And Arguments Flashcards
What is a set?
A collection of objects
What are the objects in a collection called?
Elements of that set
When are sets identical?
Iff they have the same elements
What is the set that contains no elements called?
The empty set
Definition of a binary relation?
A set is a binary relation if and only if it contains only ordered pairs
The empty set is a binary relation as it does not contain anything that is not an ordered pair
A binary relation is reflexive on a set S iff
For all elements d of S the pair is an element of R
A binary relation R is symmetric on a set S iff
For all elements d, e of S: if € R then € R
A binary relation R is asymmetric on a set S iff
For no elements d,e of S: €R and €R
A binary relation R is antisymmetric on a set S iff
for no two distinct (that is, different) elements d,e of S:
€R and €R
A binary relation R is transitive on a set S iff
For all elements d,e,f of S:
if €R and €R, then also €R
A binary relation R is …
Symmetric iff it is symmetric on all sets
Asymmetric iff it is asymmetric on all sets
Antisymmetric iff it is antisymmetric on all sets
Transitive if it is transitive on all sets
What properties does the empty relation have?
It’s diagram is empty
It is reflexive on the empty set but on no other set
It is symmetric as there is no arrow for which there is not any arrow in the opposite direction.
It is also asymmetric and antisymmetric because there is no arrow for which there is an arrow in the opposite direction.
It is also transitive
What is an equivalence relation?
A binary relation R is an equivalence relation on S iff R is reflexive on S, symmetric on S and transitive on S
A binary relation is a function iff
for all d,e,f: if €R and €R then e=f
The domain of a function R is the set
{ d: there is an e such that €R }