Discrete Math Test 2

Front 1

A relation on a set A is called an equivalence relation on A if

Back 1

R is reflexive, symmetric, and transitive.

Front 2

What do you call a ∈ A, the set [a] = {x ∈ A : a R x}

Back 2

The equivalence class of a

Front 3

Any element in an equivalence class is called a _____________ of the class

Back 3

Representative

Front 4

Let A be a set and § a collection of subsets of A. We say S is apartition if

Back 4

No element in a partition of § collection is part of another partition.
The union of all partitions is equal to set A

Front 5

Any equivalence relation on a set A defines a _______________ on A and
vice-versa.

Back 5

partition

Front 6

The smallest equivalence relation
on A that contains R.

Back 6

Re = t(s(r(R))

Front 7

A relation on a set A is called a partial ordering on A if R is___________________, ________________, ____________. If in addition, either a R b or b R a for every a, b ∈ A, the R is called a ______________

Back 7

reflexive, antisymmetric, and transitive.

Total order

Front 8

A partial order is also known as a

Back 8

poset

Front 9

Describe a total order

Back 9

In a poset every element relates in one direction.

So either aRb or bRa for every a,b element of A

Front 10

Is poset (Z+,|) a chain?

Back 10

No

ex: 2|7 and 7|2 do not work.

Front 11

Is poset (Z+,<=) a chain?

Back 11

Yes

Front 12

Is the poset (P(S), , ⊆) a chain?

Back 12

No.

S:={1, 2, 3, 4}

A:={1,2}

B:={3,4}

ACB false

BCA false

Front 13

A relation R on A is called a pseudo-order if R is:

Back 13

irreflexive and transitive.

Front 14

is the poset (Z+,<) a pseudo-order?

Back 14

yes

Front 15

Given a poset (A,≺= ), the new relation ≺ defined by x ≺ y if x ≺= y and x =/= y is a

Back 15

pseudo-order

Front 16

Give an example of a partial order which is not a total order.

Back 16

the division relation

2|7 or 7|2 does not hold

Front 17

if a poset is a total order then its also a

Back 17

Chain

Front 18

Give an example of a pseudo-ordering which is not a partial order.

Back 18

The relation < or > because its irreflexive

Front 19

Give an example of a chain which is not well ordered

Back 19

(Z,<=) , R={x e Z : x <0}

Not every subset of Z has a least element because Z is not finite, nor is the relation.

Front 20

Define least element

Back 20

a element of A such that a <= b for all b element of A

Front 21

Define greatest element

Back 21

a element of A such that b <= a for all b element of A

Front 22

Define minimal element

Back 22

There does not exist element b in A such that element a in A is b <= a, where a does not equal b.

Front 23

Define maximal element.

Back 23

There does not exist element b in A such that element a in A is a <= b, where a does not equal b.

Front 24

There cannot be more than one minimal element or maximal element in a poset

Back 24

false

Front 25

There can be more than one minimal or maximal element in a poset

Back 25

true

Front 26

Let (A,<=) be a poset and S ⊆ A

Define an upper bound

Back 26

An element a is called an upper bound on S if s<= a for all s element of S.

Front 27

Let (A,<=) be a poset and S ⊆ A

Define an lower bound

Back 27

An element a is called a lower bound on S if a <= s for all s element of S.

Front 28

Let (A,<=) be a poset and S ⊆ A

Define an least upper bound LUB

Back 28

An upper bound a on S is called the least upper bound on S if for any other upper bound b, a <=b.

Front 29

Let (A,<=) be a poset and S ⊆ A

Define an greatest lower bound GLB

Back 29

A lower bound a on S is called the greatest lower bound on S if for any other lower bound b, b <= a

Front 30

What makes poset (A, <=) a lattice?

Back 30

if every pair of elements has a least upper bound and a greatest lower bound in A.

Front 31

If you draw a hasse diagram and a pair of elements has more than one LUB or GLB in the same level. is it a lattice?

Back 31

No

Front 32

A chain (A, R) is well ordered if

Back 32

every non-empty subset of A has a least element.

Front 33

If a poset (A,<=) has a least element in every non-empty subset then <= is _________ on A

Back 33

Total ordering

Front 34

lexicographic is the same as

Back 34

alphabetizing

Front 35

What is a Hasse Diagram

Back 35

Is a simplified version of the diagraph where

redundant edges are removed

arrows are removed

and arcs point up

Front 36

Let (A, <=) be poset
If A has more than one minimal element, then A has no least element

Back 36

true

Front 37

Let (A, <=) be poset
If A has more than one maximal element, then A has no greatest element.

Back 37

true

Front 38

Let (A, <=) be poset

If a element of A is the least element it cannot be a minimal element.

Back 38

false, it is also a minimal element.

Front 39

Let (A, <=) be poset

If a element of A is the greatest element, then its also a maximal element

Back 39

true

Front 40

Suppose (A, <= ) is a finite, non-empty poset. Then A has a ________________.

Back 40

minimal element