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
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
232 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
353 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
504 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
689 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
5k 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
582 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
181 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
177 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
360 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
168 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
748 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
674 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
967 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
781 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
633 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
263 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
75 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
283 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
146 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
253 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
838 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
814 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
484 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
374 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 ...
1
vote
2answers
292 views

Combination Problem With Relations?

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
vote
1answer
633 views

What is the composition of relations like this? With no transitive relations between them?

Given $ R_1 = \{(1,2),(5,3)\}\quad\quad R_2 = \{(6,4),(5,7)\}$ What is $R_2 \circ R_1$? Because in my understanding, using the example $ R_3 = \{(1,2),(3,4)\} \quad\quad R_4 = \{ ...
1
vote
1answer
108 views

Union of equivalence relation

Let $S$ be a equivalence relation on $A$, let $B$ be a subset of $A$ and suppose that $T$ equivalence relation on $B$. Defining $R=S \cup T$. Its given that there is exist $x\in A$ such that $B$ is ...
2
votes
2answers
4k views

Transitive Relation

$$\begin{bmatrix}1&0&1\\0&1&0\\1&0&1\end{bmatrix}$$ This is a matrix representation of a relation on the set $\{1, 2, 3\}$. I have to determine if this relation matrix is ...
0
votes
1answer
142 views

Relations As Matrices

I am currently reading about portraying relations on a set as matrices. Firstly, I am not sure how to determine the dimensions of the matrix when given set(s). Secondly, when I go down the columns, ...
1
vote
1answer
3k views

Showing A Relation Is Reflexive, Symmetric, and Transitive.

The question is, "Show that the relation R = ∅ on the empty set S = ∅ is reflexive, symmetric, and transitive." I was told by my teacher that you could simply say it can't be shown that each property ...
1
vote
0answers
64 views

Properties Of Relations

The question asks if there can be a relation on a set that is neither reflexive or irreflexive. The example the book give makes perfect sense: "Yes, for instance{(1,1)} on{1,2}." I was wondering, if ...
3
votes
1answer
554 views

Determing If Relations Are Irreflexive

The question is, "Which relations in Exercise 5 are irreflexive?" Exercise five being: Determine whether the relation R on the set of all Webpages is reflexive, symmetric, antisymmetric, and/or ...
5
votes
3answers
146 views

Is $\varsigma$ equivalence relation?

Let $\varsigma$ be a relation on $\wp(\mathbb{N})$ by defining $\langle A,B\rangle\in \varsigma$ iff exist natural $n$ such that $|A\Delta B|=n$. Is $\varsigma$ equivalence relation? Reflexive: For ...
0
votes
1answer
47 views

Equivalence relation $\varsigma$ on ${\mathbb{R}}^2$

How to show that there is exist equivalence relation $\varsigma$ on ${\mathbb{R}}^2$ such that the following conditions hold: Exist only $7$ equivalence classes by $\varsigma$. For every $x,y \in ...
1
vote
1answer
109 views

Verifying this equivalence relation proposition

$\def\class#1{\mathopen{[\![}#1\mathclose{]\!]}}$Proposition: If $\sim$ is an equivalence relation on $A$ and $a,b\in A$, then either $\class a \cap \class b = \emptyset$ or $\class a = \class b$. ...
1
vote
2answers
36 views

Finding specific elements in a finite set

Given the set $A = \{0, 1\}^8$, how can I find the set of all elements in A with exactly 4 zero entries?
1
vote
1answer
265 views

Finding the equivalence class of a relation

Let $A=\{0,1\}^8$ with equivalence relation $R$ on $A$ as $R=\{(u,v)∈A×A|\text{u and v have the same number of entries equal to 0}\}$ How do I find $[(0, 0, 1, 0, 1, 1, 0, 1)]$ (the equivalence ...
1
vote
2answers
180 views

Proving a relation is an equivalence relation

Let $A = \{0, 1\}^8$. Define the relation $R$ on $A$ as $R = \{ (u, v) \in A \times A | \text{u and v have the same number of entries equal to 0}\}$ How can I show that $R$ is an equivalence ...
2
votes
3answers
12k views

Is my understanding of antisymmetric and symmetric relations correct?

So I'm having a hard time grasping how a relation can be both antisymmetric and symmetric, or neither. Are my examples correct? symmetric & antisymmetric ...
2
votes
2answers
170 views

Discrete Maths - Sets & Relations

I'm trying to get my assignment done and I'm finding it hard to understand Relations. The question says: Let $Q$ be the relation on the set $R$ of non-zero real numbers, where non-zero real numbers ...
1
vote
1answer
42 views

How to determine a in r - in a function of relations

I'm pretty stuck on the following question $f$ on $\mathbb{R}$ given by $xfy\Leftrightarrow (y(2x-3)-3x=y(x^2-2x)-5x^3)$ is a function. Let $g$ be the restriction of $f$ to $\mathbb{Z}^+$, implying ...
0
votes
2answers
171 views

Cartesian product of two sets

If I have a set $A = \{1,2,3,4\}$ why does the Cartesian product of $A \times A$ not include $(2,3) (2.1) (3,1) (3,2) (3,3) or (4,1)(4,2)(4,3)(4,4)$ if its relation subset $R = \{(a,b) : a|b\}$.
2
votes
1answer
40 views

Showing that relation $f$ is a function

How can I determine if the relation $f$ on $\mathbb{R}$ given by $xfy\Leftrightarrow (y(2x-3)-3x=y(x^2-2x)-5x^2)$ is a function? I've tried plotting the function as a quadratic function, and doing ...