Questions tagged [relations]

For questions concerning partial orders, equivalence relations, properties of relations (transitive, symmetric, etc), a composition of relations, or anything else concerning a relation on a set.

Filter by
Sorted by
Tagged with
1
vote
2answers
781 views

What's the equivalent of the adjacency relation for a directed graph?

I've found several sources describing a relation notated $\sim$ signifying adjacency in an undirected graph, but nothing explicitly describing an equivalent for a directed graph. I've been using $\...
2
votes
1answer
191 views

A characteristic of intersection with cartesian product

Fix some binary relation $f$. Does there necessarily exist a set $C$ such that $(x\times x)\cap f\ne \varnothing \Leftrightarrow x\cap C\ne \varnothing$ for all sets $x$?
2
votes
2answers
619 views

Antisymmetric's Opposite (If existant)

I am learning of Equivalence Relations and for something to be one is has to be: Reflexive (i.e., $aRa$) Symmetric (i.e., $aRb$ $\Rightarrow$ $bRa$) Transitive (i.e., $aRb$ & $bRc$ $\Rightarrow$ ...
2
votes
2answers
85 views

Determine if $(\mathbb N, \Sigma)$ is a poset, look for $\min(\mathbb N, \Sigma)$ and $\max(\mathbb N, \Sigma)$

Let $D(x) = \{y \in \mathbb N : y\text{ is a divisor of } x\}$ and let the relation $\Sigma$ be defined as follows: $$\begin{aligned}x \Sigma y \Leftrightarrow D(x) \subseteq D(y) \end{aligned}$$ ...
-6
votes
1answer
358 views

Order of products and order of multipliers [closed]

I asked this question (and have received an answer) at MathOverflow. Now a little more difficult question: Let $f$ and $g$ are binary relations (on some set $\mho$). The function $f\times^{C} g$ is ...
2
votes
1answer
163 views

Four equivalence relations on a set

Let $G_0$, $G_1$, $H_0$, $H_1$ be four equivalence relations on a set $E$ such that $G_1\cap H_0=G_0\cap H_1$ and $G_1\circ H_0=G_0\circ H_1$. Let $x\in E$. Prove that for every $y\in G_1(x)$, there ...
6
votes
10answers
592 views

Sanity check, is $\{(-9,-3),(2,-1),(7,7),(-1,-1)\}$ a function?

EDIT#2: Yes, I'm crazy! This IS a function. Thanks for beating the correct logic into me everyone! I'm using a website provided by my algebra textbook that has questions and answers. It has the ...
-3
votes
1answer
184 views

Find an elegant proof of a set-theoretic equiality about relations

I am now attempting to prove the following theorem. I am in half-underway of the proof and it seems I can do it by myself. But the proof I am now constructing is not elegant. Could anyone provide a ...
0
votes
2answers
3k views

Proof of equivalence relation

I'm studying for my final exam of discrete mathematics, is an exercise in particular concerning equivalence relations do not know how to start: $$ \text{Let } A = \left\{{3, 5, 6, 8, 9, 11, 13}\right\...
5
votes
2answers
252 views

An analogy between subgroups and equivalence relations.

I have noticed a certain analogy between subgroups of a group $G$ and equivalence relations on a set $X$. I would like to know if there's an explanation for this analogy or a common generalization of ...
0
votes
1answer
152 views

Monotonic Relation

Consider the relations $r_1, r_2, \ldots , r_n$ and consider a relational expression language as follows: $r_i$ is a relational expression, $1 \le i \le n$ $e_1 \circ e_2$ is a relational ...
1
vote
2answers
718 views

Unnecessary property in definition of equivalence relation [duplicate]

Possible Duplicates: Symmetric, Transitive and reflexive Why isn't reflexivity redundant in the definition of equivalence relation? Dependence of Axioms of Equivalence Relation? Let $X$ a ...
2
votes
1answer
126 views

Basic relations theorem

I need to prove that If relations $\rho$, $\sigma$ are both reflexive and symmetric, and their composition $\rho\sigma$ is symmetric, then $\rho\sigma = \rho\vee\sigma$. It's obvious that $\rho\...
3
votes
2answers
105 views

Determine the smallest cardinal of $D$ satisfying certain requirement.

Define the composition of two relation $R\subset A\times B$, and $S\subset B\times C$, as $(a,c)\in R\cdot S$ iff $\exists b ((a,b)\in R\land(b,c)\in S)$. My question is given a relation $R$, what ...
3
votes
1answer
520 views

Gallai's theorem, colourings and equivalence relations

I'm revising a few past papers on Ramsey theory and I've come across a question which feels like it should be easy if it weren't so confusingly set up - I was hoping someone here could help me make ...
0
votes
1answer
3k views

function f satisfies f(xy) = f(x)/y , f(30) = 20. Find f(40)

The function $f$ satisfies $$f(xy) = \frac{f(x)}y$$ and $f(30) = 20$. Find $f(40)$.
0
votes
1answer
544 views

Operator: 'Greater Than Or Equal To' is not 'equasive' or 'inequasive' So what is it?

Lets say we use the following symbols for operators: ...
1
vote
1answer
96 views

Write down all of the elements of $S_6 \times S_6$ which are related to $u = (6, 5)$ under $R'$

Let $S_6 = \{1, 2, 3, 4, 5, 6\}$ and define a relation $R \subseteq S_6 \times S_6$ by $$R = \{(n, m) \text{ | } n < m\text{ or }n = m + 1\}.$$ Question: Write down all of the elements of $S_6 \...
1
vote
1answer
491 views

Questions about maximal element and minimal element

I have question about set theory again. I have non-empty set $A$, and set $K$ of all equivalence relations on $A$. $K$ is partially ordered set regarding subsets ($\subseteq$). now I need to find the ...
1
vote
0answers
59 views

Product of relations described in categorical terms?

Can cartesian product of several (not necessarily binary) relations be described in categorical terms? Don't propose me direct product in the category Set, as it does not preserve the structure of ...
1
vote
2answers
5k views

how to prove that function is injective or surjective?

I have set $A=\{1, 2, 3\}$. $M$ is set of all relations on $A$. $t:M \to M$ is function that returns the transitive closure for each $R \in M$. I need to decide if the function $t$ is injective and/...
-4
votes
1answer
832 views

A counter-example for a set-theoretic problem?

I have proved the below conjecture for the special cases $n\in\{0,1,2\}$. The cases $n\ge 3$ (finite and infinite) are unknown. If the following conjecture is true, I don't expect that you will be ...
1
vote
2answers
683 views

Is this transitive relation or not? [closed]

Is A = {(1,1) (1,2) (2,1)} a transitive relation on {1,2}? It is confusing. Yes and No both seems to be right. I only need a hint.
6
votes
0answers
593 views

Examples of proofs by induction with respect to relations that are not strict total orders.

I have read this Wikipedia article and found it fascinating. I came across it after I tried to prove a certain statement with a method resembling induction in the set of natural numbers but ordered by ...
0
votes
1answer
547 views

Construct a graph G for which the is-adjacent-to relation is antisymmetric.

Background: In this a graph is G=(V,E) where V is the set of all vertices and E is a set of 2-element subsets of V. For example: G=({1,2,3,4},{{1,2},{1,3},{2,4}}). E stands for edges similar to a line ...
1
vote
1answer
122 views

I noticed a pattern, does this have a name?

First of all I am a programmer, not a mathematician, so I may articulate what I am trying to say very poorly. I was working with powers of $2$ when I noticed a relationship I had never noticed before. ...
0
votes
2answers
3k views

How to Prove a Simple Graph is Hamiltonian If and Only If Its Closure is Hamiltonian

Question: Prove a simple graph $G$ is Hamiltonian if and only if its closure is Hamiltonian. $|V(G)|=n$, $\deg(u)+\deg(v)\ge n$ ($u$ and $v$ is a pair of non-adjacent vertices on $G$) I know if $...
0
votes
1answer
466 views

How to Find a Specific Relation on a Set

A={1,2,3}, find ordered pairs on A which satisfy 1) R1 is transitive 2) R2 is non-symmetric and non-antisymmetric At first, I thought 1) is a simple question, and the result is {<1,2>,<2,3>,&...
1
vote
1answer
3k views

Partial Order Relations and Total Order Relations

Question: A={1,2,3} 1) How many partial order relations can be induced over A ? 2) How many total order relations can be induced over A ? 3) Does A exist a transitive relation? I guess total order ...
1
vote
1answer
179 views

Pairwise comparisons of maxima of differences between ordered n-tuples?

I have some ordered tuples $a,b,c$, and I am interested in the following relation: $$ a\succ b \Leftrightarrow \max_i \{a_i-b_i\} >\max_i\{b_i-a_i\} $$ That is, I'm interested in the maximum ...
1
vote
1answer
179 views

Name of binary relation: if $(x, y)\in R$ then there is no $z$ such that $(y, z)\in R$

Is there a term for a binary relation $R\subset A^2$ on some set $A$ such that if $(x, y)\in R$ then there is no $z$ such that $(y, z)\in R$ ? Are there any examples of it? Are there any related ...
1
vote
1answer
3k views

Is smallest binary tree simply root node? Or does it need to have two child nodes?

Apologies for this rather simplistic question, I've just started looking at binary trees and the material I've been provided wasn't explicit about this. Presumably a parent node of a binary tree can ...
-3
votes
1answer
129 views

Simplify a formula about relations

Let $F$ is an $n$-ary relation (with $n$ being any index set). Can the following formula be simplified? $$(\lambda x\in n:s(x))\in F$$ ($s$ is some function). Here $\lambda$ is defined as: $$(\...
4
votes
1answer
1k views

When is the composition of partial orders a partial order?

I have been doing some thinking about the compostition of relations and I've had trouble remembering a number of simple facts about what happens when we compose specific types of relations. I've had ...
2
votes
2answers
7k views

Checking the binary relations, symmetric, antisymmetric and etc

this is my first post. My homework was to check each of tables and findout they are reflexive, symmetric, antisymmetric and transitional. I would appreciate your help. I need someone to check my ...
2
votes
3answers
2k views

Set Theory: Symmetric Relations

I was just trying to figure out this problem I came across. For a set $X = \{1, 2, 3, 4, 5\}$ is it possible to come up with a relation on $X$ that is symmetric, but neither reflexive nor transitive? ...
4
votes
3answers
2k views

Relations (Binary) - Composition

Let $R = \{(a,b), (b,c), (c,d)\}$ How can I figure out why $R^{2} = \{(a,c), (b,d)\}$? This there a mathematical proof (or formula) to determine this for larger set of relations? Is it always first ...
0
votes
1answer
104 views

Partial Ordering over a subset of a set

Given a partial ordering $R$ over a set $S$ is it true that for every $A\subseteq S$ that $R$ is also a partial ordering over $A$? I think so but I'm not sure.
2
votes
1answer
51 views

Find the background position by mouse pos and its hit area

I'm trying to creating a jQuery plugin where the user can interact with a div element background image. Basically, the background-image is larger than ...
2
votes
2answers
410 views

Smallest and biggest symmetric relations

Can anyone give me some hints about this homework? I`m really stuck. Thank you. Let R is a binary relation in A. Define T and S using R, such that S is the smallest symmetric relation which $R \...
2
votes
1answer
143 views

Making a reflexive and transitive relation into a partial order

$R$ is a reflexive and transitive binary relation with field $A$. Prove that equivalence relation $S$ in $A$ exists and partial ordering $T$ in $A/S$, such that for arbitrary $x$ and $y$ from $A$ the ...
0
votes
1answer
96 views

An equation with arbitrary binary relations

Let $f$, $g$, and $b$ are binary relations (on some set $\mho$). Let the predicate $F$ be defined by the formula $F(a)\Leftrightarrow (a\circ f^{-1})\cap (g^{-1}\circ b)\ne\emptyset$ for every binary ...
1
vote
3answers
402 views

Generating a minimal transitive relation containing a given collection of transitive relations

Suppose I have a collection $U$ of transitive binary relations on an arbitrary set $A$; elements of $U$ are subsets $S$ of $A \times A$ such that if $(a,b) \in S$ and $(b,c) \in S$ then $(a,c) \in S$ ...
0
votes
2answers
1k views

Find the number of binary relations.

Let $X$ = {$a,b,c,d,e$}. Let us call a binary relations $R$ on $X$ special if it satisfies all of the following conditions: (i) $R$ is reflexive, (ii) $R$ is symmetric and (iii) $R$ contains the pair (...
1
vote
0answers
131 views

About function inj, surj and something else. Is this exercise resolved correctly?

This is my problem: For every couple of integers $(a,b)\in\mathbb{Z}\times(\mathbb{Z}\backslash\{0\})$ we denote with $r(a,b)$ the remainder of the division between $a$ and $b$. Consider the ...
1
vote
1answer
179 views

Hints needed on basic proof involving functions and relations.

Let $F = \{f\mid f\colon \mathbb R \to \mathbb R\}$, and define a relation $S$ on $F$ as follows: $S = \{(f,g) ∈ F \times F \mid \exists h \in F :f = h\circ g\}$. Let $f$, $g$ and $h$ be the functions ...
0
votes
1answer
3k views

directed graph representing the inverse relation

Let $R$ be a relation on a set $A$. Explain how to use the directed graph representing $R$ to obtain the directed graph representing the inverse relation $R^{-1}$ ($R$ inverse).
1
vote
1answer
234 views

Composition of relations

Let $R$ be the following relation from $\{1, 2, 3\}$ to $\{a, b, c, d\}$: $$R = \{(1, a), (1, d), (2, c), (3, a), (3, d)\}.$$ Let $S$ be the following relation from $\{a, b, c, d\}$ to $\{1, 2, 3\...
4
votes
3answers
207 views

Books and Papers that have treatment of properties like Idempotence and related operations

Please recommend resources to study Idempotence and other similar properties of processes and operations in depth. I want to know what other properties like Idempotence are there for an operation. I ...
1
vote
2answers
112 views

Minimum size of a subset to know a complete total order

Lets say we have a set $A$. Suppose that $A$ is ordered by $<$, $A$ is completely ordered. $<$ can be defined as $<:=\{(a,b) \in A\times A : a<b \}$ Given that $<$ is transitive, it ...