Tagged Questions

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

How many relations $R \subseteq A \times B$ are bijective?

$A$ and $B$ are sets. How many relations $R \subset A \times B$ are bijective? Is there a formula for that? Or can you give me any tips to get a general formula? EDIT: But a relation is a subset of ...
1
vote
1answer
14 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
11 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
21 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
20 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
14 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
13 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
28 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
39 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}$ ...
0
votes
0answers
32 views

Set theory/ relations

The task is to find out whether the following notations are: reflexive symmetric antisymmetric transitive alternative $M \subseteq N$ $M \subset N$ $M \cup N$ $M \cap N$ $M \setminus N$ $M \cap N ...
1
vote
1answer
59 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
42 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
votes
0answers
14 views

Check for transitive relation [closed]

A={Set of all the planes in R3}.The relation being normal in R3,then will the relation be transitive? please give reason
1
vote
0answers
17 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
24 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
22 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
62 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
84 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
97 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
44 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
21 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
29 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
32 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
26 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 ...
-4
votes
0answers
54 views

Is this relation an equivalence relation? If so, identify the equivalence classes. [closed]

Determine if $ρ$ is reflexive, symmetric, transitive, anti-symmetric. In each case, if $ρ$ is an equivalence relation, describe the equivalence classes. $$A = \mathbb R \,\text{ and }\, aρ b \;\text{ ...
1
vote
2answers
71 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
90 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 + ...
1
vote
1answer
84 views

$A = \mathbb{R}$ , and $a\mathrel{p} b$ if and only if $\sin a = \sin b$

My question is: For the relation $p$ described below, determine if $p$ is reflexive, symmetric, transitive, anti-symmetric. In each case, if $p$ is an equivalence relation, describe the equivalence ...
0
votes
1answer
24 views

Transitive Relations on a set

I am trying to study binary relations (for myself, it's not an assignment!) I have the set $\{1,2,3,4\}$, and one of the relations in the exercise is $\{(1,3),(1,4),(2,3),(2,4),(3,1),(3,4)\}$. A ...
1
vote
2answers
35 views

Can a relation be a partial order and an equivalence at the same time?

Can a relation be a partial order AND an equivalence at the same time? For instance, if we have a set A = {1, 2, 3, 4, 5} and a relation R on A defined as R = {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5)}: ...
1
vote
1answer
35 views

How does one find/list equivalence classes?

Can someone explain how I would find/list the equivalence classes (And number of equivalence classes) of these two examples? Example 1: A is the set of all possible strings of 3 or 4 letters in ...
0
votes
1answer
36 views

How would I draw the diagram for this relation?

The question I am trying to solve is below. I have proven it is an order but am unsure how to draw the diagram for it. Can someone point me in the right direction? Let A = {1, 2, 3, 4}, and let R be ...
0
votes
1answer
30 views

How to prove this equivalence relation?

How would one go about proving this is an equivalence relation? I have no idea where to start. $\cal R$ is the relation on $\Bbb Z \times \Bbb Z$, such that $((a, b),(c, d)) \in \cal R$ if and only ...
0
votes
0answers
17 views

Special relations on a finite set

Given a set $S = \{s_1, \dots, s_n\}$, $S \times S$ is the product space of $S$ with itself. Let $S_0 = \{(s_i, s_i), i=1,\dots,n\}$. Are there a name and/or notation for the operation mapping $S$ to ...
1
vote
1answer
36 views

Find all equivalence classes

Let R by a relation defined on pairs $(m,n)$ of integers $m$ and natural numbers $n$ by $(i,j) R (k,l)$ if $il=jk$. Prove that this is an equivalence relation and give the equivalence cases. Show ...
0
votes
2answers
27 views

Transitivity of a relation [closed]

Is the relation {(1,2)(3,4)(5,6)} is a transitive relation. I have found in many references and ncert text that it is transitive. Give reason for u r answer.
1
vote
1answer
23 views

Proving an equivalence relation(specifically transitivity)

I'm currently learning about equivalence relations. I understand that an equivalence relation is a relation that is reflexive, symmetric, and transitive. But I'm having trouble proving the transitive ...
0
votes
1answer
17 views

Composition of relations: Incomplete proof.

Let $R$ be a relation from $A$ to $B$, and $S$ be a relation from $B$ to $C$, and $T$ be a relation from $C$ to $D$. I want to prove that $T\circ (S\circ R)=(T\circ S)\circ R$. This is how I proved ...
1
vote
1answer
39 views

Partial order relation (Antisymmetric property), given a relation $xRy \iff x-y\le 4$

Given the set: $A=\{1,2,3,\dots,19,20\}$. The relation $R$ is defined on $A$ as: $xRy\Leftrightarrow x-y\leq4$ Is $R$ a partial order relation? I know that for a relation to be partial order it has ...
0
votes
1answer
188 views

The “Empty Tuple” or “0-Tuple”: Its Definition and Properties

(I would like to link to a previous discussion on the subject: What is A Set Raised to the 0 Power? (In Relation to the Definition of a Nullary Operation)) In axiomatic (ZFC) set theory, we define ...
1
vote
2answers
29 views

Equivalence Relations (Discrete Math)

Hello I'm having trouble with this math problem on equivalence relations. Let X be any subset of the set of positive integers Z. Define a relation ~ on X as follows: I have reflexive proven, having ...
0
votes
1answer
13 views

Relation symmetric and antisymmetric

Let $A$ a non-empty set. If there is a complete relation on $A$ that is both symmetric and antisymmetric, does it imply that the relation is the "equality" and $A$ has one single element?
0
votes
2answers
18 views

Subset Relation: Is the subset relation a partial order?

I read in a Wikipedia entry (subset in german http://de.wikipedia.org/wiki/Teilmenge): "Every set is a subset of itself" But for example, if A is a set of all sets, with maximum 5 Elements, than A ...
1
vote
1answer
54 views

The composition of the $<$ relation with itself

I am struggle with answering this question. I do not understand how to approach this question. 1.Let <􏰈 denote the less than relation on the set of integers. Describe the squared relation <^2 ...
1
vote
1answer
50 views

Notation interpretation

Consider the set $$\Bbb R^n :=\{x=(x_1,...,x_n):x_1,...,x_n \in \Bbb R \}.$$ For $x,y\in \Bbb R^n$, we define $<$ as below: $$ x<y \iff \exists j \in \{1,..,n \} \left( x_j<y_j \wedge ...
0
votes
0answers
35 views

Implies the $\leq$ relation a lexicographical relation?

Consider the set $\Bbb R^n = \{ x = ( x_1, ..., x_n): x_1,...,x_n \in \Bbb R \}.$ For $x,y\in \Bbb R^n$, we define $ x<y \iff \exists j \in \{1,..,n \}(x_j<y_j)$ $\wedge \forall i \in \Bbb N ...
0
votes
2answers
59 views

Lexicographical order in $\Bbb R^n$?

Consider the set $ \Bbb R^n = \{ x = (x_1, ..., x_n) : x_1, ..., x_n \in \Bbb R \}.$ For $x,y\in \Bbb R^n$, we define $<$,$\leq$ as below: $$ x<y \iff j \in \{1,..,n \} (x_j<y_j) ...
1
vote
1answer
68 views

Lexicographical order

Hello everyone i'm trying to solve an exercise that contains the following istructions. Let it be $ \Bbb R^n = \{ x = (x_1, ..., x_n) : x_1, ..., x_n \in \Bbb R \}.$ Let define on $ \Bbb R^n$ a ...
0
votes
1answer
48 views

For semigroups, $S\preccurlyeq T$ iff there exists an injective relational morpism $\mu: S\to T$.

This is Exercise 1.16 of Howie's Fundamentals of Semigroup Theory. The Details. Definition 1: Let $A$ and $B$ be sets. A relation $\rho$ from $A$ to $B$ is a subset of $A\times B$. Define ...