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

1
vote
1answer
88 views

Relations that are: reflexive but not transitive; transitive but not symmetric; symmetric but not reflexive

I have an incomplete answer to my question. Can anyone help me answer the last two parts. My question is: Find example of a set $S$ and three relations $R_1$, $R_2$, $R_3$ on it such that ...
0
votes
0answers
50 views

using entropy to calculate the relatedness of two columns in a database

There are two columns(x, y) in a database, I want to define the "relatedness" of the two columns. First i try to use I(x, y) (mutual information) to define the relatedness, then: date, ...
-1
votes
1answer
45 views

Proof the following - language

Theorem $4$. A language $A$ is regular iff there exists a regular expression $\alpha$ such that $A = L(\alpha)$. Check whether the following equations are correct. $\left((a\cup ...
0
votes
2answers
98 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
855 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
630 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 ...
3
votes
1answer
111 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
102 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
68 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
157 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
124 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
100 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
180 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 ...
4
votes
2answers
90 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 ...
2
votes
2answers
72 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
74 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
419 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
68 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
80 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
39 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
134 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 ...
1
vote
1answer
54 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
209 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
105 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
33 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 ...
6
votes
2answers
331 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
105 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
41 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
58 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
507 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
164 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
126 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
54 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
409 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 ...
2
votes
2answers
89 views

How to represent objects formally? [closed]

Computer indexed arrays can be represented formally using vector notation. x= [1,3,2] $x=(1,3,2)$ How can I show an object/associative array mathematically? y=['a'=>5,'b'=>4] ~ ?
4
votes
1answer
90 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
320 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
127 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
66 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
63 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
467 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
67 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
210 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
115 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
244 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
115 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, ...