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

0
votes
2answers
528 views

Why are these relations not posets?

I was hoping you guys could help me clarify why these relations are or arent posets. I gave my thought process that resulted in the wrong answer. ...
0
votes
1answer
387 views

Symmetric and Transitive closures

Given a relation $R$, is the symmetric closure of the transitive closure of $R$ equal to the transitive closure of the symmetric closure of $R$? If yes, prove it. If not, give a counterexample. ...
4
votes
0answers
50 views

Metric-like families of relations

Let $X$ be an arbitrary set and to start with, let us consider a relation $\leq$ on $X$ (that is $\leq$ is a subset of $X^2$) which is reflexive and transitive. such a relation is called a preorder. ...
0
votes
1answer
66 views

Variable weight according to distance.

So I have a range of numbers for this example I would say something like 0 to 25. Within this range if I get a number lets say 11, then for each number that between my goal I it weighs more depending ...
0
votes
4answers
122 views

How to find $f(2013)$ if $f(5)=45$ and $f(m)+f(n)= f(m+n)$ for all $m,n\in\mathbb N$?

$f: \mathbb N\to\mathbb N$, $f(m)+f(n)=f(m+n)$ for all $m,n\in\mathbb N$, and $f(5)=45$. Find $f(2013)$. I messed up my original posting, its fixed now. I changed $m+ n$ to $f(m+n)$.
4
votes
1answer
1k views

How many transitive relations on a set of $n$ elements?

If a set has $n$ elements, how many transitive relations are there on it? For example if set $A$ has $2$ elements then how many transitive relations. I know the total number of relations is $16$ but ...
0
votes
1answer
48 views

Why is this binary-relation symmetric?

From the example of binary-symmetric-relation demonstrated in Wikipedia, how can they say the relation "$x$ and $y$ are odd numbers" is symmetric without stating any set of $x$, $y$? If such set is ...
0
votes
1answer
84 views

Reflexive or Irreflexive

Are the following relations reflexive or irreflexive $R = \{ (x,y) : y = 2x\}$ $R = \{ (x,y) : x \text{ is a sibling of }y\}$ $R = \{ (x,y) : x = 3 + y\}$ I believe 1 is reflexive but I'm not sure ...
0
votes
3answers
64 views

Is binary-relation $\left\{\left(a,b\right)\mid a,b\in\mathbb{N}\wedge a,b \text{ are even numbers}\right\}$ reflexive?

I'm a novice in set theory and I'm not clear about reflexive relation. My question is the title. Is binary-relation $R:=\left\{\left(a,b\right)\mid a,b\in\mathbb{N}\wedge a,b \text{ are even ...
1
vote
2answers
31 views

Why $R=\{(a,b)\mid a=b \mbox{ or } a=-b\}$ is not anti symmetric?

Why $R=\{(a,b)\mid a=b \mbox{ or } a=-b\}$ is not anti symmetric? I read because this is symmetric so it is not anti symmetric, but $R=\{(a,b) \mid a=b \}$ is both symmetric and anti symmetric.
1
vote
1answer
60 views

Are there any relations R of size 15 on the set {1, 2, 3, 4, 5, 6} such that R is both transitive and symmetric?

Are there any relations R of size 15 on the set {1, 2, 3, 4, 5, 6} such that R is both transitive and symmetric? Hi, I'm gonna share my thoughts on this problem and my answer and hopefully someone ...
0
votes
1answer
477 views

Relation squared of $xRy$ iff $x-y=c$

Let $R$ be the relation on $\Bbb{Z}$ such that $xRy$ if and only if $x-y=c$. (a) Define $R^2$. Can anyone help me with $R^2$? I am not sure where to start. From similar questions, I saw that it ...
2
votes
1answer
658 views

Finding the smallest relation that is reflexive, transitive, and symmetric

Find the smallest relation containing the relation $\{ (1,2),(2,1),(2,3),(3,4),(4,1) \}$ that is: Reflexive and transitive Reflexive, symmetric and transitive Well my first attempt: Reflexive: ...
0
votes
1answer
63 views

Binary relations, closures and equivalences

Let $R$ be the relation on $Z$ such that $xRy \iff x-y=c$. Well, what I have so far is $R=\{ 0,-1,1,0,-1,1,0 \cdots\}$ Is $R^* $ and equivalence relation? Why not? This is where problems start: I ...
3
votes
2answers
45 views

Give an example of relation $R$ and $S$ on $A$ such that $R$ and $S$ are nonempty, and $R \circ S$ and $S \circ R$ are empty

Let $A = \left \{a, b, c, d\right \}$, give an example of relation $R$ and $S$ on $A$ such that $R$ and $S$ are nonempty, and $R \circ S$ and $S \circ R$ are empty I'm thinking of ways that a set ...
2
votes
1answer
32 views

Generated equivalence relations in logics

Let $L$ be some logic (FO or stronger which is not important for this purpose). Given a $\tau$-structure $A$ and a formula $\varphi(x_1, \dots x_n) \in L[\tau]$ with free variables $x_1, \dots, x_n$. ...
0
votes
1answer
22 views

How many inverse relations

How many inverse relations are there for an n-element set? I know that $R \circ R^{-1}=R^{-1} \circ R$ where $R$ is an invertible relation, but that's as far as I can get.
0
votes
3answers
101 views

Let $A$ be a set with $n$ elements

How many reflexive relations are there on $A$? How many symmetric, reflexive relations are there on $A$? How many equivalence relations are there on $A$, if $n=5$? How are you supposed to find how ...
0
votes
1answer
78 views

Show that there are no squares included in the sequences

Show that there are no squares included in in the sequences (11, 111, 1111, 11111, ....) (22, 222, 2222, 22222, ....) (33, 333, 3333, 33333, ....) and so on and so forth for all numbers $1 ...
1
vote
4answers
40 views

Stuck on equivalence relation question

I have been stuck on this question for a while. I was wondering for a set $A={1,2,3,4,5,6}$, given that its distinct equivalence classes are $\{1,4,5\},\{2,6\},\{3\}$, what is the equivalence relation ...
1
vote
2answers
65 views

Did I do this assignment right? Antisymmetric relation.

I need to prove or disprove, that R is antisymmetric. This is my set: $$ R=\{(1,1),(1,2), (1,4), (2,1), (2,2), (3,2), (3,3), (4,4)\} $$ I proved that it is not antisymmetric in the following manner: ...
0
votes
1answer
112 views

How to tell if relation on set is a partial order when relation is defined as a set of ordered pairs?

Determine whether $R$ is a partial order on set the $S$ and justify your answer. $S=\{1,2,3\}$ and $R=\{(1,1),(2,3),(1,3)\}$. So the job is to consider if $R$ is reflexive, antisymmetric and ...
3
votes
1answer
302 views

Is a set closed under finite intersections? (about filters)

In my research I was faced with the problem (as a special example and a pattern for more general problems) whether the family $\operatorname{GR} ( \Delta \times^{\mathsf{FCD}} \Delta)$ of sets is ...
1
vote
2answers
27 views

Transitive relations and Subsets

I have a question to prove: If relations R is transitive, than R^2 is transitive. In the answer the professor says that if R is transitive than: R^2 is a subset of R (I understand why, this is the ...
1
vote
3answers
58 views

Why is this relation reflexive?

$S$ is this set of all graduates from a university. $xRy$ means that student $x$ first attended the university at the same year student $y$ did. The answer key says $R$ is reflexive but isn't it ...
0
votes
1answer
34 views

Congruence Inconsistency

I have a question about congruency... I understand that: $$ 12 \equiv 7 \bmod 5 $$ $$ \text {is equivalent to:} $$ $$ 5|12-7 $$ but this doesn't seem to hold for: $$ 2 \equiv 8 \bmod 6 $$ $$ \text ...
0
votes
2answers
124 views

An example of a total order (that is NOT a well-order) of the Natural numbers

I need an example of a total ordering of the Natural numbers, that is not a well-ordering. So the classic "less than or equal to" doesn't work in this case since it is well-ordered. I've been ...
2
votes
2answers
101 views

For relations to be reflexive, symmetric and transitive is the property true for just the single subset $A$ or $A\times A$?

I was going over my notes on what it means for relations to be reflexive, symmetric and transitive and I'm unclear on one thing: is it for every $x$ in a set $A$ or set $A\times A$? So my ...
1
vote
1answer
76 views

I need help with a transitive closure question

the question deals with relations $R$ is a binary relation defined on $A = \{0,1,2,3\}$. Let $R = \{(0,1), (0,2), (1,1), (1,3), (2,2), (3,0)\}$. Find $R^t$, the transitive closure of $R$. I have ...
2
votes
0answers
303 views

Suppose $R$ is a relation on $A$ and $R^{-1}$ is the inverse. Proof or counterexample

Suppose $R$ is a relation on $A$ and $R^{-1}$ is the inverse. Give a proof or counterexample for each of the following statements. (a) If $R$ is reflexive, then $R^{-1}$ is reflexive. Let $x \in A$; ...
0
votes
2answers
91 views

Describing relations

(a). Describe all relations $R$ on $A$ which are simultaneously symmetric and antisymmetric. (b). Describe all relations $R$ on $A$ which are reflexive, symmetric, and antisymmetric. I have no ...
1
vote
2answers
229 views

List the symmetric relations on the set {0,1}.

I think the answer should be this, but not sure. Can anyone help me? { }, {(0,0)}, {(0,1)}, {(1,0)}, {(1,1)}, {(0,0), (0,1)}, {(0,0), (1,0)}, {(0,1), (1,0)}, ...
0
votes
2answers
69 views

Model and countermodel to $\exists x.\forall y. x<y$ (with $<$ an arbitrary relation)

Can someone please help me with this question. I have been struggling with it for ages and can't quite seem to work it out: Let $<$ be a binary relation symbol that we will write infix. Let ...
0
votes
1answer
133 views

Kleene Star operation on sets

I have the following question, and do not understand the Kleene star operation in the context of relations. Let R be the relation $R=\{(0,1),(0,2),(1,4),(1,5),(2,3),(2,4),(2,5)\}^*$ on the set ...
0
votes
1answer
42 views

Prove that symmetric closure of R $h_{sym}(R) = R \cup R^T$

I have a question about proving statements of the form in which the given is the union of two sets. Well first of all let me just write how I tried to prove the statement: To show that $h_{sym}(R) = ...
1
vote
2answers
69 views

Transitive, symmetric $R$ such that for all $x$, there is $y$ such that $xRy$, is an equivalence relation

I'm stuck at one particular task I'm working on. Here is the task: Let R be a transitive and symmetrical relation on $S$. Assume that for all $x \in S$ there is a $y \in S$ so that $xRy$. ...
0
votes
1answer
110 views

Closures of Relations

How to prove that the transitive closure of a symmetric closure of a relation is greater than the symmetric closure of a transitive closure of a relation?
0
votes
1answer
62 views

Relations in Discrete Math/ tables

Does anyone know how to make this table? I can do a table with normal values but the $x^2$ throws me off. 'Write the relation as a table, the relation $\mathbb{Z}$ on $\{1,2,3,4\}$ by $(x,y) \in ...
0
votes
2answers
108 views

Showing S is an equivalence relation in X when we know R is a reflexive and transitive relation in X.

I have this question and can't quite grasp it..I'll write down what it says then go through what I've tried. Let $R$ be a reflexive and transitive relation in $X$. Let $S$ be a relation in $X$ such ...
0
votes
1answer
53 views

Proving that the relation $(x,y)S(x',y') \iff x - x' \in \mathbb{Z} \land y = y'$ is of equivalence.

The relation $S$ is of equivalence. I have to prove it. I managed to prove reflexibility and transitivity, but I'm having problems with symmetry. How can I prove it? The relation $S$ is defined ...
2
votes
1answer
1k views

How to determine the equivalence classes of a relation?

I don't fully understand how to find the equivalence classes of a relation. Over $\mathcal P(E)$, where $E = \{1,2,3,4,5,6\}$, $ARB \iff |A\cap\{1,2\}| = |B\cap\{1,2\}|$ From what I've seen, ...
1
vote
1answer
99 views

Determining equivalence classes of certain pairs for the relation $(a,b)R(c,d) \iff a^2 + 7b^2 = c^2 +7d^2$

This is an equivalence relations exercise. It has two parts. The first is about proving that the relation is of equivalence, which seems to be fine to me, but I'll put it there anyway. With the second ...
2
votes
1answer
28 views

Finding order properties in the relation $aSb \iff \exists k \in \mathbb{N} : b = ak$

An order relations exercise I just did. I think it's fine, but the second proof felt a bit too wordy or discursive, instead of going straight to the point with brief and accurate statements. How could ...
0
votes
0answers
77 views

Proof of “relations $R$ and $S$ are symmetric $ \Rightarrow R \cap S$ is symmetric”

Claim: If the relations $R$ and $S$ are symmetric, then $ R \cap S$ is symmetric Proof: Let $R$ be the relation of congruence modulo 10 and $S$ the relation of congruence modulo 6 on the integers. ...
0
votes
2answers
424 views

Transitive closure

Given $M=\{n\in\Bbb Z: 0\le n\le 30\}$ find the transitive closure of the relation $R\subset M\times M$ defined by $R=\{(n,m): m=3n+1\}\cup\{(8,16)\}$ So, I know that a transitive closure is the ...
3
votes
2answers
54 views

Determining the properties for the relation over $P(\mathbb{N})$ where $ARB \iff A \cup B \in H$

I had two problems with this exercise: I don't know the universe for doing $\overline{A}$ (I'll show below). I couldn't show that it was transitive, although I'm fairly sure it is. Can you assist ...
0
votes
1answer
43 views

What is the equivalence class of a relation's element?

I'm studying about equivalence relations. My book has the following definition for an equivalence class: If $R=(G,A,A)$ is a relation of equivalence over the set $A$, the equivalence class of ...
0
votes
0answers
155 views

Finding the first, last, minimal and maximal elements in these relations.

I'm now learning about relations of order. This is what I gather: First element: Precedes all elements Minimal elements: Have no predecessors. The first element is always a minimal. Last element: ...
0
votes
1answer
35 views

Linearly ordered set [closed]

$R_1$ and $R_2$ are linear order relations in set $X$. Prove that $R_1 = R_2$ I'm having trouble understanding the linear order relations. Can someone explain how to prove this? Thanks.
0
votes
1answer
30 views

Proving reflexivity and transitivity

I want to show that if $R$ is reflexive and transitive then $R^{-1}$ is also. Transitivity: $$(a,b)\in R^{-1} \wedge (b,c)\in R^{-1} \Rightarrow (b,a)\in R \wedge (c,b)\in R \Rightarrow (c,a)\in R ...