Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

MATH 2030 > Chapter 4 - Relations > Flashcards

Chapter 4 - Relations Flashcards

1
Q

Define: Suppose X and Y are sets. The cartesian product of X with Y, denoted X x Y, is…

A

the set of all ordered pairs (a,b) where a is in X and b is in Y

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Define: A binary relation R on a set X is…

A

a subset of the cartesian product X x X, that is, a set of ordered pairs (a_1, a_2) where a_1 and a_2 are in X.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

A binary relation (X, R) is REFLEXIVE provided that…

A

aRa, ∀a∈X
and
its diagraph has a loop at every vertex

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

A binary relation (X, R) is NONREFLEXIVE provided that…

A

it is not reflexive (i.e. ∃a s.t. ~aRa)
and
its diagraph has at least one loop missing

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

A binary relation (X, R) is IRREFLEXIVE provided that…

A

~aRa, ∀a∈X
and
its diagraph has no loops

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

A binary relation (X, R) is SYMMETRIC provided that…

A

aRb ⇒ bRa, ∀a,b∈X

in a diagraph, if there is an arc from u to v whenever there is an arc from v to u, we can replace the arcs with a single non-directed line called an edge

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

A binary relation (X, R) is NONSYMMETRIC provided that…

A

it is not symmetric (i.e. ∃a,b∈X s.t. aRb ⇏ bRa)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

A binary relation (X, R) is ASYMMETRIC provided that…

A

aRb ⇒ ~bRa, ∀a,b∈X
and
its diagraph has no loops and that for all vertices u and v, d(u,v) + d(v,u) ≠ 2

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

A binary relation (X, R) is ANTISYMMETRIC provided that…

A

aRb & bRa ⇒ a = b, ∀a,b∈X
and
its diagraph may have loops, but for vertices u≠v, d(u,v) + d(v,u) ≠ 2

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

A binary relation (X, R) is TRANSITIVE provided that…

A

aRb & bRc ⇒ aRc, ∀a,b,c∈X
and
in a diagraph, if there is an arc from vertex u to v and an arc from vertex v to w, then there will be an arc from vertex u to w

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

A binary relation (X, R) is NONTRANSITIVE provided that…

A

it is not transitive (i.e. ∃a,b,c∈X s.t. aRb & bRc ⇏ aRc)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

A binary relation (X, R) is NEGATIVELY TRANSITIVE provided that…

A

~aRb & ~bRc ⇒ ~aRc, ∀a,b,c∈X

OR

aRc ⇒ aRb OR bRc, ∀a,b,c∈X

In other words, the relation “not in R” is defined on the set X, is transitive (ex. “greater than” on a set of real numbers is negatively transitive because “not in R” = “not greater than” or “less than or equal to,” which are both transitive)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

A binary relation (X, R) is STRONGLY COMPLETE provided that…

A

aRb OR bRa, ∀a,b∈X

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

A binary relation (X, R) is COMPLETE provided that…

A

aRb OR bRa, ∀a≠b∈X

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Being antisymmetric versus asymmetric means that…

A

“equality of elements” is allowed, hence the fact that antisymmetric diagraphs may have loops

every asymmetric binary relation is antisymmetric but the converse is false

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Define: A relation R is called an equivalence relation iff…

A

R is reflexive, symmetric, and transitive

Let R be an equivalence relation on a set A. Then for every a∈A, define the equivalence class by [a] = {x∈A | xRa}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Theorem: let R be an equivalence relation on a set A, then…

A

for every a,b∈A, either [a] = [b] or [a] ∩ [b] = ∅

using an equivalence relation on a set, we can always partition the set into the corresponding equivalent classes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Define: A relation R on A is called partial order iff…

A

R is reflexive, antisymmetric, and transitive

The pair (A,R) is called a “partially ordered set” or “POSET”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

in a relation R on A, we say that a,b∈A are comparable iff…

A

either aRb or bRa

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

in a relation R on A, we say that a,b∈A are incomparable iff…

A

~aRb & ~bRa

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Theorem: the diagraph of a partial order has ____ cycles

A

The diagraph of a partial order has NO cycles (except for loops)

cycles are NOT partial order because they are NOT antisymmetric

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Define: A strict partial order is…

A

irreflexive, antisymmetric, and transitive

the irreflexive and antisymmetric properties can be reduced to simply asymmetric, hence a binary relation R on a set A is irreflexive and antisymmetric iff it is asymmetric

23
Q

Define: A Hasse diagram is…

A

a graph obtained from drawing the diagraph of the relation with all the edges pointing upward, loops are removed, all edges that are implied by transitivity are removed, and all direction of the edges are removed

24
Q

Define: Let (A,R) be a poset and x∈A. Define x to be maximal iff…

A

∀y∈A, xRy ⇒ y = x (i.e. it is not smaller than another element/it is the largest element)

may have more than one maximal

25
Q

Define: Let (A,R) be a poset and x∈A. Define x to be minimal iff…

A

∀y∈A, yRx ⇒ y = x (i.e. it is not bigger than another element/it is the smallest element)

may have more than one minimal

26
Q

Define: Let (A,R) be a poset and x∈A. Define x to be maximum iff…

A

∀y∈A, yRx

if it exists, denote maximum as ^1 (1 hat)

can only have one!

27
Q

Define: Let (A,R) be a poset and x∈A. Define x to be minimum iff…

A

∀y∈A, xRy

if it exists, denote minimum as ^0 (0 hat)

can only have one!

28
Q

Define: A linear order is a partial order iff…

A

every pair of elements in A are comparable

recall: to be comparable, for a,b∈A either aRb or bRa (or both)

recall: a relation R on a set A is called a partial order if A is reflexive, antisymmetric, and transitive

ex. ≤, ≥ on a set of real numbers

29
Q

Define: A STRICT linear order is a STRICT partial order iff…

A

every pair of elements of A are comparable

recall: to be comparable, for a,b∈A either aRb or bRa (or both)

recall: a relation R on a set A is called a strict partial order if A is irreflexive, antisymmetric, and transitive

ex. <, > on a set of real numbers

30
Q

Theorem: a diagraph D = (V, E) is an interval order iff…

A

D has no loops and if for any (a,b)∈E and (c,d)∈E, either (a,d)∈E OR (c,b)∈E

31
Q

Lemma: Let R_1 and R_2 be partial orders on a set A. The relation R_1∩ R_2 = …

A

{(a,b)∈AxA | (a,b)∈R_1 and (a,b) ∈ R_2} is a partial order

i.e. if R_1 and R_2 are partial orders on a set A, then their intersection R_1∩ R_2 is a partial order also, such that the ordered pairs (a,b) in R_1 is also in R_2

32
Q

Define: Given relations R_1 and R_2 on a set A, R_2 is called an extension of R_1 iff…

A

R_1⊆R_2

If an extension is itself a linear extension, it is called a linear extension

33
Q

Define: in a partial order (A,R), a chain is…

A

a set C⊆A for which every pair of elements in C are comparable

34
Q

Define: in a partial order (A,R), an antichain is…

A

a set L⊆A for which none of the elements in L are comparable

35
Q

Lemma: Any non-empty finite poset contains a _____ element and a _____ element

A

Any non-empty finite poset contains a MAXIMAL element and a MINIMAL element

36
Q

State the Szpilrajn Extension Theorem:

A

Every partial order has a linear extension. Moreover, if (A,R) is a poset and x,y∈A are incomparable, then there is a linear extension L with xLy.

37
Q

State the Szpilrajn Extension Theorem for a STRICT partial order:

A

If (X,R) is a partial order and F = {L: L is a linear extension of (X,R)}, then R = ∩L (big intersection)

i.e. F is the set of all linear extensions of a partial order (X,R)

38
Q

Define: the dimension of a poset (X, R), denoted dim(X,R), is…

A

the smallest t such that there exists linear extensions L_1,…L_t with R = ∩L_t (big intersection from i = 1 to t)

i.e. the smallest number t of linear extensions Li such that the intersection of Li’s = R (the original poset)

39
Q

State the Dilworth Theorem:

A

V1: Let (A,R) be a poset and suppose the largest chain has size j. Then there are j antichains X_1,…,X_j that for all i≠k, X_i∩X_k = ∅ and A = X_1 ∪ X_2∪…∪X_j

V2: Let (A,R) be a poset and suppose that the largest antichain has j elements. Then there are j chains c_1,…,c_j with the property that if i≠k, c_i∩c_k = ∅ and A = c_1 ∪ c_2∪…∪c_j

40
Q

Define: let (A, R) be a poset and U ⊆ A. x∈A is an UPPER BOUND of U iff…

A

∀u∈U, uRx (where u≤x)

41
Q

Define: let (A, R) be a poset and U ⊆ A. x∈A is a LEAST UPPER BOUND of U, denoted lub(U) iff…

A

x is an upper bound for U and if y is an upper bound for U, xRy where x≤y

least upper bound, lub(U)
OR
supremum, sup(U)

42
Q

Define: let (A, R) be a poset and U ⊆ A. x∈A is a LOWER BOUND for U iff…

A

∀u∈U, xRu (where x≤u)

43
Q

Define: let (A, R) be a poset and U ⊆ A. x∈A is a GREATEST LOWER BOUND in U iff…

A

x is a lower bound in U and if y is a lower bound for U, yRx where y≤x

greatest lower bound, glb(U)
OR
infimum, inf(U)

44
Q

What is the difference between the supremum and maximum of U?

A

The maximum of U must be in U, whereas the supremum of U need not be in U

45
Q

Define: a poset (L, R) is called a lattice iff…

A

∀a,b∈L, sup({a,b}) and inf({a,b}) both exist

a∧b = inf{a,b} = “the meet of a and b”
a∨b = sup{a,b} = “the join of a and b”

46
Q

Theorem: Every finite lattice has a…

A

maximum and a minimum element

47
Q

What are the 5 properties that a lattice MUST have?

A
  1. Idempotent
  2. Commutativity
  3. Associativity
  4. Absorption
  5. Order-Preserving
48
Q

What are the 2 properties that a lattice MAY have (not necessarily must always have)?

A
  1. Distributivity
  2. Complement
49
Q

Define: Let (L, R) be a lattice and x∈L. An element c∈L is called COMPLEMENT OF X iff…

A

x∨c = 1^ (1 hat) AND x∧c = 0^ (0 hat)

if every element of (L,R) has a complement, then (L,R) is a complemented lattice

50
Q

Define: if a lattice (L, R) is distributive AND complemented, then it is called a…

A

boolean algebra

i.e. a lattice is a boolean algebra iff (L,R) is distributive and complemented

51
Q

Theorem: Let (L,R) be a boolean algebra. For every x∈L, x has a…

A

unique complement

52
Q

Theorem: a lattice (L,R) is called MODULAR iff…

A

whenever xRz, then ∀y∈L, we have x∨(y∧z) = (x∨y)∧z

53
Q

Theorem: Let (L,R) be a distributive lattice. Then (L,R) is…

A

modular

MATH 2030 (2 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions