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

-2
votes
1answer
94 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: ...
2
votes
1answer
2k views

Symmetry and transitivity for the union of two equivalence relations

Let $R \subseteq A \times A$ and $S \subseteq A \times A$ be two arbitary equivalence relations. Prove or disprove that $R \cup S$ is an equivalence relation. Reflexivity: Let $(x,x) \in R$ or $(x,x) ...
3
votes
1answer
286 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 ...
-3
votes
1answer
199 views

Does an identity exist for ALL functions?

Does an identity exist for all the functions? If not then what kinds of functions do and do not have these identities? For example, 1 is a multiplicative identity for integers, real numbers, and ...
5
votes
3answers
3k views

Is there a relation which is neither symmetric nor antisymmetric?

I've proved that there are relations which are both symmetric and antisymmetric ($\forall a \forall b (aRb \rightarrow (a=b))$) and now I'm trying to prove that there are relations which are neither ...
11
votes
2answers
300 views

Can we extend the definition of a continuous function to binary relations?

Let $X,Y$ be topological spaces. A function $\phi:X\to Y$ is continuous iff for any open subset $A\subseteq Y,$ the preimage $\phi^{-1}(A)$ is open in $X.$ We could similarly define a relation ...
1
vote
3answers
1k 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
694 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
86 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
45 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
148 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
108 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
76 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
161 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
1answer
41 views

Two terminology question about relations

Is there a name for constructing a set from a relation (or, more generally speaking, from a set of pairs that are tuples)? For example, let $R = \{(0, 1), (1, 2), (2, 3)\}$; if you collect all the ...
5
votes
7answers
569 views

Branch of math studying relations

There are many branches of mathematics (analysis, algebra, group theory, logic, ...). Now, I'm interested in relations and their special kinds (like equivalence relation) and their properties. I'd ...
0
votes
2answers
405 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 ...
4
votes
2answers
275 views

The fibres of a map form a partition of the domain.

This is a question from the free Harvard online abstract algebra lectures. I'm posting my solutions here to get some feedback on them. For a fuller explanation, see this post. This problem is from ...
1
vote
0answers
69 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
124 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 ...
1
vote
1answer
149 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, ...
0
votes
3answers
212 views

Two questions about equivalence relations

Question 1: Let $x,y \in S$ such that $x\sim y$ if $x^2 =y^2\pmod6 $. Show that $\sim$ is an equivalence relation. This is what I tried: Reflexive: $x^2\pmod6 = x^2$ implying $x\sim x$ ...
1
vote
2answers
60 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 ...
2
votes
1answer
105 views

What is a binary relation like whose reflexive transitive closure is a partial order?

Let $R$ be a reflexive binary relation and $R^*$ be its reflexive transitive closure. The question is what is the equivalent condition in terms of $R$ to $R^*$ being a partial order. Intuitively, a ...
3
votes
3answers
173 views

What's the name for the equivalence induced by a function on its domain?

Any function $f$ with domain $X$ induces an equivalence relation on $X$, with classes $$\{f^{-1}(\{y\})\,:\, y \in \operatorname{im}f\;\} .$$ Is there a name for this equivalence? Thanks!
1
vote
1answer
126 views

Equivalence Class

Let $A:= \{1,2,3,\dots\}$ and $P := A \times A$. Now define a relation on $R$ on $P\,$ by $$(x,y)R(a,b) \iff x^y = a^b$$ 1) Determine the equivalence class $[(9,2)]$ of $(9,2)$ Note that I already ...
3
votes
2answers
163 views

Proof that the relation $5 \mid (a + 4b)$ is symmetric and transitive

Take the relation $R$ to be defined on the set of integers: $$aRb \iff 5 \mid (a + 4b)$$ As part of a larger proof, I have to show that $R$ is both symmetric and transitive. I'm lost. I see the ...
1
vote
1answer
2k views

Number of reflexive relations defined on a set A with n elements

Problem: If a set $A$ has $n$ elements in it, how many reflexive relations can be defined on it? My solution Is the answer ...
0
votes
2answers
137 views

Equivalence relation on $\mathbb{R}^2$

I've been looking at some equivalence relations and was wondering how to define an equivalence relation on $\mathbb{R}^2$ by $(w,y)\sim(x,z)$ if $(w,y)=(cx,cz)$.
0
votes
2answers
55 views

Finding a untransitive relation

I have tried without luck for a few hours now... given $$A=\{1,2,3\}$$ find $R \subseteq A \times A$ such that $R \cup R^2$ is not transitive.
2
votes
1answer
119 views

Questions about power sets and their ordering

Okay, so I'm stuck on a question and I'm not sure how to solve it, so here it is: In the following questions, $B_n = \mathcal{P}(\{1, ... , n\})$ is ordered by containment, the set $\{0,1\}$ is ...
0
votes
1answer
68 views

Relation on $S\times S$

I am having problem in making relations for this question. $S = \{1, 2, 3, 4\}, A = S \times S; (a,b) R (c,d)$ if and only if $ad = bc$. I have made the following relations, but I am not sure ...
1
vote
4answers
980 views

Why is this relation not transitive but R = {(3,4)} is ?

While studying relations, I came across a strange question. Set $A=\{1,2,3,4\}$ on which the relation $R=\{(2,4),(4,3),(2,3),(4,1)\}$ is defined. It is said in the answer that the relation is not ...
2
votes
3answers
893 views

Bijective Function between Uncountable Set of Real numbers and a set of all functions

Let $S$ be the set of all real numbers in $(0, 1)$ having a decimal representation which only uses the digits $0$ and $1$. So for example, the number $1/9$ is in $S$ because $1/9 = 0.1111\ldots$, ...
3
votes
4answers
163 views

The equivalence relation $(z_1, n_1)\sim(z_2, n_2) :\Leftrightarrow z_1 \cdot n_2 = z_2 \cdot n_1$

Given the relation $(z_1, n_1)\sim(z_2, n_2) :\Leftrightarrow z_1 \cdot n_2 = z_2 \cdot n_1$ on the set $\mathbb Z \times \mathbb N$. a) Prove that $\sim$ is an equivalence relation. Here is ...
0
votes
4answers
58 views

Help create this relation

$A=B=\mathbb{Z}^+$. Define a relation $R$ by $$ a\;R; b \text{ iff } b = a \bmod 6.$$ Please help me write the set relation. Will the set relation contain only the multiples of 6?
0
votes
1answer
60 views

Stuck with relation

Here is a question, A = {1,2,3,4,6} = B, $aRb$ iff $a$ is a multiplier of $b$ . Now I think the whole cartesian product of AxB should be the relation as every number is somehow a multiplier of ...
1
vote
1answer
157 views

Is $x^3-yx^2 = y^3-xy^2$ transitive?

I'm asked to prove that the relation $R$ on $\mathbb{C},$ $xRy \iff x^3-yx^2 = y^3-xy^2$ is an equivalence relation. It's easily shown it's reflexive and symmetric, but I'm having problems with its ...
1
vote
2answers
2k views

Proving this relation is transitive

Let $r$ be a relation on $A \times A$ such that $(a,b) r (c,d) \iff ad = bc.$ How can I show that this relation is transitive, ie. $(a, b)r(c,d)$ and $(c,d)r(e, f) \implies (a,b)r(e,f)$? I tried to ...
1
vote
2answers
1k 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 ...
0
votes
1answer
550 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).
3
votes
1answer
144 views

Equivalence relation independence from G.C.Rota paper?

On page 4 of Many Lives of Lattice Theory the author wrote: "Two equivalence relations on a set are said to be independent when every equivalence class of the first meets every equivalence class of ...
0
votes
2answers
2k views

Equivalence Relations and Inverse Relations

Prove that if $R$ is an equivalence relation on a set $A$, then $R^{-1}$ is also an equivalence relation on $A$. Solution: We know that $\forall R\in A$, $$ R = \{(a, b) | (b, a)\in A\} $$ ...
0
votes
1answer
175 views

Sets and Relations

I've been having quite a bit of trouble with this topic and I'm in need of some help with this question. Determine whether easy relation is reflexive, symmetric, or transitive. $A=\mathbb{R}$; ...
1
vote
0answers
53 views

Term for generalized antisymmetry?

As I understand it, a binary relation $R$ over a set $A$ is antisymmetric if for all $a, b \in A: aRb \land bRa$ implies $a = b$. Now, suppose that I have an equivalence relation $E$ over the set ...
1
vote
1answer
84 views

Proving a relation is asymmetrical

Can someone please help? I am trying to answer the following: Consider the relation $T$ on $\mathbb{Z}$ given by $$xTy \Longleftrightarrow x + 1 \le y;$$ Is $xTy$ asymmetric? $xTy ...
0
votes
1answer
87 views

Can a group be defined in terms of a relation on a set?

Wikipedia defines a group as "an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element." I keep thinking that there is a ...
6
votes
2answers
3k views

If a relation is symmetric and transitive, will it be reflexive? [duplicate]

Possible Duplicate: Why isn't reflexivity redundant in the definition of equivalence relation? We had a heated discussion in class today and i still cant be sure if the professor was ...
2
votes
1answer
89 views

Is this relation transitive if $n=m$?

If $X$ is a set and $n \in \mathbb N$, then $[X]^n$ will denote the set of all subsets of $X$ with exactly $n$ elements. For a set $X$ and natural numbers $n$ and $m$ define a relation $R$ on $[X]^n$ ...
0
votes
1answer
111 views

Need Help in Tabular Notation to represent a Relation

I am stuck with a question. It is stated below. Let $R$ be a relation defined on the set of integers $\mathbb Z$ by the rule $aRb \iff |a-b|\leq 2$. Write the relation $R$ as a set. Now there ...