This tag is intended for questions concerning partial orders, equivalence relations, properties of relations (transitive, symmetric,...), composition of relations and similar stuff. More-or-less the things about relations taught in the first elementary set theory or discrete math course.

learn more… | top users | synonyms

1
vote
2answers
1k views

Proving a relation is partial ordering

I have a problem proving that a very simple relation is partial ordering. It is defined explicitly (i.e. with pairs of numbers) and I have no idea how to do a formal proof for its antisymmetric ...
2
votes
1answer
1k views

Amount of transitive relations on a finite set

In counting the amount of relations on finite sets, we can quite easily count the amount of reflexive and symmetric relations on a finite set. We just consider (in accordance with the definition of a ...
0
votes
1answer
131 views

Quotient set univocally defined

I know that what I am going to ask is pretty basic, borderline stupid, nevertheless it is bugging me. By definition I know that given a set $A$ and a equivalence relation $\rho$, then the items ...
1
vote
1answer
119 views

Is the relation $x+3y = 0$ antisymmetric for all real numbers?

I don't think so, because it is never $aRb$ nor $bRa$ and it is never $aRa$ or $bRb$, thus it is always false, but I don't know if I understood what antisymmetric means exactly.
1
vote
1answer
94 views

How come the relation $\subseteq $ on the power set $2^N$ is antisymmetric?

where $2^N$ is the power set with $n$ elements (subsets). Does it hold true to any set or just the power set $2^N$?
1
vote
1answer
75 views

What's the payoff associated with the definition of a relation as an ordered triple?

We can define a binary relation as a set of ordered pairs. Alternatively, we can call the set of ordered pairs the "graph" of the relation, and define the relation itself as a triple $(X,Y,f)$, where ...
1
vote
1answer
245 views

Transitive closure of binary relation

How would you make a transitive closure on something like this: Among all students in a classroom we have a binary relation $\mathcal R$. Student A is in relation with student B, formally (A,B) $\in$ ...
1
vote
2answers
1k views

Finding all partial order relations on a set

Suppose I have a set $A$ such that $A$ = $\{1, 2, 3, 4, 5\}$ (or $A$ = $\{1, 2, 3, 4\}$ or $A$ = $\{1, 2, 3\}$ or any other finite small set). How can I find the total number of partial order ...
2
votes
2answers
875 views

Answering Questions For A Poset.

The question I am looking at is, "Answer these questions for the poset $(\{3,5,9,15, 24,45\},|)$." a) Find the maximal elements. b)Find the minimal elements. c) Is there a greatest element? d) Is ...
6
votes
4answers
3k views

Understanding equivalence class, equivalence relation, partition

Im having difficulty grasping a couple of set theory concepts, specifically concepts dealing with relations. Here are the ones I'm having trouble with and their definitions. 1) The collection of ...
2
votes
3answers
2k views

Reflexive Transitive Closure

The problem I am working on is, "Show that a finite poset can be reconstructed from its covering relation. [Hint:Show that the poset is the reflexive transitive closure of its covering relation.]" I ...
0
votes
1answer
121 views

Establishing A Covering Relation

The problem I am working on is, "What is the covering relation of the partial ordering $\{(A,B)|A⊆B\}$ on the power set of $S$, where $S=\{a, b, c\}$?" I am reading the answer key, and I can follow ...
1
vote
1answer
2k views

Constructing A Hasse Diagram Using The Covering Relation

I am still having a little difficultly with the covering relation, specifically that when y covers x, $x \prec y$ there is no element in between them, $ x \prec z \prec y$, where x,y, and z are ...
2
votes
1answer
319 views

reflexive, transitive and symmetric relations.

Problem Let $R:=\{(a,b) \in \mathbb{N^2}\mid a \leq b\}$. Is $R$ reflexive, symmetric, antisymmetric, transitive? The portrayed relation is reflexive because both $a \leq b$ and $b \leq ...
1
vote
3answers
3k views

Definition Of Lexicographic Ordering

I am reading about about lexicographic ordering, and I want to make sure I am understanding it properly. Lexicographic ordering is defined to be the cartesian product of two, or more, posets. So, $A_1 ...
3
votes
1answer
386 views

Incomparable Elements In A Poset

The problem I am working on is, Find two incomparable elements in these posets. a) $(P(\{0,1,2\}),⊆)$ b) $(\{1,2,4,6,8\},|)$ For a, I said that $R \subseteq p(\{0,1,2,3\}) \times p(\{0,1,2,3\})$, ...
0
votes
1answer
84 views

Am I correct? State the necessary and sufficient condition for R to be an equivalence relation on A.

Let R be a relation on a given nonempty set A. State the necessary and sufficient condition for R to be an equivalence relation on A. My attempt The conditions for any equivalence relation are ...
1
vote
1answer
392 views

Warshall's algorithm multiple choice…

Here's a question given to us for practice. Can anyone help me through the steps of solving it? The algorithm itself is confusing to read, so I'm just looking for a concise way to calculate $W_1$, ...
0
votes
1answer
85 views

Finding Upper And Lower Bounds

The question is, Find the lower and upper bounds of the subsets $\{a, b, c\}$, $\{j, h\}$, and $\{a, c, d, f\}$ in the poset. A poset is of the form $(S,R)$, where $S$ is the set, and $R$ is the ...
1
vote
3answers
1k views

How to show that two equivalence classes are either equal or have an empty intersection?

For $x \in X$, let $[x]$ be the set $[x] = \{a \in X | \ x \sim a\}$. Show that given two elements $x,y \in X$, either a) $[x]=[y]$ or b) $[x] \cap [y] = \varnothing$. How I started it is, if ...
2
votes
2answers
234 views

Dual Of A Poset

The question I am working on is, "Find the duals of these posets. a) $(\{0,1,2\},≤)$ b) $(\Bbb Z,≥)$ c) $(P(\Bbb Z),⊇)$ d) $(\Bbb Z^+,|)$ In my textbook, they say to find the dual of a poset, ...
0
votes
1answer
359 views

Multiple choice questions on relations and some of their properties

I'm confused about these 3 selected problems. I have the solutions for each, if necessary, but I'm much more interested in understanding the material. If anyone can offer a clear, concise, and ...
4
votes
1answer
509 views

Determining If A Relation And Set Can Form A Poset

The question is, "Is $(S,R)$ a poset if $S$ is the set of all people in the world and $(a, b)∈R$, where a and b are people, if a) a is taller than b? b)a is not taller than b? c) $a=b$ or a is an ...
1
vote
3answers
700 views

Trouble understanding equivalence relations and equivalence classes…anyone care to explain?

What exactly are equivalence relations and equivalence classes? The latter is giving me the most trouble; I've tried to read multiple sources online but it just keeps going over my head. Example ...
1
vote
3answers
136 views

Intuitive understanding of relations and their basic properties

Can anyone explain relations and the four basic properties of them (reflexive, symmetric, antisymmetric, transitive)- or direct me to a source that does. Particularly, are these statements ...
6
votes
3answers
6k views

Transitive Relations

For example, $$R = \{ (1,1),(1,2),(2,1),(2,2) \} \quad\text{for}\quad A = \{1,2,3\}.$$ This relation is symmetric and transitive. I understand that the relation is symmetric, but my brain does not ...
2
votes
2answers
586 views

Determing If Relations Are Partial Orderings

The question is, "Which of these relations on$\{0,1,2,3\}$ are partial orderings? Determine the properties of a partial ordering that the others lack." The only two I had trouble with were: ...
3
votes
3answers
185 views

Disjoint Equivalence

Why do equivalence classes, on a particular set, have to be disjoint? What's the intuition behind it? I'd appreciate your help Thank you!
1
vote
1answer
1k views

Maximal and Minimal Elements

In my textbook, the give an example for finding maximal and minimal elements on a set. The set is $(\{2,4,5,10,12,20,25\},|)$. To find the maximal and minimal elements of the set, the draw a Hasse ...
2
votes
1answer
182 views

Partial Ordering and Covering Relations

I am currently reading about partial ordering and covering relations. I just want to be certain that I am understanding these concepts correctly. A partial ordered set (poset) is just a relation on a ...
3
votes
1answer
369 views

Inverse of composition of relation

I'm doing preparaton problems for my exam and one of the first problems in the "composition of relations" section is this: Prove: $$ (A \circ B)^{-1} = B^{-1} \circ A^{-1} $$ I know I need to prove ...
1
vote
3answers
170 views

Describing A Congruence Class

The question is, "Give a description of each of the congruence classes modulo 6." Well, I began saying that we have a relation, $R$, on the set $Z$, or, $R \subset Z \times Z$, where $x,y \in Z$. The ...
1
vote
1answer
30 views

The Importance Of Equivalences

Okay, I asked a question earlier today, Congruence Class, pertaining to finding equivalence classes. I already know how to solve such problems, now my question is, what is the importance of ...
1
vote
2answers
751 views

Equivalence Class of the relation {(0,0) (1,1) (2,2) (3,3)}

The above relation is equivalent for the set {0,1,2,3}. How would you find the equivalence class for this relation or any general relational set of pairs of integers?
2
votes
4answers
682 views

Equivalence relation on set $\{0,1,2,3\}$

I'm given a a relation on the set above as $R = \{(0,0), (1,1), (2,2), (3,3)\}$. I can see how this is reflexive. Since if $a = 0,1,2, 3$ then $(a,a)\in R$. However, how is it symmetric and ...
2
votes
3answers
977 views

Equivalence Relation On A Set Of Ordered-Pairs

The question is, "Let R be the relation on the set of ordered pairs of positive integers such that $((a, b), (c, d)) ∈ R$ and only if $a+d=b+c$. Show that R is an equivalence relation." There are two ...
1
vote
3answers
787 views

Finding The Equivalence Class

Okay, so the question I am working on is, "Suppose that A is a nonempty set, and $f$ is a function that has A as its domain. Let R be the relation on A consisting of all ordered pairs $(x, y)$ such ...
3
votes
2answers
642 views

Equivalence Relations On A Set of All Functions

The question is, "Which of these relations on the set of all functions from $Z$ to $Z$ are equivalence relations." The first relation to consider is, $\{(f,g)|f(0)=g(0)\vee f(1)=g(1)\}$ For this one, ...
0
votes
1answer
271 views

Equivalence Relations On A Set of All Functions From Z to Z

The question is, "Which of these relations on the set of all functions from $Z$ to $Z$ are equivalence relations. $\{(f,g)|f(1)=g(1)\}$ I just want to make certain that I am interpreting this ...
1
vote
1answer
77 views

Deciding If A Relation On A Set Is An Equivalence Relation

The relation I am looking at is $\{(0,0),(1,1),(1,3),(2,2),(2,3),(3,1),(3,2),(3,3)\}$, and is on the set $\{0,1,2,3\}$ Apparently, the only thing that does not qualify this as an equivalence relation ...
2
votes
3answers
284 views

Equivalence Class Definition

I am currently reading about the subject given in the title of this thread. The definition they give for equivalence classes in my textbook is a rather ostentatious in its wording, so I just want to ...
0
votes
1answer
149 views

Is the following Hasse diagram for a partial order correct?

I'm not sure if my Hasse diagram is correct for the partial order $$R = \{(2,2),(4,2),(6,2),(6,3),(3,3),(4,4),(5,5),(6,6)\}.$$ Any confirmation/correction would be much appreciated.
0
votes
1answer
23 views

For the partial order R = {(2,2),(4,2),(6,2),(6,3),(3,3),(4,4),(5,5),(6,6)} is the following answer for maximal and minimal elements correct?

Maximal elements: 2,3 and 5 Minimal elements: 4,5 and 6 I just want to confirm to make sure that I understand maximal and minimal elements correctly.
0
votes
1answer
254 views

List all maximal and minimal elements of the partial order R = {(a,a), (b,b), (c,c), (a,c)}

I know what the definitions of maximal and minimal elements are but I'm not sure how to apply them in this case. Any help would be great.
0
votes
2answers
875 views

What is the significance of the mirror numbers?

I'd like to hear insights and theory of the mirror numbers and their possible significance in mathematics and geometry. With mirror numbers I mean these four examples: ...
1
vote
1answer
173 views

Proof that an equivalence class contains an element

Let $A = \mathbb{N} \times \mathbb{N} $, and let $R$ be an equivalence relation on $A$ such that: $$R = \left\{\big((m,n),(h,k)\big) \in A \times A \mid m + k = n + h\right\}.$$ Prove that each ...
1
vote
2answers
821 views

Prove that a function is a total function (as opposed to a partial function)

I've got as part of an assignment to determine whether a given function is total, and if so, to say whether it's injective, surjective, or bijective. I can tell the answer by looking at it, but I feel ...
0
votes
2answers
486 views

Relations Represented As Matrices

The question is, "How many nonzero entries does the matrix representing the relation $R$ on $A=\{1,2,3,...,100\}$ consisting of the first $100$ positive integers have if $R=\{(a, b)|a=b+1\}$? I ...
0
votes
1answer
69 views

Equivalence-relations question.

Show that for all class $ \{A_i \}_{i\in I}$ of $A $, the relation $T$ is equivalence relation where $T$ is defined to be: $xTy$ iff exist $i\in I$ such that $\{ x,y\}\subseteq A_i$. My attempt: ...
0
votes
2answers
378 views

Elementary Row Operations To Find Inverse Matrix

I have to find the inverse matrix of this matrix that represents a relation. My question is, is it possible to use elementary row operations on a one-zero matrix to find the inverse? I've done it ...