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
183 views

Is there relation that is symmetrical, transitive and non-reflexive?

We must show that there exists some kind of $\alpha$ relation $\alpha ⊆ X \times X$ which has these conditions : if this relation is I and II type. I) symmetrical: if $∀x,x' ∈ X : (x, x') ∈ \alpha ...
0
votes
1answer
127 views

Relation on countable sets

Let $R$ be a relation on two countable sets $A$ and $B$, where $R\subset A\times B$, with the following properties: $\forall a\in A$ the set $\{b\in B: (a,b)\in R\}$ is finite. For any finite set ...
1
vote
1answer
58 views

The $\mathcal{J}$- class of a primitive idempotent in a regular semigroup.

I am currently studying some basic facts of regular semigroups and Green's relations and I got stuck on the following exercise problem. Let $S$ be a regular semigroup with a primitive idempotent $e$. ...
1
vote
2answers
452 views

equivalence relations and partial ordering

Let $A$ be a set with $6$ elements, $R$ be a relation on $A$ and $n = |\{(x, y) \in A \times A : xRy\}|$. (a) If $R$ is an equivalence relation on $A$, then what is the maximum value of $n$? (b) If ...
4
votes
1answer
97 views

Cases where reflexivity is hard to prove

A couple of remarks at Surjections and equivalence relations lead me to wonder: are there any important and/or interesting examples of reflexive relations whose reflexivity is hard to prove? There are ...
1
vote
2answers
392 views

Two questions about monotonicity of entailment.

I wonder about two things. First, how do we prove that entailment in some logic is monotonic? The second one - What is the relationship between monotonicity of logic and deduction theorem? It seems ...
2
votes
2answers
133 views

Who is Epsilon ($\epsilon$)? a binary relation?

I was reading: Transitive set ordered by epsilon and http://www.princeton.edu/~jburgess/PHI323S13Problems.pdf (ex. 4) so, who is epsilon? Thanks in advance!
1
vote
0answers
71 views

Not closed under equality?

One of the Peano axioms state that "For any $a \in \Bbb N : a = b, b \in \Bbb N$." An example where transition is not closed under equality is the relation to friends. C may not be B's friend, but A ...
0
votes
0answers
67 views

function of 2 variables in UML, how to define relation?

when we have a a Relation of 1 variable such as Y=R1(X)(i used closed-form representation of my relation instead of tree or table representaton or ) with ...
1
vote
2answers
520 views

$(a,b)\,R\,(c,d)\iff a+2b=c+2d:\;$ Equivalence classes of a Partition

Let $S$ be the Cartesian coordinate plane $\mathbb{R}\times \mathbb{R}$ and define the equivalence relation $R$ on $S$ by $(a,b)\,R\,(c,d)\iff a+2b=c+2d$. $\hspace{1cm}$(a) Find the partition $P$ ...
0
votes
1answer
68 views

$R\subset S\times S$ for $S=\{1,2,3\}$: A Graph-Theoretic Approach

So I am given the relation $R=\{(1,1),(2,2),(3,3),(1,2),(1,3)\}$ and asked which of the properties reflexive, symmetric, or transitive are held in the relation, but what I am thinking is that this can ...
0
votes
2answers
269 views

Proving $R^n$ is antisymmetric when R is antisymmetric

Needing to solve this problem in a past paper. Not even sure where to start. Let $R$ be a binary relation on some set S. Prove or disprove the following claim. "If $R$ is antisymmetric then $R^n$ is ...
1
vote
0answers
31 views

Relation which is only locally a function

Is there a term for a relation which is not a function (because it maps multiple inputs to the same output), but which looks like one locally? That is, for any $\langle x,y\rangle\in R$, there's some ...
-1
votes
2answers
119 views

What is a relationship between sets and Factorials of Non-Natural number?

We know that factorial of natural number n describes how many bijections there are from some set with k cardinality into itself. But what if cardinality of the set is non natural number? or what if ...
2
votes
2answers
262 views

Smallest Congruence Relation generated by a set

$\newcommand{\cl}{\operatorname{cl}}$ Let $R \subset S \times S$ be a binary relation, the smallest i) reflexive relation containing it is $$ \cl_\mathrm{ref} = R \cup \{ (x,x) : x \in S \} $$ ii) ...
2
votes
2answers
122 views

Ted Sider's Definition of a Total Relation over a Set D

I'm working through Ted Sider's book "Logic for Philosophy," and I'm noticing some discrepancies between the definition of a "Total Relation" that he uses and the definition used in other places, ...
1
vote
3answers
80 views

Examples of relations: reflexive but not transtive; transtitive but not symmetric; symmetric but not reflexive [closed]

Find example of a set $ S $ and three relations $R_1, R_2 ,R_3$ on it such that $R_1$ is reflexive but not transitive, $R_2$ is transitive but not symmetric and $R_3$ is symmetric but not ...
1
vote
1answer
33 views

Relation between two gamma functions

Does anyone know the relation between these two gamma functions? 1st) Gamma[1 + c, a (1 + b)] 2nd) Gamma[c, a (1 + b)] The question is: may I write the 1st like the 2nd times something? thank you ...
1
vote
2answers
164 views

Partially ordered set Question : $A=\{1,2,3,4,5,6\}$ ,$R =\mathcal P(A) \times \mathcal P(A) $

I`m trying to prove that this relation is partially ordered set: $A=\{1,2,3,4,5,6\}$ $R =\mathcal P(A) \times \mathcal P(A) $ $(B,C)R(D,E) \Longleftrightarrow (B \subset D) \vee ((B=D)\wedge(C ...
1
vote
3answers
85 views

What do $R$, $R^2$ and $R^{-1}$ represent?

Question What do $R$, $R^2$ and $R^{-1}$ represent when $R$ is a relation on the set of natural numbers? I'm doing some homework, but the $R^2$ and $R^{-1}$ notation confuses me. Does $R^2 = R*R$? ...
1
vote
1answer
220 views

Transitive closure of these relations on $\{1,2,3,4\}$?

Problem How can I show transitive closure of these relations on $\{1,2,3,4\}$? $\{(1,2), (2,1), (2,3), (3,4), (4,1)\}$ $\{(2,1), (2,3), (3,1), (3,4), (4,1), (4,3)\}$ $\{(1,2), (1,3), (1,4), (2,3), ...
1
vote
2answers
207 views

Need assistance determining whether these relations are transitive or antisymmetric (or both?)

Problem I have these two relations over $A$, and I am supposed to determine whether they are reflexive, symmetric, antisymmetric, and/or transitive. I have determined that they are not reflexive or ...
0
votes
1answer
770 views

Totally ordered sets. Give a real life example of a total order relation on the set of all existing images on the internet

Provided that we have some information on all the existing images on the Internet, I'm asked to define a total order relation on the set by proving that it's reflexive, anti-symmetric and transitive. ...
0
votes
2answers
175 views

What is this problema asking for? I don't understand the question. (set notation, composite relations)

In the following problem, what does the "circle" between set names represent? What exactly is this problem asking me to do? Consider the following relations on Z: $R1 = \{(x, y) | y = x + 1\}$ ...
0
votes
1answer
21 views

Question about graphs and relations

If I have a directed graph $G = (V,E)$, let the relation $R$= {$(a,b)$ | $a$ has a directed path to $b$} be a relation over $V$. How can I prove that $R$ is an equivalence relation, partial order, ...
3
votes
3answers
337 views

New kind of identities?

I found a new kind of identities which are half logic and half algebraic while working on a proof of NP-completeness. They are like this: $$ \frac{a+mb}{n+m} < \frac{a}{n} \iff b < ...
9
votes
2answers
148 views

Question from 'How to Prove It'

Below is the question from the book mentioned above: Suppose $f : A \rightarrow B$ and $R$ is an equivalence relation on $A$. We will say that $f$ is compatible with $R$ if $∀x \in A\forall y ∈ ...
4
votes
3answers
98 views

Topological equivalence relations

Consider $(T, \tau)$ a topological space. Now consider $\sim_1,\sim_2$ equivalence relations on T. Let's call $\sim_3= (\sim_1 \vee \sim_2$) Is it always true that that topological quotient ...
0
votes
1answer
563 views

Proving that a pair of equivalence classes must be identical or disjoint

Give an equivalence $R$ relation over a set $A$: $$C_x=\{y\in{A}:xRy\}$$ I'm trying to prove that if $x,y\in{A}$, Either $C_x=C_y$ or $C_x\cap{C_y}=\{\}$. In other words, $C_x$ and $C_y$ must be ...
2
votes
1answer
197 views

Transitive closure of a reflexive antisymmetric relation

Prove that the transitive closure $S$ of a reflexive antisymmetric relation $R$ is a partial order.
7
votes
3answers
283 views

Unambiguous terminology for domains, ranges, sources and targets.

Given a correspondence $f : X \rightarrow Y$ (which may or may not be a function) I generally use the following terminology. $X$ is the source of $f$ $Y$ is the target $\{x \in X \mid \exists y \in ...
0
votes
2answers
84 views

Let $\sim $ be equivalence relation on $\mathbb N$ so there 4 different integers

Let $\sim $ be equivalence relation on $\mathbb N$ so there are $4$ different integers: $i,j,k,m$ that for all $n\in \mathbb N$ there's $t\in \{i,j,k,m\}$ such that $n \sim t$ then: A. $1\leq \left | ...
1
vote
2answers
100 views

reflexive and antisymetric relation

Let $A = \{1,2,3,4,\ldots ,n\}$ A). How many relations on $A$ are both reflexive and antisymmetric and contain the ordered pair $(1,2)$ ? Ans. for this I believe it is either $3^{(n^2-n-1)/2}$ or ...
1
vote
1answer
172 views

Confusion regarding transversal for a partition in Smith Introductory Mathematics: Algebra and Analysis

In Smith's Introductory Mathematics: Algebra and Analysis, I came across the definition of a transversal for a partition along with examples. Either I don't understand one of the examples, or it is ...
0
votes
1answer
358 views

Show that a relation is a partial ordering

Show that the relation $R$ on $\Bbb N$ given by $aRb \text{ iff } b = a2^k$ for some integer $k\ge 0$ is a partial ordering.
1
vote
3answers
46 views

Ordering Relation

Prove the following theorem: Suppose $A$ is a set, $F \subseteq P (A)$, and $F \neq \varnothing.\;$ Then the least upper bound of $F$ (in the subset partial order) is $\bigcup F.$
1
vote
1answer
97 views

Question on 1-1 & onto function

While I was studying relations & functions I came across with this question which I can't figure out the meaning of it. Please help. Let $X$ be the set of all strings of finite length consisting ...
0
votes
1answer
89 views

Relation $R$: $R\circ R \subseteq R \implies R$ is transitive

Let $R$ be a relation on $X$, a set. If $R\circ R\subseteq R$, then is $R$ transitive?
5
votes
0answers
85 views

Is there a standard name for the relation $X \times Y$?

Given sets $X$ and $Y$, is there a standard name for the relation $f : X \rightarrow Y$ whose graph equals $X \times Y$? Something like the full/maximum/top/total/complete relation?
0
votes
1answer
257 views

Related rates, where do I start?

A revolving searchlight, which is $100$ m from the nearest point on a straight highway, casts a horizontal beam along a highway. The beam leaves the spotlight at an angle of $\frac{π}{16}$ rad and ...
1
vote
1answer
30 views

Problem understanding domain of circular relation

I came across an exercise in a book which introduces the circular relation as: $C$ is a relation from $R \to R$ such that $(x,y) \in C$ means $x^2+y^2 = 1$. It then says that the domain of $C$ ...
-2
votes
2answers
50 views

Statements regarding relations in R

Suppose $\rho$ is a relation on $R$. I want to verify whether the following statements are true. Looks simple but proving them seems to be difficult for me. $\rho\circ\rho$ is a subset of $\rho$ ...
1
vote
1answer
51 views

About functions and relations

A pure threoretical question here. I have the relation $\pm\sqrt x$. As far as I understand it, that is not a function, as 1 input can map to 2 outputs. If I have a relation, which is not a function, ...
1
vote
1answer
95 views

Can someone help me finish this relations problem?

I have tried to work with this but this is all I have so far Are the following relations (integer sets) Reflexive, Symmetric, Asymmetric, or Transitive? $$R_1= \{(a, b) \mid a*b<1\}$$ Solution: ...
2
votes
1answer
80 views

Extension theorem on acyclic relations

By Sziplrajn's Theorem, we know that every partial order $\succsim$ (i.e. reflexive, transitive and antisymmetric relation) on a nonempty set $X$ can be extended to a linear order (i.e. a complete ...
0
votes
1answer
522 views

Matrix of a relation on a set

If I have a Matrix $A=\begin{bmatrix} 0&0&0\\ 0 & 0 & 0 \\0&0&0\end{bmatrix}$ why is this both symmetric and anti-symmetric? If I had a Matrix $B=\begin{bmatrix} ...
2
votes
1answer
997 views

Relation Matrix

Is my set of related pairs correct for this problem? $$\{(2,1), (2,2), (3,1), (3,2), (3,3), (4,1), (4,2), (4,3), (4,4)\}$$ Suppose that $\,A = \{1,2,3,4\}\,$ and $\,B = \{1, 2, 3\}.$ Let ...
2
votes
2answers
486 views

Set Relations Question

I understand these laws when applied to certain situations but can't seem to understand how to apply it to these problems. I know that if Jon is Mike's cousin, then Mike is Jon's cousin and that is a ...
2
votes
1answer
196 views

A problem on equivalent metrics and equivalence classes

Let $ X $ be a non empty set and $ \tau= \{d\mid d$ is a metric on $X\}$ Define the relation $\sim $ on $\tau$ by $ d \sim d' $ iff $ d $ and $ d'$ are equivalent metrics on $X$. Show that $\sim $ ...
1
vote
1answer
34 views

Set Relations Quick Question

Can someone please explain how this answer was reached? I know that relation of A is just A * A but wouldn't that just be $4^{2}? $ Let A = {1, 2, 3, 4}. How many relations are there on a set A? ...