0
votes
1answer
47 views

Proving a relation is transitive

I am trying to understand transitive relations. I understand given that a set may have $\{(a,b)(b,c)\}$ it must contain $(a,c)$ for it to be transitive. But for longer sets I am getting confused in ...
0
votes
2answers
9 views

Find a relation over $P(${$1,2,3$}$)$ such that $|R|=12$ and the transitive closure of $R$ is the proper subset relation

I'm having trouble finding relation $R$ over $P(${$1,2,3$}$)$ such that $|R|=12$ and the transitive closure of $R$ is $T$, the proper subset relation over $P(${$1,2,3$}$)$. My thoughts: a pair of ...
1
vote
1answer
54 views

Show that if $R$ is a strict partial order on $X$, and $R$ is not linear, then there exists a strict partial order $R'$ and $R' \supsetneqq R$.

Question: Show that if $R$ is a strict partial order on $X$, and $R$ is not linear, then there exists a strict partial order $R'$ and $R' \supsetneqq R$. My attempt: By definition 6.23,6.3.1, and ...
0
votes
1answer
42 views

Determining Equivalence Relation on $\Bbb{Z}$

Alright, I have a homework problem which I have researched, read up on and I (think) solved. I just need someone to either confirm my answer (and re-affirm my knowledge) or explain why I am wrong. ...
0
votes
2answers
30 views

Use of “for all” in definition of reflexive and symmetric relations.

My book says that a relation R on A is reflexive, if $\ (a,a) \in R, \ for\ every \ a \in A$ symmetric, if $\ (a_1,a_2) \in R \implies (a_2,a_1) \in R,\ for\ all\ a_1,a_2 \in A$ Although I ...
1
vote
1answer
46 views

Proving isomorphisms from posets.

An isomorphism from a poset $(S_1,R_1)$ to a poset $(S_2,R_2)$ is a bijection $f: S_1 \rightarrow S_2$ such that, for all $x,y \in S_1$ $(x,y) \in R_1 \leftrightarrow (f(x), f(y)) \in R_2$ When ...
2
votes
1answer
37 views

$R$ is transitive if and only if $ R \circ R \subseteq R$

Question: Let $R$ be a relation on a set $S$. Prove the following. $R$ is transitive if and only if $ R \circ R \subseteq R$. Definition 6.3.9 states that we let $R_1$ and $R_2$ be relations on a ...
0
votes
0answers
24 views

Equivalence Relations and Order? Homework help

Having some trouble on these questions: c) Describe a partial order on {1, 2, 3} that is not a total order d) Describe a binary relation on {1, 2, 3} that is both a partial order and an equivalence ...
2
votes
1answer
336 views

Composite Relations - Give Examples of relations $R_1$ and $R_2$ such that $R_2 \circ R_1 = R_1 \circ R_2$ and $R_2 \circ R_1 \neq R_1 \circ R_2$

Let $S =[a,b,c]$. Give examples of a. relations $R_1$ and $R_2$ on $S$ such that $R_2 \circ R_1 = R_1 \circ R_2$ b. relations $R_1$ and $R_2$ on $S$ such that $R_2 \circ R_1 \neq R_1 \circ R_2$ My ...
1
vote
1answer
53 views

Relation $R$ on $V$ is given by $x+y$ is even [closed]

A relation $R$ on $V$ is given by $x+y$ is even. How can we show that if integers $x$ and $y$ are $R$-related then either $x$ and $y$ are both even or $x$ and $y$ are both odd? I've been looking ...
2
votes
1answer
18 views

Checking the equivalence relations of sets

$S=\{0,1,2,3\}, R:SxS, (m,n)\in R \text{ if } m+n=4$. From the condition of $R$, I found that $R=\{(2,2),(1,3),(3,1)\}$. Now I have to see if $R$ is reflexive, symmetric, antisymmetric, and ...
0
votes
1answer
150 views

Count number of binary relations between sets

He, I have following questions: We have sets $A$ and $B$, $\left | A \right | = m,\left | B \right | = n$. 1) How many binary relations are there from $A$ to $B$? 2) How many binary relations are ...
0
votes
1answer
28 views

Prove the following $R \subseteq A\times B$ and $S\subseteq B\times C \rightarrow $ $ S \circ R $ is symetric

I want to prove the following $ S \circ R $ is symetric, A,B, C are sets $R \subseteq A\times B$ is Symetric $S\subseteq B\times C$ is Symetric Any Suggestions? Thanks!
1
vote
0answers
34 views

Prove the following $(R\cap S)^n=R^n \cap S^n$

I would like to prove the following without induction. $$(R\cap S)^n=R^n \cap S^n$$ We can start by take $(a,b)\in (R\cap S)^n$ its represent a path from $a$ to $b$ right? Any hints? Thanks.
0
votes
3answers
51 views

Check the following Relation $R=\{(x,y) |\exists k\in \mathbb{Z} \cdot x*y=3k \}$

I would like to check the following relation: $$R=\{(x,y) |\exists k\in \mathbb{Z} \cdot x*y=3k \},R\subseteq \mathbb{Z} \times \mathbb{Z}$$ Reflexivity Symmetric Transitivity Asymmetric Can I ...
0
votes
2answers
42 views

Binary relations: The Lion quiz.

This is my third question today and I think I'm abusing the platform a bit. In any case, here's the question: Let $L$ be the total number of lions that live in Africa today. A binary relation $R$ ...
1
vote
1answer
35 views

What is meant by a|a notation?

Is the "divides" relation on set of positive integer reflexive? In solution of above question I found following. ...
0
votes
2answers
52 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
2answers
60 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 ...
0
votes
1answer
73 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
4answers
117 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)$.
0
votes
1answer
218 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 ...
0
votes
1answer
60 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 ...
0
votes
2answers
43 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 ...
0
votes
2answers
24 views

Why are both of these not equivalence relations?

Can anyone tell me why the first set is an equivalence relation, and not the second? As far as I can see, both are reflexive, symmetric and transitive, but my books says only the second one is an ...
0
votes
1answer
50 views

Question on increasing/decreasing subsequences?

Here's the question: Describe a sequence consisting from 1 to 10,000 in some order so that there is no increasing or decreasing subsequence of size 101. I'm not quite sure how to do this. My first ...
0
votes
1answer
71 views

Is this poset a lattice?

Given the set $\Bbb Z^+\times\Bbb Z^+$ and the relation $$\begin{align*} (x_1,x_2)\,R\,(y_1,y_2)\iff &(x_1+x_2 < y_1 + y_2)\\ &\text{ OR }(x_1 + x_2 = y_1 + y_2\text{ AND }x_1 \le y_1)\;: ...
1
vote
2answers
104 views

Symmetric relations

Let $A=\{ 1, 2, 3, 4 \}$ is $ B = \{ (1, 2), (2, 1), (1, 3), (3, 1) \} $ Is $B$ a symmetric relation on $A$? I said no because not all $x, y \in A$ are in $B$ Is this correct?
1
vote
1answer
114 views

Prove the relation to be a Linear Order.

Let (a, b),(x, y) ∈ R × R and define ≺ as follows: (a, b) ≺ (c, d) iff a < c or a = c and b < d: Define (a, b) ≼ (c, d) if and only if (a, b) = (c, d) or (a, b) ≺ (c, d). Show that ≼ is a ...
2
votes
3answers
263 views

How to solve recurrence relation: f(n) = f(n-1) + 2(n-1) when f(1) = 1?

I am just learning about recurrence relations, and this is an absolute beginner's question. I understand what's going on in the formula, but I have no clue how to write it's solution? This probably ...
2
votes
2answers
69 views

Set theory relation: irreflexive and transitive

Which of the following relations on $T = \{1, 2, 3\}$ is irreflexive and transitive. $\{(2, 1), (2, 3)\}$ $\{(1, 1), (2, 1), (3, 2)\}$ $\{(2, 1), (1, 2), (3, 2), (2, 3)\}$ $\{(1, 1), (2, 2), (3, 3), ...
0
votes
1answer
273 views

Antisymmetric Relation

Determine whether the relation R on the set of all people is antisymmetric. (a) a is taller than b. (b) a and b are born on the same day. (c) a has the same first name as b. ...
0
votes
0answers
22 views

Prove that T comp (S comp R)=(T comp S) comp R

W, X, Y, Z are sets. R is the relation from W to X, S is the relation from X to Y, and T is the relation from Y to Z. Prove that T composition (S composition R)=(T composition S) composition R If ...
4
votes
1answer
83 views

Function Question (one-to-one, onto)

Define $F : \mathbb{Z} \to \mathbb{Z}$ by the rule $F(n) = 2 -3n$, for all $n \in \mathbb{Z}$. Is $F$ one-to-one? Onto? Now, I understand that one-to-one means that nothing in the co-domain is ...
0
votes
1answer
38 views

Discrete and combinatorial mathematics

Suppose we have a relation on a set $A$, i.e. $A \times A$, where $|A| = n; \;n$ a positive integer. How can we count the number of relations on set $A$ which are reflexive, symmetric, transitive and ...
1
vote
2answers
284 views

Reflexive but not Transitive relation

What is an example of a Relation R on a set S such that R is reflexive but not transitive Here is what I come up with. Let S be the set of all Integers then R = {x and y are both positive OR x and y ...
3
votes
1answer
71 views

$\beta$ as the relation “is a brother of”

So I have a question about relations. In particular, here is the formal question: Let $\beta$ be the relation "is a brother of" and let $\sigma$ be the relation "is a sister of". Describe ...
0
votes
2answers
58 views

Abstract Algebra topic: Equivalence relations [duplicate]

If R1 is reflective and not transitive, R2 is transitive but not symmetric and R3 is symmetric but not reflexive. We need to find an example of a set S and the three relations R1 R2 R3.
1
vote
1answer
104 views

relations - examples and counterexamples

The question is to find an example of a set $S$ and three relations $R_1$, $R_2$, and $R_3$ on it, such that $R_1$ is reflexive but not transitive, $R_2$ is transitive but not symmetric and $R_3$ is ...
0
votes
1answer
38 views

Number of (equivalence) relations fulfilling some additional conditions

let say I have $A=\{1,\dots,8\}$ I want to know the following things: what the number of relations on $A$? what the number of reflexivity relations on $A$? what the number of equivalence relations ...
1
vote
2answers
124 views

Partially ordered set Question : $A=\{1,2,3,4,5,6\}$ ,$R =\mathcal P(A) \times \mathcal P(A) $

I`m trying to prove that this relation is partially ordered set: $A=\{1,2,3,4,5,6\}$ $R =\mathcal P(A) \times \mathcal P(A) $ $(B,C)R(D,E) \Longleftrightarrow (B \subset D) \vee ((B=D)\wedge(C ...
1
vote
1answer
121 views

Transitive closure of these relations on $\{1,2,3,4\}$?

Problem How can I show transitive closure of these relations on $\{1,2,3,4\}$? $\{(1,2), (2,1), (2,3), (3,4), (4,1)\}$ $\{(2,1), (2,3), (3,1), (3,4), (4,1), (4,3)\}$ $\{(1,2), (1,3), (1,4), (2,3), ...
1
vote
2answers
157 views

Need assistance determining whether these relations are transitive or antisymmetric (or both?)

Problem I have these two relations over $A$, and I am supposed to determine whether they are reflexive, symmetric, antisymmetric, and/or transitive. I have determined that they are not reflexive or ...
1
vote
2answers
81 views

reflexive and antisymetric relation

Let $A = \{1,2,3,4,\ldots ,n\}$ A). How many relations on $A$ are both reflexive and antisymmetric and contain the ordered pair $(1,2)$ ? Ans. for this I believe it is either $3^{(n^2-n-1)/2}$ or ...
-2
votes
2answers
49 views

Statements regarding relations in R

Suppose $\rho$ is a relation on $R$. I want to verify whether the following statements are true. Looks simple but proving them seems to be difficult for me. $\rho\circ\rho$ is a subset of $\rho$ ...
0
votes
2answers
247 views

Let $R$ be an equivalence relation on a set $A$, $a,b \in A$. Prove $[a] = [b]$ iff $aRb$.

Hello I need help with the proof strategy for this problem. Let $R$ be an equivalence relation on a set $A$ and let $a,b \in A$. Prove that $[a] = [b]$ if and only if $aRb$.
0
votes
2answers
91 views

Minimum Equivalence Relation

Let $X= \{1,2,3,4\}$, and $R = \{(1,2),(3,4)\}$. Show the minimum equivalence relation on $X$ that extends $R$. How many elements does the quotient set $X/R$ have ? Can somebody give hints to solve it ...
-4
votes
2answers
77 views

General properties of equivalence relations

Let $\sim_1$ and $\sim_2$ be distinct equivalence relations on A. Define $\sim_3$ by $a \sim_3 b$ if and only if $a \sim_1 b \land a \sim_2 b$. Prove that $\sim_3$ is an equivalence relation on A. ...
1
vote
1answer
73 views

Equivalence relation homeomorphisms

Is said to be $X\approx Y$ ($X$ is homeomorphic to $Y$) iff exists a function $h: X \longrightarrow Y$ which is bijective and preserves open sets, this relationship is an equivalence relation on $Top$ ...
0
votes
2answers
536 views

Proving symmetry of Relation and Inverse Relation

Why is this a flawed proof? Knowing that $a$ is an element in $A$ and $b$ is an element in $B$. $R$ being a symmetric binary relation: “Consider any $a$ and $b$ such that $aRb$. Since $R$ is ...