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

6
votes
1answer
25 views

How to determine an ordering relation?

I would like to determine an ordering relation: We are given a linear order on $\mathbb{N}$ $\leq'$ for all $m,n$ such that $ n\leq' m$ $\iff$ (n is odd and m is even) or ($n$$\leq$$m$ and $m-n$ is ...
2
votes
1answer
219 views

If a relation is to be reflexive, symmetric, transitive, etc., do the properties need to be satisfied by all values?

I want to know if different scenarios in relations must satisfy all the value in the relation. In mathematical relations, a given set relation is reflexive if all the elements in the set exhibit ...
1
vote
1answer
35 views

How can we get the approximate values $a,b,c$?

How can we get the approximate values $a,b,c$? The condition and relation are the followings : $0 < a,b,c < 1$ $a + b + c = 1$ $(1-a)^2 + b^2 + c^2 =1 $
7
votes
4answers
286 views

How to find the appropriate equivalence class?

I would like find the system of representatives & equivalence class for $[(1,-1)]_{\equiv 1}$ and $[(1,-1)]_{\equiv 2}$ given: $R_1=_{def.} (x_1,y_1)\equiv(x_2,y_2) \Leftrightarrow ...
1
vote
2answers
52 views

Partition of Real Numbers

Let R be the set of all real numbers. Is $\{\mathbb R^+,\mathbb R^−,\{0\}\}$ a partition of $\mathbb R$? Explain your answer. My answer is no because of $\{0\}$. I am confused with $\{0\}$. please ...
0
votes
2answers
70 views

Prove or Counter example.For all nonempty sets $A$ and $B$ and for all functions $F: A \to B$, $F(A-B) = F(A) - F(B)$

Prove or Counter example.For all nonempty sets $A$ and $B$ and for all functions $F: A \to B$, $F(A-B) = F(A) - F(B)$ I am pretty lost on this question. I don't feel like its right since it would be ...
0
votes
1answer
37 views

Finding smallest set of real numbers according to a property

This is one of the example problem that has been solved in Velleman's How to prove book: Find the smallest set of real numbers X such that $5 \in X$ and for all real numbers $x$ and $y$, if $x ...
1
vote
2answers
43 views

For $f: A \to B$ with $S, T \subset A $, show that $f(S \cap T) \subset f(S) \cap f(T) $.

Let $f:A\mapsto B$ be given and let $S\subseteq A$ and $T\subseteq A$. Show that, $$f(S\cap T)\subseteq f(S)\cap f(T)$$
0
votes
1answer
67 views

connectivity relation to find the transitive closure

Hello I am having difficulties with this question: Use connectivity relation to find the transitive closure of relation $R = \{(a, e),(b, a),(b, d),(c, d),(d, a),(d, c),(e, a),(e, b),(e, c),(e, e)\}$ ...
2
votes
1answer
54 views

cardinality of cartesian product of m sets

I was proving that the cardinality of Cartesian product of m(m>1) non-empty finite sets is the product of cardinalities of the m sets. it can be easily proved using the fundamental principle of ...
0
votes
0answers
20 views

Is it possible to make $R = \{(1, 0), (0, 1) \}$ antisymmetric without removing elements?

I was wondering if I have the relation $R = \{(1, 0), (0, 1) \}$, is there any way I can make the relation antisymmetric without removing elements? I think not, because since the first part of the ...
1
vote
2answers
75 views

Suppose R is a relation on A. Prove that if R is reflexive then R ⊆ R ◦ R. Counterexample?

Problem: Suppose R is a relation on A. Prove that if R is reflexive then R ⊆ R ◦ R. Counterexample: Let A = {1,2} and R = {(1,1),(2,2),(1,2)}. Then R ◦ R = {(1,2)}. Obviously R⊈ R ◦ R. This is an ...
3
votes
2answers
80 views

Associativity of cartesian product and nested ordered n-tuples

for 3 sets $A,B,C$ is $A\times B \times C = A\times (B\times C) = (A\times B)\times C$ OR to be more specific, is the ordered pair $((a,b),c)=$ ordered triplet $(a,b,c)=$ ordered pair $(a,(b,c))$? ...
1
vote
4answers
55 views

Prove $R$ is an equivalence relation.

I think I'm on the right track. Set $S = N \times N$, and for any two members $(a,b),(c,d)$ of $S$, define $(a,b) \simeq (c,d)$ provided that $ad = bc$. Prove that $\simeq$ is an equivalence ...
1
vote
1answer
63 views

Geometric description of composition of two convex polygons? [duplicate]

The composition was defined as follow: $(a,b)$ $\in$ $(R;S)$ $\Leftrightarrow$ $\exists c | (a,c) \in R \\ $&$ (c,b) \in S$ . Also the composition was defined as the binary product of two ...
1
vote
1answer
41 views

Find equivalence classes (Solution with questions)

I have to find the relation properties and the equivalence classes. $$X = \mathbb{R}^{2}$$ $$(x,y) \sim (u,v) \Leftrightarrow x - y = u - > v$$ Showing the relation properties of the ...
0
votes
1answer
22 views

Let $R$ be a relation on $A$ and $S$ its transitive closure. Prove $\text{Dom}(S) = \text{Dom}(R)$ and $\text{Ran}(S) = \text{Ran}(R)$

I have the following exercise from the book "How to prove it", chapter 4.5, p.211, problem 9. Suppose $R$ is a relation on $A$, and let $S$ be the transitive closure of $R$. Prove that ...
1
vote
1answer
20 views

Proof that $S$ is a partial order when it is the reflexive closure of a strict partial order

Suppose $R$ is a strict partial order on $A$. Let $S$ be the reflexive closure of $R$. Show that $S$ is a partial order on A. ("How to Prove it", Chapter 4.5 exercise 4.a) To prove that $S$ is a ...
1
vote
3answers
27 views

multiplying term on sum

Say I know the following relation holds $$ \sum_i f_i + \sum_i g_i = 0 $$ Now I multipy both sides with a set of vectors $\mathbf v_i$. Will it still be true that $$ \sum_i f_i \mathbf v_i + \sum_i ...
0
votes
1answer
43 views

Divisibility relation: transitivity proof

I'm a bit confused about the proof for this relation. I get the first part, but the second line is where I'm totally muffled! Any help is greatly appreciated :) ** An example would also be ...
2
votes
1answer
33 views

Discrete Mathematics: Relations

Confused about this question: Describe two binary relations $R$ and $S$ on $\{1, 2, 3\}$ that are not equivalence relations, but whose composition $R\circ S$ is an equivalence relation.
3
votes
0answers
53 views

Why is this not a poset after adding zero?

The problem    Consider the following set for divisibility. {1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 96}. If 0 is added, the divisibility relation set will no longer be a poset. Please ...
1
vote
2answers
54 views

What is subset partial order

This is one of the example problem solved in Velleman's How to prove book: Find the smallest set of real numbers X such that $5 \in X$ and for all real numbers $x$ and $y$, if $x \in X$ and $x ...
1
vote
0answers
64 views

How to construct a transitive relation?

Given a binary relation $\mathcal{R}$ on a set $A$, you can be assured that the relation $\mathcal{R} \cup \mathcal{R}^{-1}$ is symmetric. (I can give a proof of this, if you would like.) I wanted to ...
0
votes
2answers
22 views

Why is this relation not Symmetric

$R_1$ = {(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)} Is this not symmetric ONLY due to the ordered pair (2,4) not having symmetry with (3,4)? I can't seem to find a lot of information on how to deal with a ...
-1
votes
2answers
56 views

Is this relation reflexive?

Suppose $R$ is a relation on $N_4=\{1,2,3,4\}$ such that $R\circ R = R$. How would I prove that $R$ is reflexive? Could you give me some tips about how to start off?
2
votes
1answer
49 views

Is the $\in$ relation a dyadic, or a monadic, relation?

I believe that it's true (correct me if I'm wrong) that When we predicate something of an argument we're saying that that argument is a member of a set intensionally defined just by that predicate? ...
1
vote
1answer
45 views

Order relation of complex numbers

Show what order relations apply: Set $X = \mathbb{C}$. $(z_1,z_2) \Leftrightarrow Re(z_1) \leq Re(z_2)$ "($z_1$ in relation to $z_2$) is equivalent to ((the real part of $z_1$) $\leq$ ...
1
vote
3answers
42 views

Is this relation transitive? $S = \{1,2,3,4\}, R = \{(x,y) | x - y \text{ is even and } x - y \geq 0 \}$

This is my first attempt to make up a relation that is transitive, reflexive, but not symmetric. I can't find a counterexample. There are only a few examples, one being: $$(3,1) \text{ and } (1,1) ...
0
votes
1answer
20 views

Solve the following recurrence by using telescoping

a(n)=2a(n-1) + 2n-1 a(0)=1 I tried below; a(n)-2a(n-1)=2n-1 from here I found P(n)=1, q(n)=2 r(n)=? according to below formula p(n)an()-q(n)a(n-1)=r(n) for n>=1 Since I can not find r(n) ...
2
votes
3answers
31 views

Trying to figure out whether the following relation is an equivalence relation

LEt $R$ be a relation on $\mathbb{N}$ given by $m R n$ iff $m$ and $n$ have the same digit in the tens place. What does it mean to have the same in digit in the tens place?
2
votes
1answer
49 views

Is the following an equivalence relation on $\mathbb{R} \times \mathbb{R} $?

Define $(x,y) R (z,w) $ iff $x + z \leq y + w $. Is $R$ an equivalence relation on $\mathbb{R} \times \mathbb{R} $? So far I got reflexivity and symmetry which are obvious. However, I am stuck on ...
1
vote
2answers
26 views

Relation antisymmetry check

Hello the question I am having trouble with is Describe a binary relation on 1, 2, 3 that is reflexive and transitive, but not symmetric nor antisymmetric. I Have the answer ...
0
votes
0answers
34 views

What does the Dedekind Rule `say'?

In Relation Algebra, the modal law or dedekind rule $$R;S \,\cap\, T \;\subseteq\; (R \cap T;S^\circ);S$$ appears often and I wonder what is the motivation behind it. Moreoever, what does it "say". I ...
2
votes
3answers
42 views

Reflexivity and Order

It seems to me that the most important concept that the idea of an order brings, is tied to the notion of assymetry ( or the weak antisymmetry, if you may ). However, the way the order ...
5
votes
3answers
159 views

Proving transitive property

I have been working on this problem from Velleman's How to prove book: Suppose A is a set, and F ⊆ P (A). Let R = {(a, b) ∈ A × A | for every X ⊆ A \ {a, b}, if X ∪ {a} ∈ F then X ∪ {b} ∈ F}. Show ...
1
vote
1answer
63 views

Cartesian Product characterization in Rel Category (Category of sets and relations) in simpler terms

The question here explains how a cartesian product of sets are specified. It is difficult for me to follow it; for example, I do not know about "symmetric monoidal category". Can anybody please ...
4
votes
1answer
168 views

Can someone verify my answers to these questions regarding this poset?

Problem: 18. Answer these questions for the poset ({{1}, {2}, {4}, {1,2}, {1,4}, {2,4}, {3,4},{1,3,4}, {2,3,4}}, $\subseteq$) $\quad$a.Find the maximal elements $\quad$b.Find the minimal elements ...
0
votes
0answers
11 views

Relations that satisfy certain properties

I've been trying to come up with functions that are, at the same time, symmetric, bijective and are either irreflective or transitive. I created this question from something my younger brother had ...
0
votes
2answers
58 views

How to mathematically show that the relation is transitive?

Problem: Show that the relation $x R y$ iff $x \leq y$ is a poset over the set of integers $\mathbb{Z}$ My work: I know that to show the relation is a poset or a post order, I have to show the ...
-1
votes
1answer
113 views

How to find union and intersection of these relations?

Problem: Let $R_1$ and $R_2$ be the "divides" and "is the multiple of " relations on the set of all positive integers respectively. That is, $R_1 = \{(a,b) | a \text{ divides }b\}$ and $R_2 = \{(a,b) ...
2
votes
0answers
59 views

Relations in a finitely complete category with images

I can't use tikz inside MathStackExchange; so my question is on an image below.
0
votes
1answer
24 views

why this is transitive relation?

$\rho\subseteq \mathbb{N}\times \mathbb{N},\rho=\{(x,y):y=x+5,x<4\}$ is the relation, so $\rho=\{(1,6),(2,7),(3,8)\}$ in my book it is written that $\rho$ is an transitive relation, but why? I know ...
0
votes
2answers
57 views

How to prove the relation is transitive?

Problem: Consider the relation R on $N$ defined by $x$R$y$ iff $2$ divides $x + y$. Prove that R is an equivalent relation My work: I know that to prove that a relation is an equivalent relation, ...
1
vote
0answers
86 views

Can someone verify my work for finding the following closures?

This is the problem I am currently working on Let R be the relation on the set {0, 1, 2, 3} containing the ordered pair (0,1), (1,1), (1,2), (2,0), (2,2), and (3,0). Find the a.reflexive closure of ...
1
vote
0answers
22 views

Can someone verify my work for finding the following relations?

I am working on this problem Let R be the relation on the set {1, 2, 3, 4, 5} containing the ordered pairs {(1,1), (1, 2), (1,3), (2,3), (2,4), (3,1), (3,4), (3,5), (4,2), (4,5), (5,1), (5,2), ...
0
votes
1answer
57 views

Why can the author just switch the order of the inequality without any reprecussions?

Note: This example is from Discrete Mathematics and Its Applications [7th ed, example 2, page 598]. I understand the idea of a symmetric closure. You add all ...
2
votes
2answers
54 views

Can a relation from A to some other set B also be considered symmetric?

Note: This definition is from Discrete Mathematics and Its Applications [7th ed, page 577]. This is my book's definition of a relation R on a set A My ...
0
votes
1answer
28 views

Transitive Closures

Let the relation R = {(0, 0), (0, 3), (1, 0), (1, 2), (2, 0), (3, 2)} Find the Transitive closure of the relation. So far this is what I'm coming up with: {(0, 0), (0, 3), (1, 0), (1, 2), (2, 0), (3, ...
0
votes
4answers
124 views

Is antisymmetric the same as reflexive?

Note: The following definitions from my book, Discrete Mathematics and Its Applications [7th ed, 598]. This is my book's definition for a reflexive relation This is my book's definition for a anti ...