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
2answers
146 views

Proving well ordering is total relation

Assuming R is well-ordered relation on a set A. Wikipedia claims that every well ordered relation is also a total one.Even tough in first sight it seems trivial, how can I prove it?
1
vote
2answers
1k views

Reflexive but not Transitive relation

What is an example of a relation $\mathscr{R}$ on a set $S$ such that $\mathscr{R}$ is reflexive but not transitive? Here is what I have come up with. Let $S = \mathbb{Z}$. Then let $\mathscr{R} = ...
1
vote
1answer
632 views

Transitivity of Relations and Eulerian Cycles

Question: Let $R$ be the relation $\{(1,1),(2,3),(2,2),(3,2),(3,3)\}$ on the set $S=\{1,2,3\}$. Is $R$ an equivalence relation? If $R$ is, describe the partition $\mathscr{P}$ determined by $R$ by ...
2
votes
1answer
116 views

Deriving the Axiom of Infinity

I'm currently reading about recursion, working on various exercises since I haven't formally studied the material before. The main book that I'm following is Kunen's Set Theory book There's an ...
0
votes
4answers
104 views

bijection in $\mathcal P \left({S}\right)$ and $\mathcal P \left({S}\right) \times \mathcal P \left({S}\right)$

given that ${S}$ is countably infinite set. is there any bijection exist between $\mathcal P \left({S}\right)$ and $\mathcal P \left({S}\right) \times \mathcal P \left({S}\right)$. Here $\mathcal ...
0
votes
1answer
71 views

Bijection between $\mathbb{R} \times \mathbb{R}$ and $\mathbb{R}$

How can we define bijection in between $\mathbb{R} \times \mathbb{R}$ and $\mathbb{R}$? Even giving a injection from $\mathbb{R} \times \mathbb{R}$ to $\mathbb{R}$ and vice-versa will work.
1
vote
2answers
171 views

smallest element in Partial ordered set

Every finite partial order has a smallest element, where an element x $\epsilon$ S is said to be the smallest if for all y $\epsilon$ S; it is the case that (x,y)$\epsilon$R. here R is relation ...
1
vote
1answer
137 views

Reflexive, symmetric, transitive tests - did I do it right?

Z = { ..., -2, -1, 0, 1, 2, ... } Relation ~ is defined such that a~b <=> a evenly divides b. I said that this function IS reflexive because a evenly divides a. I said that this function is NOT ...
3
votes
1answer
145 views

$\beta$ as the relation “is a brother of”

So I have a question about relations. In particular, here is the formal question: Let $\beta$ be the relation "is a brother of" and let $\sigma$ be the relation "is a sister of". Describe ...
0
votes
2answers
229 views

Prove the set relation without using Venn diagrams

Prove the set relation without using Venn diagrams: $$(A \cup B) \cap (B \cup C) \cap (C \cup A) = (A \cap B) \cup (A \cap C) \cup (B \cap C) $$ I have proven that the RHS leads to LHS, but not the ...
3
votes
2answers
94 views

Finitely many minimal elements

I've been working on various exercises to get a better understanding of some topics for an upcoming course. I have a relation $R$ on $\mathbb{N} \times \mathbb{N}$ defined as follows: $(x_0, x_1) R ...
3
votes
1answer
62 views

Relation as the Union of 4 Relations

I'm trying to write the relation $$\rho=\{\langle{x},y\rangle\in{\mathbb{R}\times\mathbb{R}}: |x|+2|y|=1\}$$ as the union of 4 relations. Is it enough to just think of this as a diamond and use the ...
3
votes
2answers
79 views

Proving that if $\bar{R}$ transitive (where $R$ equivalence relation), $|A/R|=1$

Let $A\neq\emptyset$ a set and $R\subseteq A\times A$ equivalence relation s.t the complementary relation $\bar{R}=(A\times A)\setminus R$ is transitive. Prove that $|A/R|=1$ (cardinality of ...
3
votes
1answer
133 views

About binary relations under certain conditions and their composition

(I have edited it. The previous version was with errors.) Let $A$ be a set. Let $\pi_0$, $\pi_1$ be projections from $A\times A$. Let $F_0$, $F_1$, $G_0$, $G_1$ be binary relations on $A$. Let ...
-1
votes
2answers
81 views

Abstract Algebra topic: Equivalence relations [duplicate]

If R1 is reflective and not transitive, R2 is transitive but not symmetric and R3 is symmetric but not reflexive. We need to find an example of a set S and the three relations R1 R2 R3.
5
votes
2answers
507 views

Ordering the field of real rational functions

Perusing the Wikipedia article on ordered fields, I encountered an interesting statement, a variation of which I am now trying to prove. Basically, I am trying to show that the set of real rational ...
1
vote
1answer
76 views

Question about suprema/infima of partially ordered subsets

This is another clarifying question; alas, I find myself confused once again by a seemingly innocuous statement in my lecture notes. Let $S$ be a subset of a partially ordered set $(T, \preceq)$, and ...
3
votes
0answers
45 views

A relation on 2 countable sets [duplicate]

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 ...
0
votes
1answer
84 views

Down-set closure of subsets

I am confused by the following statement in my lecture notes on down-set closure of subsets: "The family of down-sets containing a given subset $E \subseteq S$ is nonempty since $E \subseteq S$ and ...
3
votes
2answers
52 views

Question about the definition of the upper set

As I understand it, a subset $L$ of a partially ordered set ($S, \preceq$) is called a down-set or lower set if for any $s \in L$ and $s' \preceq s$, we have $s' \in L$. Now, my question is can we ...
1
vote
1answer
167 views

relations - examples and counterexamples

The question is to find an example of a set $S$ and three relations $R_1$, $R_2$, and $R_3$ on it, such that $R_1$ is reflexive but not transitive, $R_2$ is transitive but not symmetric and $R_3$ is ...
2
votes
1answer
60 views

Set Theory Relations

Given set $A={1, 2, 3}$ consider the following relation on $A$ $R=\{(1, 1), (2, 1), (3, 3), (3, 2)\}$ Which one of the following statements are true $R$ is antisymmetric and transitive $R$ is ...
1
vote
2answers
323 views

The bijective property on relations vs. on functions

I recently encountered what seems to me like an inconsistency in the usage of the term bijective. This is pretty basic stuff, but it somehow never occurred to me before. I'd like to make sure I'm ...
4
votes
1answer
113 views

Prove that $D_r \circ D_s = \{ (x,y) \in \mathbb{R}^2 \ | \ |x-y|<r+s \}$, where $D_a = \{ (x,y) \in \mathbb{R}^2\ | \ |x-y| < a \}$

Suppose $r$ and $s$ are two positive real numbers. Let $D_r = \{ (x,y) \in \mathbb{R}^2\ | \ |x-y| < r \}$ and $D_s = \{ (x,y) \in \mathbb{R}^2 \ | \ |x-y| < s \}$. Prove that $D_r \circ D_s = ...
1
vote
1answer
36 views

On equality of quotient relations

I am a non-mathematician who is taking a self-learning course in mathematics. I am studying a chapter on (equivalence)relations and I have the following question: Suppose $R$ and $S$ are ...
7
votes
2answers
529 views

Notation for a relation

I'm reading up on "Set Theory and Logic" by Stoll and came upon notation for relations that I haven't seen before. I've seen $x\sim{y},$ and $xRy$ before but Stoll uses this one. $$(x,y)\in{\rho}$$ ...
2
votes
1answer
106 views

Some (in)equalities about binary relations

Let $\Phi\subseteq (A\times A)\times(A\times A)$, $F_0,F_1\subseteq A\times A$ (for some set $A$) be binary relations. I will denote $\pi_0$ and $\pi_1$ the projections of a cartesian product of ...
0
votes
1answer
42 views

Number of (equivalence) relations fulfilling some additional conditions

let say I have $A=\{1,\dots,8\}$ I want to know the following things: what the number of relations on $A$? what the number of reflexivity relations on $A$? what the number of equivalence relations ...
0
votes
1answer
61 views

Question about posets and maxima/minima

A thought just occurred to me, thinking about posets and maxima/minima... This is a "little" question just to make sure I am really grasping the definitions here: if $E$ is partially ordered by a ...
1
vote
1answer
645 views

Proving the transitivity of a relation

I want to prove that the relation $\sim$ on fractions given by $\frac{a}{b} \sim \frac{c}{d}$ if $ad = cb$, where $a, c \in \mathbb Z$ and $b, d \in \mathbb Z_{> 0}$, is transitive. (My last ...
2
votes
1answer
185 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
129 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
468 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
408 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
72 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
70 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
532 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
278 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
125 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
266 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
125 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
83 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$? ...