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
291 views

Reflexive, Symmetric, Anti-Symmetric relations

Let $A = \mathbb Z \times ( \mathbb Z\setminus {0} )$. A binary relation $R$ on $A$ is defined as follows: For all $(a,b),(c,d) \in A$ $$(a,b) \,R\,(c,d) \iff ad = bc$$ now how do I find if $R$ is ...
1
vote
1answer
40 views

Relations $R^2, R^3, R^i and R^*$

Consider the relation on R on the reals where $xRy$ iff $xy=1$ I need to find $R^2, R^3, R^i $ and $R^*$ Ok, so I first started off with the following: $$xR^2z \equiv \exists y: xRy\land yRz \\ ...
1
vote
2answers
182 views

Reduction Transitive Relation Problem

I have this problem on my homework, it's my last one left but I'm having trouble with it. Any help would be appreciated.
0
votes
1answer
61 views

Question about relations and ordered pairs

I am not sure how to determine if the ordered pairs are in the relation. I kind of have a gut feeling that 7 a) c) are in the relation, but not sure about b) Also can someone help me with question ...
1
vote
1answer
59 views

Proving that $\bigcup_{n=1}^{\infty }R^n$ is a transitive relation on A

Let $R$ be a relation on set $A$. How can i prove that $\bigcup_{n=1}^{\infty }R^n$ is a transitive relation on $A$? Maybe it has to do with $\bigcup_{n=1}^{\infty }R^n=tc(R)$ ?
2
votes
0answers
26 views

How would I show the relations on this set of S?

I want to show that the set below is reflexive, anti-symmetric, and transitive. Let $S$ be the set of positive integer divisors of $180$ and consider the relation $\mid$ on $S$. I understand that ...
1
vote
1answer
33 views

Relations and transitivity.

Let $R=\{ (a,b) : \ \mid a-b\mid \ \leq1\ \}$ on $\Bbb Z$ Well I know it's reflexive and symmetric and not anti-symmetric, although I don't see why it's not transitive. if $\mid a-b\mid \leq1 \ ...
0
votes
2answers
72 views

Unknown maths topic, does the numbers hold

Let $A=\{a,b,c,d,e,f\}$ and let $R\subseteq A\times A$ be a relation which is symmetric and transitive. You have been given some partial information about the relation which is that the following ...
1
vote
1answer
53 views

Naturally definable order relations

Each and every function $f:X\rightarrow Y$ between two totally ordered sets $(X,\leq_X), (Y,\leq_Y)$ induces a relation $\preceq$ on $X$ by $$x \preceq x' :\equiv \begin{cases} x &\leq_X x' ...
1
vote
1answer
50 views

how many elements does Ia have?

Let $A=\{1,2,3,4\}$. Let $F$ be the set of all functions from $A$ to $A$. Let $R$ be the relation on $F$ defined by $f,g \in F$ $f R g \Leftrightarrow |f(A)|=|g(A)|$ $f(A)=\{f(x): x\in A\}$ ...
0
votes
2answers
99 views

Let S = {1,2…10} Let R be the relation on P(S), the power set of S, defined by: for any X,Y ∈ P(S),

Let S = {1,2....10} Let R be the relation on P(S), the power set of S, defined by: for any X,Y ∈ P(S), XRY <=> X∩Y=∅ is it true that ∀X∈P(S),∃Y∈P(S) so that (X,Y)∈R? I dont know what is (X,Y)? ...
2
votes
0answers
20 views

Partial orders and equivalence relations [duplicate]

Let $S = \{ u,v,w \} $ List all equivalence relations on S. How many of these are also partial orders? Well I found five total equivalences classes but right now I'm confused as to which are partial ...
1
vote
1answer
53 views

Need help to understand equivalence class

This is in my note Let S={1,2,3,4} Let R be the relation on P(s) defined by xRy <=>|x|=|y| how many equivalence classes are there ? 5 [∅]={∅} [{2}]={{1},{2},{3},{4}} [{2,3}]={{1,2},.......... ...
0
votes
1answer
76 views

Reflexive, Symmetric, And Transitive

Define a relation R on $\Bbb{Z}$ as follows: $$ (x, y) \in R \qquad \text{if and only if} \qquad x \cdot y > 0 $$ Is R reflexive? Is R symmetric? Is R transitive? I think it's not reflexive ...
0
votes
0answers
38 views

Composition of relation

This is a follow to a question I had previously asked but got no clarification. Suppose you wish to find $R^2$ for the relation defined $xRy$ iff $x-y=c$. I know that $R^2$ is $x-y=2c$, but I'm not ...
4
votes
1answer
210 views

Smallest relation for reflexive, symmetry and transitivity

Find the smallest relation containing the relation $$R=\{ (1,2),(2,1),(2,3),(3,4),(4,1) \}$$ that is Reflexive and transitive Reflexive, transitive and symmetric Well this ...
2
votes
1answer
69 views

Relations and equivalence relation

Let $R=\{ (x,y) \vert x=1 \,\, or\,\, y=1 \}$ When I see something written like this to represent "or", I immediately think XOR. But is that necessarily true? This would greatly change the ...
1
vote
1answer
30 views

Proof by induction in Relations

$R$ and $S$ be relations such that $R\subseteq S$. Prove that $R^n \subseteq S^n$ for all positive integers.Can anyone help me in proving this using induction?
4
votes
3answers
1k views

'Does not necessarily equal' symbol

What symbol would I use if I wanted to express that, in the context of some binary relation $P$ implied from context, that $\exists (a,b)\in P: a\ne b$, but not to the extent that $\forall (a,b) \in ...
3
votes
1answer
117 views

Finite poset maximum and minimum element

Let $(P,\le)$ be a finite poset. An element $z \in P$ is an upper bound for $x,y \in P$ if $x \le z$ and $y \le z$. How do I prove that if every two elements in $P$ have an upper bound then ...
2
votes
1answer
26 views

What is the structure of a directed graph with vertex set A which has a relation R

I am studying for a test and found this question in the book: Let $R$ be an equivalence relation on the set A (Non-empty). Let $D_R$ be the directed graph with vertex set $A$ and an arc from $x$ to ...
0
votes
1answer
71 views

Composition relations and powers

Let $R$ be the relation on $\Bbb Z$ such that $xRy$ iff $x-y=c$ a.) Define $R^2$ b.) Define $R^i$ for abitrary $i\ge1$. Well the problem I'm having with this is trying to figure out ...
5
votes
1answer
94 views

Why is this binary-relation antisymmetric?

Definition of antisymmetric binary-relation is $$\forall a,b\in\mathrm{A},\left[ \left(aRb\wedge bRa\right)\rightarrow\left(a=b\right)\right].$$ Let $\mathrm{A}=\left\{a\mid ...
0
votes
1answer
352 views

Maximal and minimal elements of the partial order relation

Let $A=\{1,2,3,4\}$ and $H$ is the set of antisymmetric relations on $A$. I think that $H = \{(1,2),(2,3),(3,4),(1,3),(1,4),(2,4)\}$. How would I find the minimum/maximum and min/max elements?
0
votes
1answer
121 views

Give proofs by induction for the following relation properties.

Let $R$ and $S$ be relations such that $R\subseteq S$. Prove that $R^n$ is a subset of $S^n$ for all positive integers $n$. Let $R$ be a symmetric relation. Prove that $R^n$ is symmetric for all ...
0
votes
1answer
45 views

Let $R$ be the relation on $\mathbb Z^+ \times \mathbb Z^+$ such that $(a, b)R(c, d)$ if $gcd(a, b) = gcd(c, d)$?

I need to find out: Prove that $R$ is an equivalence relation. (I am not clear on definition of an equivalence relation) What is the equivalence class of $(1,2)$? Give an interpretation of the ...
1
vote
1answer
369 views

What are some concrete examples of kinds of relations in math?

I'm writing an undergrad philosophy paper. My take on the issue is that the conceptual problem I'm addressing is only a problem because the word 'is' and 'relation' are too slippery. By more precisely ...
1
vote
2answers
211 views

Finding Powers of Relations

I have been trying to work on this question and this up to were I was able to go, but I am stuck and I do not know if I am going the right way.
3
votes
1answer
74 views

How do you find the power set within a power set?

I'm trying to find P(P(A)), where A = {0, 1, 2, 4, 7, 9}. Any ideas?
0
votes
0answers
50 views

How does Dilworth’s Theorem apply to the set $\{0, 2, 6, 7\}$?

I'm having some serious problems with Dilworth's Theorem. My question is 'how does Dilworth’s Theorem apply to the set $\{0, 2, 6, 7\}$?'. Any help is appreciated.
5
votes
4answers
739 views

is the empty set a relation?

Is the empty set is a relation? I wonder if the empty set is a relation.in enderton's a relation is a set of ordered pairs. If yes it's a relation why is that?. There is an example in the text for a ...
-1
votes
1answer
54 views

Relations on a set.

State the smallest relation containing the relation $$\{(1,2),(2,1),(2,3),(3,4),(4,1)\}$$ that is: a) reflexive and transitive. b) reflexive, symmetric and transitive. For me reflexive would be ...
1
vote
1answer
93 views

State whether or not the relation on the set of reals is reflexive, symmetric, antisymmetric or transitive

State whether or not the relation on the set of real numbers is reflexive, symmetric, anti-symmetric or transitive. $$R= \{(x,y)\mid x=1\text{ or }y=1\}$$ This is what I have done up to now, not ...
1
vote
2answers
259 views

Notation of a function that maps a random element

Let there be a functions $f$ and $g$ such that, $$f:A \times B \mapsto \Re$$ $$g: B \mapsto A$$ where $\forall b \in B$, $g(b)$ is some $a$ such that, $\forall a' \in A, f(a,b) \geq f(a',b)$. (This ...
2
votes
2answers
170 views

Is statistical dependence transitive?

Take any three random variables $X_1$, $X_2$, and $X_3$. Is it possible for $X_1$ and $X_2$ to be dependent, $X_2$ and $X_3$ to be dependent, but $X_1$ and $X_3$ to be independent? Is it possible ...
1
vote
3answers
233 views

Show that there is exactly one maximal element in a poset with a greatest element?

This is true, any idea how to say it in proof form? I would guess: In a poset with one maximal element, then that element has no other elements above it and has elements below it. If its the only ...
0
votes
2answers
552 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
421 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
51 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
69 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
86 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
488 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
682 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 ...