Maths

Question 1

What is an equivalence relation?

Answer 1

A relation that is:
- Reflexive: Each element is related to itself
- Symmetric: If a is related to b, then b is related to a
- Transitive: If a and b, and b and c are realted, then a and c are related

Question 2

What is an equivalence class and a quotient set?

Answer 2

Equivalence class:
- The set of all elements that are equivalent to each other
Quotient set:
- The set of all distinct equivalence classes

Question 3

What is a Poset?

Answer 3

• Partially ordered set
• Reflexive
• Anti-symmetric
• Transitive

Question 4

What is anti-symmetry?

Answer 4

• Two elements cannot be less than or equal to each other unless they are equal
• Multual related-ness implied equality
• No closure (would require removing elements)

Question 5

What is the difference between total and partial order?

Answer 5

• In total order, every element is comparable, unlike partial order

Question 6

Give the definition of minimal and maxiamal?

Answer 6

• Minimal: Nothing strictly smaller than
• Maximal: Nothing strictly greater than
• Posets can have many minimal maximal elements

Question 7

Give the definition of greatest and least element?

Answer 7

• Greatest: Greater than or equal to everything
• Least: Less than or equal to everything
• Only one exists of each

Question 8

Give the defintion of upper and lower bound?

Answer 8

• Upper Bound: if every element in a subset of a poset is less than or equal than it
• Lower Bound: if every element in a subset of a poset is greater than or equal to it
• Doesn’t have to be in the subset