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
2answers
35 views

Why is {(0,1), (1,2)} an antisymmetric relation?

This is my relation: $R= \{(0,1), (1,2)\}$ I know it is not transitive, because: $$ 0R1 \wedge 1R2 \Rightarrow 0R2,$$ but this is false Now I want to check, if it is antisymmetric. How can I write ...
0
votes
1answer
48 views

Understanding relations: Are these examples correct?

The task is to find examples for the following relations on the set of (and prove its correctness) : 1: antisymmetric and transitiv 2: antisymmetric and not transitiv (intransitiv) 3: not ...
1
vote
0answers
109 views

Proving Reflexivity, Symmetry and Transitivity of a Relation

I'm currently taking an intro discrete math course, and I'm having some trouble understanding the rules of reflexivity, symmetry, and transitivity. The book isn't making a lot of sense to me, and my ...
1
vote
2answers
106 views

Calc I Related Rates Question involving a Circle

Two runners at the same point begin running in opposite directions along a circular track of radius $100$m at a speed of $5$m/s. At what rate is the (shortest) distance between them growing after ...
1
vote
2answers
42 views

Define a relation on the integers such that $a R b$ iff $\;3\mid (a + 2b)$?

I've seen relations defined as functions between sets and as sets of ordered sets; however, I've never seen a relation defined as $3\mid(a+2b)$. What does this mean? --Edit-- I'll try and express my ...
2
votes
0answers
40 views

Prove $[(n, k)] = 7^{*} \iff n - k = 7$

Prove $[(n, k)] = 7^{*} \iff n - k = 7$ given $7^{*} = [(8,1)] \in \mathbb{Z}$ and $k < n \in \mathbb{N}$ using any facts about addition in the Peano System. $k < n \in \mathbb{N}$ is ...
0
votes
1answer
25 views

Relation between nodes in a graph

i'm currently working on a mathproblem in "discrete mathematics for computing". I'm a little behind and have some trouble with one question. "Let ∼ be a relation defined on the nodes on a graph G(N, ...
0
votes
1answer
17 views

Doman and range of a simple relation

Relation xRy if x≥y^2 (on real numbers), I'm assuming the domain is (o, infinity) and the range is all real numbers?
0
votes
1answer
45 views

Equivalence relation for set given as matrix

I need a hint. My task is to proof that ((a11, a12), (b11, b12)) ((a21, a22), (b21, b22)) ∈ R ⇔ a11 + a12 + a21 + a22 = b11 + b12 + b21 + b22 R is equivalnce relation. My problem is that I ...
0
votes
1answer
72 views

Define a relation ~ on ℕ by a~b if ab is a perfect square

So, for this problem: a. Prove that ~ is an equivalence relation on ℝ². (I'm not sure if this is a typo on my professor's part since we are defining a relation on ℕ.) b. Describe the equivalence ...
1
vote
1answer
36 views

Define a relation ~ on ℝ² by (x,y)~(w,z) if x+y=w+z

So, it comes in two parts: a. Prove that ~ is an equivalence relation on ℝ². b. Give a geometric description of the partition of ℝ² formed by the equivalence classes. For a, I have to prove that ~ ...
0
votes
1answer
44 views

The properties of relations $xRy$ if $x\ge y^2$ and $aRb$ if $a|b$.

I am given these 5 questions about the relations $xRy$ if $x\ge y^2$ (on real numbers), and $aRb$ if $a|b$ (on $\mathbb N$). a. Find the domain and range of R. b. Prove or disprove that R is ...
2
votes
1answer
37 views

How many relations are there between the set A and B?

$A =\{1,2,3\}$ and $B=\{a,b\}$ Based on the text, the number of relations between sets can be calculated using $2^{mn}$ where $m$ and $n$ represent the number of members in each set. Given this, I ...
1
vote
0answers
31 views

Suppose A and B are sets. If $|A| = m$ and $|B| = n$, then how many relations are there from $A$ to $B$?

Coudn't I say that it is $m\times n$ relations because the collection of all ordered pairs is the Cartesian Product $A\times B$?
0
votes
0answers
29 views

equivalnce relation for sets given as matrix [duplicate]

I need a hint. My task is to proof that ((a11, a12), (b11, b12)) ((a21, a22), (b21, b22)) ∈ R ⇔ a11 + a12 + a21 + a22 = b11 + b12 + b21 + b22 R is equivalnce relation. My problem is that I have ...
2
votes
1answer
19 views

Symmetric and antisymmetric binary relations

I would like to ask you for an advice. I need to find all binary relations on set A ⊆ N which are symmetric and antisymmetric. Am I right when I thing that result pairs could be just pairs on ...
0
votes
1answer
35 views

Prove that if a relation $R$ on $X$ is not symmetric, but transitive, the collection of pseudoequivalence classes does not partition $X$.

I'm trying to work through this problem for the class I'm teaching, but am getting stuck. I think the key is that there exists some $(x,y)\in R$ such that $(y,x) \notin R$, so $x$ won't be in a ...
-4
votes
1answer
61 views

Is empty set is a reflexive, symmetric, anti symmetric, transitive? [closed]

Is empty set is a reflexive, symmetric, anti symmetric, transitive ?
0
votes
1answer
333 views

How many reflexive relation are there on a set with n elements? [duplicate]

How many reflexive relation are there on a set with n elements ?
0
votes
3answers
43 views

Test the binary relation on the set for reflexivity, symmetry, antisymmetry, and transitivity.

$S = \{0,1,2,3,4,5\}$ $xRy, x+y = 5$ I'm not entirely sure on how to test this for reflexivity, symmetry, antisymmetry, and transitivity, though I understand the rules for each. I guess I'm ...
0
votes
1answer
84 views

Intersect and Union of Reflexive relations

Below are my attempts at two proofs. Let $R$ and $S$ be relations on a set $A$. Assume $A$ has at least three elements. If $R$ and $S$ are reflexive, then $R \cap S$ is reflexive proof: ...
1
vote
0answers
27 views

Uniqueness of smallest element in poset

Prove that a smallest element, if it exists, is determined uniquely. This is follows directly for definition. An element $a \in X$ is called the smallest element of $(X, \preceq)$ if for every $x \in ...
0
votes
1answer
25 views

Proof involving relations

$\def\Rng{\operatorname{Rng}}$ Let $R$ be a relation from $A$ to $B$. For $a \in A$, define the vertical section of $R$ at $a$ to be $R_a$ = $\{ y \in B: (a,y) \in R\}$. Prove that the union over ...
0
votes
1answer
18 views

Find a right inverse of a map with gauss brackets.

I am having a composition of two maps: $$ f:\mathbb{R}->\mathbb{R_0^+},f(x)=x^2 $$ $$ g:\mathbb{R_0^+}->\mathbb{\mathbb{N}},g(x)=\lfloor x\rfloor $$ $$h=g\circ f:\mathbb{R}->\mathbb{N_0}$$ ...
1
vote
1answer
34 views

Find relations on the real number: transitive and/or antisymmetric

$$I\ am\ searching\ for\ a\ relation\ on\ the\ real numbers\ (\mathbb R ),\ which\ sould\ be:$$ antisymmetric and transitive antisymmetric and NOT transitive NOT antisymmetric ,but ...
3
votes
2answers
147 views

Intersect and Union of transitive relations

Let $R$ and $S$ be relations on a set $A$. Assume $A$ has at least three elements. These are my best guesses at these two proofs. The first one I don't feel confident about at all, as it seems I'm ...
1
vote
1answer
37 views

Linear Order relations

Im having a slight issue grasping the concept of Linear Orders among relations. It was made apparent to me that linear orders must first be partial orders(reflexive, anti-symmetric and transitive) ...
2
votes
1answer
17 views

How do I prove that $R=\{(x,y) \in S \times S : x\text{ divides }y\}$ is antisymmetric?

$S=\{1, 2, 3,\ldots, 1000\}$ $R=\{(x,y) \in S \times S: x \mid y\}$ My attempt: Assume $xRy$ and $yRx$. Then $x=ym$ and $y=xn$ for $m$, $n$ in Natural numbers. -So $x=xxn..$ that gets me nowhere. ...
0
votes
3answers
22 views

Example of Relation Help

Example of a relation that is reflexive, not symmetric, not transitive but anti-symmetric. I can't think of an example.
0
votes
1answer
23 views

Why are all singletons confluent?

A relation R of a set M is confluent, if $ \forall x \in M \forall w1,w2 \in M :((xRw1 \land xRw2 ) \to \exists z \in M (w1Rz \land w2Rz)) $ . 1. Someone told me that all singletons, no matter the ...
0
votes
1answer
17 views

Help with Relation aRb if b =a^k

In the set X = {2, 3, 4, 5, 9, 16, 25, 27, 64, 81, 125} was introduced journal R is defined as follows: aRb exists a natural number k such that b = a^k. Draw a graph of the relationship. ...
0
votes
1answer
60 views

to find the smallest and largest number of equivalence relation in a set

Let $s$ be a set of $n$ elements. The number of ordered pairs in the largest and smallest equivalence relation on set $s$ are $n^2$ and $n$. I am able to understand the largest set of equivalence ...
0
votes
1answer
33 views

Equivalence classes, relation, partitions

Let $\sim$ be an equivalence relation on M, and $M/{\sim}$ to be the partition of M by $\sim$, and $\sim_{M/\sim}$ to be the equivalence relation by the partition. How do I show that the two ...
0
votes
1answer
51 views

What is confluence?

I got a worksheet at university last week, and the first task is: A relation R of a set M is confluent, if $ \forall x \in M \forall w1,w2 \in M :((xRw1 \land xRw2 ) \to \exists z \in M (w1Rz \land ...
0
votes
1answer
39 views

Find a map $g: \mathbb{R}^2 \rightarrow \mathbb{R}$ to prove surjectivity for a given $f:\mathbb{R} \rightarrow \mathbb{R}^2 $

When the following is given: Let $f:\mathbb{R} \rightarrow \mathbb{R}^2 $ be given by $f(x)=(4x, -x)$ for all $x \in \mathbb{R}$ How to find a map $g: \mathbb{R}^2 \rightarrow \mathbb{R}$ ...
1
vote
1answer
86 views

Is a subobject classifier logically equivalent to set-inclusion?

Can one subsume the notion of set-inclusion $\subseteq$ and $\subset$ with the notion of a subobject classifier, expressed via an injective morphism $\hookrightarrow$? Specifically: Are the ...
0
votes
1answer
49 views

The relation $a + d = b + c$ between pairs $(a, b)$, $(c, d)$ is an equivalence relation

Let R be the relation on $Z × Z$, that is elements of this relation are pairs of pairs of integers, such that $((a, b),(c, d))\in R$ if and only if $a + d = b + c$. Show that R is an equivalence ...
1
vote
1answer
27 views

Non strictly convex “singleton” preferences

A relation $\succeq $ over a vector space $X$ is rational if it is transitive and complete. We say $x\succ y$ iff $x\succeq y$ and NOT $y \succeq x$ Moreover $x\sim y$ iff $x\succeq y$ and $y ...
0
votes
0answers
26 views

process of $(a,b)R(c,d)\implies a\cdot b(b+c)=bc\cdot (a+d)$ being transistive relation..

My question was is as follows: If a relation $R$ defined as $\mathbb Z\backslash\{0\}\times\mathbb Z\backslash\{0\}$ as $(a,b),(c,d),(e,f) \in \mathbb Z\times \mathbb Z$ where $(a,b)R(c,d)\implies ...
1
vote
1answer
40 views

drawing diagram for binary relation

im working on the practice problem on unit about sets and relations The question is: Let a = {1,2,3,4} and R be a binary relation on A x A given by: ((a,b),(c,d)) ∈R if and only if a divides c and b ...
1
vote
1answer
70 views

how to fnd if R is an order?

hello i have a upcoming quiz and I was solving practice problems that the instructor gave us. But Im not sure how to approach this problem the problem is: Let $A = \{1,2,3,4\}$, and $\mathcal{R}$ be ...
0
votes
1answer
93 views

How to show that R(binary relation on A x A) is an order?

im working on the practice problem on unit about sets and relations The question is: Let a = {1,2,3,4} and R be a binary relation on A x A given by: ((a,b),(c,d)) ∈R if and only if a divides c and b ...
0
votes
2answers
115 views

Relation that is only symmetric, reflexive, antisymmetric or transitive?

What could be a possible example of a relation that's symm, reflex, antisymm, transitive? I am working on practice problems on the unit about Sets and Relations. The question asks me to give a ...
2
votes
2answers
62 views

Anti-symmetric relation given by a matrix

Relation R is given by a matrix $$\begin{bmatrix} 1& 0& 0& 0\\ 1& 1& 0& 0 \\ 1& 0& 1& 0 \\ 1& 1& 1& 1 \end{bmatrix} $$ Is it anti-symmetric? I'm ...
1
vote
1answer
25 views

intersection of antisymetric relations is antisymetric

Suppose $A$ is some set, and $R$ and $S$ are relations on $A$ s.t. $R$ and $S$ are anti-symmetric. I want to prove that $R\cap S$ is anti-symmetric. Let $a,b \in A \ $ s.t. $a\ne b$ and $(a,b)\in ...
1
vote
1answer
35 views

Restriction of an equivalence relation on a subset.

If we have an equivalence relation defined on a set E and S its subset. Is the relation defined on S is also an equivalence one? Thank you for your answers.
1
vote
1answer
36 views

My question is a very basic one about relations

I am learning about relations right now and I have a question about some terms. I am told a relation on $A$ is a subset of $A\times A$. Then I am told a relation $R$ on $A$ is reflexive if for all ...
2
votes
2answers
29 views

Number of Symmetric Relations on a set A

I'm having trouble understanding their explanation. I follow everything up to "The Set $A_2$ contains $(1/2)(n^2 - n)$ subsets..." could someone please help explain this to me? Source: Discrete and ...
0
votes
2answers
74 views

Relations $\rho $ and $\rho^2$ [closed]

If $\rho$ is a relation on a set $A$, define $\rho^2$ by $a\rho^2 b$ if and only if there exists $c$ with $a\rho c$ and $c\rho b$. If $\rho$ is reflexive/symmetric/transitive does $\rho^2$ have the ...
-2
votes
1answer
142 views

determining reflective, symmetric, transitive, anti-symmetric properties and describing equivalence classes

The question: determine if p is reflective, symmetric, transitive and/or anti-symmetric, if p is an equivalence relation, describe the equivalence classes A = Z , and $apb$ if and only if $5 | (2 a + ...