Sets and Relations Flashcards
What is naive set theory? What is its problem?
A set is a (unordered) collection of objects, called elements or members of the set. The set is said to contain its elements. The notation a ∈ S means that the object a is an element of the set S. The notation a ∉ S means that a is not an element of the set S.
Problem:
- a set can contain other sets as elements.
- a set can contain itself as an element
Two sets A and B are equal iff
For all elements x, x is is in both A and B
What does it mean to be a subset of another set? What is the notation?
What is the roster method for representing sets?
What is the set-builder notation for representing sets?
What is the representation of the empty set? The universal set? What is the difference between the empty set and the set containing the empty set?
Memorize the following important sets of numbers:
What is the difference between open and closed brackets for ranges of numbers?
Is the empty set a subset of any set?
Yes
What is a subset of a set that is different from the set itself called? What is the notation?
A proper subset
What is a power set?
The power set of a set A P(A) has how many elements?
2^n elements
What does the intersection of two elements mean? What is the notation? What does it look similar to?
The notation looks similar to the AND connective:›
What does the union of two sets mean? What is the notation? What is it similar to?
Is it similar to the disjunction connective.
What is the complement of a set?
The complement of any universe is
The empty set
The complement of the empty set is
The given universe
The difference between two sets is
The notation is the \ backslash
To prove set identities:
Consider this example of proving set identities:
Go over the relationships between sets and logic:
What is cardinality?
The cardinality of a set is the number of elements that are in the set.
What is a tuple?
What are cartesian products?
Examine the following examples of cartesian products:
Consider the following examples of binary relations:
What is the notation for binary relations?
How many distinct binary relations are there on a relation A?
2 to the power of the cardinality of A squared
What is reflexivity of relations?
What is irreflexivity of relations?
Is it possible for a relation to be neither irreflexive of reflexive?
Yes
Is it possible for a relation to be both reflexive AND irreflexive
No
What is symmetry of relations?
What is antisymmetry of relations?
What is asymmetry of relations?
What is the difference between asymmetry and antisymmetry?
What is transitivity of relations?
$
What is the inverse relation?
What is composition of relations?
What are powers of relations?
How are relations represented via matrices?
What is the correlation between relation properties and matrices?
Examine the properties of the following matrix:
How are relations represented via graphs?
What are the properties relations representation through graphs?
Examine the follwing examples of relations represented by graphs:
What is an equivalence relation?
What is an equivalence class?
Congruence modulo m is an example of…
Equivalence class$
What is a partition of a set?
What are partial orderings?
What are strict orderings?
What is the difference between partial and strict orderings?
Examine this example of the power set poset:
What are hasse diagrams?
What are total orders?
Examine this example of a hasse diagram of a total order:
