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

3
votes
1answer
34 views

Is there a specific name for a directed graph that is composed of only loops?

Recently I have been doing practice questions for my Final exam tomorrow and this one question appeared that was interesting, but I couldn't seem to find the other half of the answer to it. Q: Given ...
3
votes
1answer
26 views

Geometric/visual interpretation of transitivity for equivalence relations on $\mathbb{R}$

If we graph equivalence relations on $\mathbb{R}$ on the plane $\mathbb{R} \times \mathbb{R}$, the properties of reflexivity and symmetry give rise to certain geometric properties--i.e. reflexivity ...
5
votes
4answers
300 views

Can functions be defined by relations?

So let us say that for whatever reasons, we are not allowed to use function symbols in first-order logic. Then can we define and use a function only by relations?
2
votes
1answer
34 views

Proving that this relation is transitive

I have seen this question on a book I am reading and could not figure it out fully. The question is as follows: "Suppose A is a set, and $F\subseteq P(A)$. Let $$R_F=\{ (a,b)\in AxA|\text{ for every ...
0
votes
1answer
25 views

suppose $R$ is an equivalence relation on $A$ such that there are only finitely many distinct equivalence classes $A_1,A_2,\ldots,A_k$ w.r.t $R$

Suppose $R$ is an equivalence relation on $A$ such that there are only finitely many distinct equivalence classes $A_1,A_2,\ldots,A_k$ w.r.t $R$. Show that $$A=\bigcup_{i=1}^k A_i$$ Since $A_i\subset ...
2
votes
1answer
51 views

Proving Transitivity

Consider a relation defined by $Z$ where $(a,b) = 2a^2 + b^2 -3ab = 0$ Is the relation $R_1$ reflexive? symmetric? transitive? Is it an equivalence relation? I have said that it is ...
0
votes
3answers
76 views

If R is $(a,b)R(c,d) \iff a+d =b+c$ show that R is an equivalence relation.

The relation R is defined n all positive integers such that, $(a,b)R(c,d) \iff a+d =b+c$ . Show that R is an equivalence relation. In order to be an equivalence relation, R has to be reflexive, ...
0
votes
1answer
35 views

Proof for a relation

Define a relationship $R$ on $\mathbb{Z}$ by declaring that $xRy$ if and only if $x^2 \equiv y^2 (mod 4)$. Prove that $R$ is reflexive, symmetric and transitive. I'm unsure of where to start with ...
0
votes
1answer
36 views

I am working on basic functions, I am asked is x-5=y^2 a function,

i use the square root property and get plus or minus the sqaure root of x-5=y, then I come to my question, for any value of x greater than 5, how many values of y result? I need some insight to fully ...
0
votes
1answer
35 views

Proving theorems on relations

I came across the following three statements about relations. I understand why the statements are true, but I am not sure how to demonstrate them mathematically. In the following, $A,B$ are sets and ...
0
votes
2answers
52 views

How to figure out the solution to this equality problem? [closed]

Let $x, y, z$ be strictly positive, real numbers. If: $$\frac{x^2}{y^2} + \frac{y^2}{z^2} + \frac{z^2}{x^2} = \frac{x}{z} + \frac{y}{x} + \frac{z}{y}$$ then prove that $x = y = z$. Thanks!
2
votes
1answer
46 views

Relations examples (reflexivity, symmetry, transitivity)

I've found the two textbooks I'm using to to be particularly unhelpful in explaining these concepts, especially as they relate to English examples (non-existent). The first few following questions ...
0
votes
1answer
50 views

Properties of a relation on matrices: $(m_1,m_2)\in R$ iff $m_1\cdot m_2$ is defined

Let $M$ be a set of matrices of integers. Let $R$ be the relation on $M$ defined as follows: For any two $m_1, m_2 \in M, (m_1, m_2) \in R$ iff the matrix multiplication $m_1 \cdot m_2$ is defined. ...
0
votes
0answers
37 views

Properties of relations on Z

$$R_3 = \{(x,y) \in \mathbb{Z} \times \mathbb{Z}|\frac{x-y}{5} \in \mathbb{Z}\} $$ $$R_4 = \{(x,y) \in \mathbb{Z} \times \mathbb{Z}|x > y \} $$ I need to know which one is reflexive, symmetric, ...
1
vote
2answers
94 views

Why relations are defined as the smallest

Often relations are defined as follows: The xxxxx relation is the smallest relation satisfying... My question is why relations are defined as the smallest ...
0
votes
2answers
33 views

Relations on set A and conditions of existence of descending chains

I am reading through the Elements of Set theory by Herbert Enderton and even though I have passed this exercise long ago,the more I look at my solution the less I believe it. Problem goes like this: ...
2
votes
1answer
42 views

Terminology on pullbacks

I'm quite confused with the use of pullbacks, and in particular I wonder which terminology I shall use in the following examples. Let $X$ and $Y$ be arbitrary sets. Suppose that $f,g:X\to Y$ and I ...
7
votes
1answer
623 views

What is meant by “m|n”? Two letters separated by a vertical bar (|)

I am new to this subject, and not not sure what "|" symbol means on this statement. Let $R_2 \subset\Bbb N \times\Bbb N$ be defined by $(m, n) \in R_2$ if and only if $m|n$.
1
vote
2answers
31 views

If $R$ is a transitive realation, then $R\circ R\subseteq R$

Here's the question I'm struggling with: Let R be a transitive relation on a set A. Prove the R composed with R is a subset of R. I'm kind of lost on how to prove this. I've started with saying: ...
2
votes
3answers
78 views

What is it called when !(a < b) and !(b < a) implies a = b?

I thought it would be some kind of symmetric equality but its impossible to do a google search on this, all I get are definitions of reflexive, symmetric and transitive. I'm not really sure which ...
1
vote
1answer
14 views

Equivalence between different definitions of transitive closure

Let $W$ be an arbitrary, non-empty set and let $R$ be an arbitrary binary relation on $W$. Define the transitive closure of $R$ as $R^+ = \bigcap \{ R' \; | \; R' \text{ is a binary transitive ...
2
votes
1answer
46 views

Relations and functions with valence 0

From http://en.wikipedia.org/wiki/First-order_logic#Non-logical_symbols Relations of valence 0 can be identified with propositional variables. For example, P, which can stand for any ...
3
votes
3answers
52 views

An example of symmetric transitive relation that is not reflexive on a set of natural numbers $\mathbb{N}$ [duplicate]

An example of symmetric transitive relation that is not reflexive on a set of natural numbers $\mathbb{N}$. My guess is that such relation does not exist, but I don't know how to prove it.
1
vote
2answers
35 views

What is the name of the Speed, Distance, Time relationship?

Really simply, I'd like to know if there is a name used to describe the speed, distance & time relationship. i.e. As this is basically the same relationship that applies to current, voltage and ...
0
votes
1answer
43 views

How many relations exist in the set of A

When A = {1,b,ø}, how many reflexive relations exist on the set? I have said that AxA={(1,1), (b,b), (ø,ø), (1,b), (1,ø), (b,1), (b,ø), (ø,1), (ø,b)} Would I be right in saying that there are only 3 ...
0
votes
0answers
54 views

Is this connected relation?

My task is to check if this is preference relation (connected and transitivited) $$ f \succeq g \Leftrightarrow \forall x\in [0,1] f'(x) \leq g'(x) $$ My solution is: that this relation is not ...
1
vote
1answer
30 views

A question on relations

Problem Statement: Let $A$ and $B$ be sets. Many books define a relation $\mathcal R$ from $A$ to $B$ to be a subset $ \mathcal R \subseteq A \times B $. Show that such an R is a ...
5
votes
2answers
35 views

Two functions whose order can't be equated - big O notation

Our teacher talked today in the class about big O notation, and about order relations. she mentioned that the set of order of magnitude, is not linear Meaning, there are function $f,g$ such that $f$ ...
0
votes
3answers
114 views

What would make a function reflexive, transitive, and/or symmetric?

A binary relation $R$ is a subset of the Cartesian product between two sets $X$ and $Y$, containing a set of ordered pairs $\{(x,y) : x \in X, y \in Y\}$. $R$ is a function if each element of $X$ is ...
1
vote
3answers
35 views

How many reflexive binary relations there are on a finite countable set?

We know that binary relation is subset of Cartesian product made by set on to itself. let's say we have a set with two elements $A=\{0,1\}$ So Cartesian product is $C=A\times A = ...
2
votes
2answers
71 views

Binary relation, reflexive, symmetric and transitive

I have a question regarding an image. I'm currently studying binary relations and the following image confused me: What got me confused is that the page from which I got the link ...
1
vote
0answers
29 views

A partial order with more properties than would be expected

Consider the relation: $$\langle x_1,x_2\rangle\prec\langle y_1,y_2\rangle\iff x_1,x_2,y_1,y_2\in\Bbb N\wedge x_1y_2<x_2y_1.$$ This is usually used for defining the (positive) fractions $\Bbb ...
0
votes
1answer
28 views

New way of combining information in graphs

So, I am working for a social project involving graph theory. I have a dynamic dataset (weighted and undirected), I made graphs out of them ( for 10 years ). Now, I am trying to find out relations ...
0
votes
1answer
55 views

Understanding the difference between relations and functions.

$R=\{(1,2),(1,3)\}$ is a relation but not function. The logic for this is that if the first element of every ordered pair must remain different, then it is said to be function. Otherwise, it's just ...
0
votes
2answers
53 views

Sets and Relations in Math

I have not knowledge about relations, could you help me to solve this excercise step by step, to use in futures excercices? Thanks for your time. Given the set $A = \{1, 2, 3, 4\}$ and $B = \{1, 3, ...
0
votes
0answers
27 views

Produce a list of the most-similar units, given various correlations/relationships

I have a database full of units (U1 - U50, U51...) where every unit has the same standard attributes (A1 - A10) and where a % of each attribute defines the amount of that attribute for that particular ...
2
votes
3answers
36 views

let A be a set of 6 distinct postive integers each <= 12, show that the sum of non empty subests of A cannot all be distinct [closed]

let A be a set of 6 distinct postive integers each <= 12, show that the sum of non empty subsets of A cannot all be distinct. for when does this not continue to hold up ( ie instead of 12 , its ...
0
votes
1answer
16 views

Relations - Logical Boolean Matrix

I am having trouble with the following question: Relations $S$ and $R$ are defined on the set $$\{1, 2, 3, \ldots, 12\}$$ as follows: $$R = \{(x, y)\mid xy = 12\}$$ $$S = \{(x, y)\mid 2x = 3y\}$$ ...
0
votes
1answer
24 views

Relations - Ordered Pairs

I have the following question: Relations $S$ and $R$ are defined on the set $$\{1, 2, 3, \ldots, 12\}$$ as follows: $$R = \{(x, y)\mid xy = 12\}$$ $$S = \{(x, y)\mid 2x = 3y\}$$ Write the ordered ...
1
vote
1answer
34 views

Describing a partition for an equivalence relation?

Describe the partiton for the equivalence relation. For each $x,y\in \mathbb{R}$ xRy $\iff$ $x-y\in \mathbb{Z}$ Now I am not sure how to find a partition for this I guess one could have negative ...
0
votes
1answer
36 views

showing if $ x\equiv_my\rightarrow\frac{x}{r}=\frac{y}{r}$

How would I show this proposition. $ x\equiv_my\rightarrow\frac{x}{r}=\frac{y}{r}$ I will make $\frac{x}{r}$ capital X because it is easier to write. And $\frac{y}{r}$ capital Y. These are the ...
0
votes
3answers
49 views

Giving an equivalence relation that corresponds to set partitions

My question is: Give equivalence relation that corresponds to the partitions A1 = {1,3,5} A2 = {2} A3 = {4,6} of the set A = {1,2,3,4,5,6} I don't know what the format of the relation should be, in ...
0
votes
3answers
69 views

Showing $ x-y\in\mathbb{Q}$ is an equivalence relation?

How would one show the the following is an equivalence relation. The relation R on the real numbers given by xRy iff number $ x-y\in\mathbb{Q}$. This is what I did. Reflexive Let $x \in ...
1
vote
1answer
33 views

Finding the cardinality of $\{X\in \mathcal P(\mathbb R)| |X|=\aleph_0 \}$

Let $S$ be a relation over $\mathcal P(\mathbb R)$ such that $A,B\subseteq\mathbb R: \exists f:A\to B, \exists g: B\to A$ and $f,g$ are injections. Find the cardinality of $\{X\in \mathcal ...
3
votes
5answers
427 views

Real life examples of order relations.

It's easy to find examples of equivalence relations (for example, A shares room with B), but I can't seem to find a real life example of an order relation (that is, a relation that's reflexive, ...
2
votes
3answers
60 views

Name for relationship where a is related to b iff a and b are in different subsets

Yesterday I was out running in the park, and like many others I always run in a counterclockwise direction around the central lake. There are also strange people who always run in a clockwise ...
0
votes
1answer
27 views

Define a numeric relation that is reflexive, but not symmetric or transitive.

Define a numeric relation that is reflexive, but not symmetric or transitive. I've googled on this one quite a bit and am stuck.
0
votes
0answers
28 views

Finding the composition of relation?

Let $R=\{(1,5),(2,2),(3,4),(5,2)\}$ $S=\{(2,4),(3,4),(3,1),(5,5)\}$ $T=\{(1,4),(3,5),(4,1)\}$ 1.Find $R$ composite $T$ 2. Find $R$ composite $R$ 3. Find $T$ composite $T$ For all these I made a ...
-1
votes
1answer
74 views

Showing a counter example $(A\times B)\times C=A\times (B\times C)$

Showing a counter example $(A\times B)\times C=A\times (B\times C)$ I think $A=\{1\}$ $B=\{2\}=C$ Would work but I am not sure...
6
votes
10answers
2k views

I need a relation which is not reflexive, not symmetric, and not transitive

I need an example of a relation which is simultaneously not reflexive, not symmetric, and not transitive. Any accessible examples? Thanks in advance.