Sets and Relations

Question 1

What is naive set theory? What is its problem?

Answer 1

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

Question 2

Two sets A and B are equal iff

Answer 2

For all elements x, x is is in both A and B

Question 3

What does it mean to be a subset of another set? What is the notation?

Answer 3

Question 4

What is the roster method for representing sets?

Answer 4

Question 5

What is the set-builder notation for representing sets?

Answer 5

Question 6

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?

Answer 6

Question 7

Memorize the following important sets of numbers:

Answer 7

Question 8

What is the difference between open and closed brackets for ranges of numbers?

Answer 8

Question 9

Is the empty set a subset of any set?

Answer 9

Yes

Question 10

What is a subset of a set that is different from the set itself called? What is the notation?

Answer 10

A proper subset

Question 11

What is a power set?

Answer 11

Question 12

The power set of a set A P(A) has how many elements?

Answer 12

2^n elements

Question 13

What does the intersection of two elements mean? What is the notation? What does it look similar to?

Answer 13

The notation looks similar to the AND connective:›

Question 14

What does the union of two sets mean? What is the notation? What is it similar to?

Answer 14

Is it similar to the disjunction connective.

Question 15

What is the complement of a set?

Answer 15

Question 16

The complement of any universe is

Answer 16

The empty set

Question 17

The complement of the empty set is

Answer 17

The given universe

Question 18

The difference between two sets is

Answer 18

The notation is the \ backslash

Question 19

To prove set identities:

Answer 19

Question 20

Consider this example of proving set identities:

Answer 20

Question 21

Go over the relationships between sets and logic:

Answer 21

Question 22

What is cardinality?

Answer 22

The cardinality of a set is the number of elements that are in the set.

Question 23

What is a tuple?

Answer 23

Question 24

What are cartesian products?

Answer 24

Question 25

Examine the following examples of cartesian products:

Answer 25

Question 26

Consider the following examples of binary relations:

Answer 26

Question 27

What is the notation for binary relations?

Answer 27

Question 28

How many distinct binary relations are there on a relation A?

Answer 28

2 to the power of the cardinality of A squared

Question 29

What is reflexivity of relations?

Answer 29

Question 30

What is irreflexivity of relations?

Answer 30

Question 31

Is it possible for a relation to be neither irreflexive of reflexive?

Answer 31

Yes

Question 32

Is it possible for a relation to be both reflexive AND irreflexive

Answer 32

No

Question 33

What is symmetry of relations?

Answer 33

Question 34

What is antisymmetry of relations?

Answer 34

Question 35

What is asymmetry of relations?

Answer 35

Question 36

What is the difference between asymmetry and antisymmetry?

Answer 36

Question 37

What is transitivity of relations?

Answer 37

$

Question 38

What is the inverse relation?

Answer 38

Question 39

What is composition of relations?

Answer 39

Question 40

What are powers of relations?

Answer 40

Question 41

How are relations represented via matrices?

Answer 41

Question 42

What is the correlation between relation properties and matrices?

Answer 42

Question 43

Examine the properties of the following matrix:

Answer 43

Question 44

How are relations represented via graphs?

Answer 44

Question 45

What are the properties relations representation through graphs?

Answer 45

Question 46

Examine the follwing examples of relations represented by graphs:

Answer 46

Question 47

What is an equivalence relation?

Answer 47

Question 48

What is an equivalence class?

Answer 48

Question 49

Congruence modulo m is an example of...

Answer 49

Equivalence class$

Question 50

What is a partition of a set?

Answer 50

Question 51

What are partial orderings?

Answer 51

Question 52

What are strict orderings?

Answer 52

Question 53

What is the difference between partial and strict orderings?

Answer 53

Question 54

Examine this example of the power set poset:

Answer 54

Question 55

What are hasse diagrams?

Answer 55

Question 56

What are total orders?

Answer 56

Question 57

Examine this example of a hasse diagram of a total order:

Answer 57