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
1answer
44 views

Is a total order compatible with a partial order?

I was given the following multipart problem. Part 1: Consider the poset ({2,4,6,9,12,18,27,36,48,60,72},|), with the indicated integers and the divides relation. Find the following, if they exist; ...
1
vote
1answer
48 views

Which of the following relations on the set of all people are equvilance relations?

Determine the properties of an equivalence relation. I'm not sure if I am understanding this correctly. A. $\{(a,b)|\ a$ and $ b$ are the same age$\}$ B.$\{(a,b)|\ a$ and $ b$ have the same ...
0
votes
2answers
27 views

Prove $(n,m)R(r,s) \equiv (n>r) \text{ or } (n=r \text{ and } m\geq s)$ is an order relation.

Prove $(n,m)R(r,s) \equiv (n>r)\text{ or } (n=r\text{ and } m\geq s)$ is an order relation. So I have to prove reflexivity, antysimmetry and transitivity. I could prove reflexivity but I'm having ...
1
vote
1answer
53 views

If there are Predicates before Predicate Calculus, why is it called such?

In my understanding, predicates are synonyms of relations: mappings of an ordered set (a,b) to the set of values "True" and "False" Well, propositional calculus comes before predicate calculus, and ...
0
votes
2answers
32 views

How do I find a partition of an equivalence relation?

Say I have the function: $$x\,R\,y \iff y = 3^k$$ for some $k \in \mathbb Z$ and the set is: $$A = \{1,1/3,1/27,1/4,3,1/36 , 2,2/9,9/4, 5\}$$ So in this scenario, how do I find the partitions of the ...
0
votes
1answer
23 views

Relations and Equivalence Sequences

A relation is defined on the set $A=\{a + b\sqrt{2} \; : \; a, b \in \mathbb{Q} \text{ and } a + b\sqrt{2} \neq 0\}$ by $xRy$ if $x/y$ is in $\mathbb{Q}$. Show that $R$ is an equivalence relation and ...
0
votes
1answer
19 views

Equivalence Classes points on the plane

I'm confused about the topic of equivalence classes. $x=(a,b) , y=(c,d)$ are points on the plane. $xRy$ iff: 1) $a+b = c+d$ 2) $a^2-b = c^2-d$ 3) $a=c=5 , b=d=20$ 4) $a^4+b^4 = c^4+d^4$ For each ...
0
votes
1answer
20 views

Relations equivalence

$f) x^2-5x+6=y^2-5y+6$ $g) x^2+y^2=1$ Decide whether or not it’s a reflexive, symmetric, transitive and equivalence relation. If R is an equivalence relation, describe the equivalence classes. I ...
0
votes
1answer
21 views

Does a statement have to be true for all conditions to be transitive,symetric,reflexive?

I'm trying to determine if the following are symmetric, reflexive, transitive, equivalence for all-natural numbers but am struggling because they aren't in set notation. Examples of confusing ...
1
vote
1answer
29 views

Prove if $x$ is greatest lower bound of $U$ then $x$ is the least upper bound of $B$

This is one of the problem I have been solving from Velleman's How to prove book; Suppose $R$ is a partial order on $A$ and $B \subseteq A$. Let $U$ be the ...
1
vote
2answers
31 views

Antisymmetric Relation: How can I use the formal definition?

So I can determine whether a certain relation is antisymmetric, by using a digraph. My understanding through a digraph is that if there is only 1 way streets and/or loops between edges, it's ...
0
votes
1answer
22 views

Complementary Relation Proof

If $R$ is reflexive, prove that $R^c$ is irreflexive. If $R$ is asymmetric, prove that $R^c$ is reflexive. Where $R^c$ = complement of $R$. I just can't figure out anything to say for the first one ...
-4
votes
1answer
56 views

How to figure out how many entries are in a relation

I have the domain $A = \{1, 2, \ldots , 1000\}$. I need to figure out how many non zero entries are in each relation: a. $R_1 = \{\;(a, b) \;|\; a \le b\;\}$ b. $R_2 = \{\;(a, b) \;|\; a + b = ...
1
vote
2answers
60 views

for some or for all

The following text is from Velleman's How to Prove book from the reflexive closure section: According to the definition we gave in the last section, the ...
1
vote
4answers
210 views

Is this relation transitive, reflexive, symmetric?

I am having a hard time identifying transitive relations. I think I understand those that are symmetric, but do correct me if I'm wrong. For a set $S = \{0,1,2,3,4\}$ and a relation $Z = ...
2
votes
1answer
38 views

In a transitive relation does x and z have to be the same element?

I am new to relations on sets and am trying to get my head around transitive relations. I understand the definition of $(x,y) \in R, (y,z) \in R$ and $(x,z) \in R$ However what i am not sure about ...
1
vote
1answer
63 views

Find if relation is reflexive, symmetric or transitive

Let $A = \{1, 2, 3, 4\}$ and let $F$ be the set of all functions from $A$ to $A$. Let $R$ be the relation on $F$ defined by "For all $f, g$ in $F$, $(f, g)$ in $R$ if and only if $f (i) = g (i)$ for ...
1
vote
1answer
25 views

Which of these relations are maps?

List all relations $\{a,b\} \to \{c,d\}$, assuming $a \neq b$ and $c \neq d$. Which of them are maps? So I know the cartesian product gives $\{(a,c),(a,d),(b,c),(b,d)\}$. And the relations will be ...
7
votes
4answers
826 views

“$ x $ is a brother of $ y $.” Why is this not transitive?

I am working on a problem set at the moment, and while checking my answers I realized that I have listed "x is a brother of y" as a transitive relation, while the answers say that it is not. EDIT: I ...
0
votes
2answers
49 views

How do I prove this? (Relations Proof)

So I can't seem to figure out how to prove this. Any help would be greatly appreciated. My professor said a contradiction would work but I don't see where I can make a contradiction. Show that {X ...
1
vote
1answer
41 views

Meaning of at least as late in the alphabetical order

I'm working some problem in Velleman's How to prove book and is faced with a set in it which goes like this: $R1 = \{(x,y) \in A \times A \mid \text{the word $y$ occurs at least as late in ...
0
votes
2answers
25 views

Transitivity of a relation

If a relation contains (a,b) and (a,c), in order for it to be transitive, is (b,c) required, or is (c,b) also required? In my mind, it should require both (b,c) and (c,b), but I'm not certain.
0
votes
1answer
69 views

Given the relation $\{(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)\}$ determine whether it is reflexive, transitive, symmetric, or anti-symmetric.

Given the relation $\{(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)\}\,$ determine whether it is reflexive, transitive, symmetric, or anti-symmetric. I found this set to be reflexive and symmetric. But not ...
1
vote
1answer
28 views

Asymmetric Relation Confusion

$A = \{1, 2, 3, 4\}, R \subset A \times A$ Why is $\{(1,1),(2,2),(3,3)\}$ an asymmetric relation? $(a,b)$ where $a=b$ must come under symmetric relation.
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
187 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
252 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
39 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
67 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
34 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
59 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
44 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
66 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
68 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
38 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
20 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
17 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
34 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
31 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
50 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
40 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
63 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
20 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?