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

5
votes
1answer
54 views

Why is this binary-relation antisymmetric?

Definition of antisymmetric binary-relation is $$\forall a,b\in\mathrm{A},\left[ \left(aRb\wedge bRa\right)\rightarrow\left(a=b\right)\right].$$ Let $\mathrm{A}=\left\{a\mid ...
0
votes
1answer
72 views

Maximal and minimal elements of the partial order relation

Let $A=\{1,2,3,4\}$ and $H$ is the set of antisymmetric relations on $A$. I think that $H = \{(1,2),(2,3),(3,4),(1,3),(1,4),(2,4)\}$. How would I find the minimum/maximum and min/max elements?
0
votes
1answer
113 views

Give proofs by induction for the following relation properties.

Let $R$ and $S$ be relations such that $R\subseteq S$. Prove that $R^n$ is a subset of $S^n$ for all positive integers $n$. Let $R$ be a symmetric relation. Prove that $R^n$ is symmetric for all ...
0
votes
1answer
39 views

Let $R$ be the relation on $\mathbb Z^+ \times \mathbb Z^+$ such that $(a, b)R(c, d)$ if $gcd(a, b) = gcd(c, d)$?

I need to find out: Prove that $R$ is an equivalence relation. (I am not clear on definition of an equivalence relation) What is the equivalence class of $(1,2)$? Give an interpretation of the ...
0
votes
1answer
81 views

What are some concrete examples of kinds of relations in math?

I'm writing an undergrad philosophy paper. My take on the issue is that the conceptual problem I'm addressing is only a problem because the word 'is' and 'relation' are too slippery. By more precisely ...
1
vote
2answers
58 views

Finding Powers of Relations

I have been trying to work on this question and this up to were I was able to go, but I am stuck and I do not know if I am going the right way.
3
votes
1answer
60 views

How do you find the power set within a power set?

I'm trying to find P(P(A)), where A = {0, 1, 2, 4, 7, 9}. Any ideas?
0
votes
0answers
34 views

How does Dilworth’s Theorem apply to the set {0, 2, 6, 7}?

I'm having some serious problems with Dilworth's Theorem. My question is 'how does Dilworth’s Theorem apply to the set {0, 2, 6, 7}?'. Any help is appreciated.
1
vote
4answers
122 views

is the empty set a relation?

Is the empty set is a relation? I wonder if the empty set is a relation.in enderton's a relation is a set of ordered pairs. If yes it's a relation why is that?. There is an example in the text for a ...
-4
votes
2answers
44 views

Equivalence Relations with infinite range [closed]

Find the equivalence class for $[0.5] , [0.8] , [\sqrt 3] , [1.8]$ in range of $(-\infty,\infty)$, with $R =\{ (x , y) : (y - x) \in \Bbb Z \}$
-1
votes
1answer
33 views

Relations on a set.

State the smallest relation containing the relation $$\{(1,2),(2,1),(2,3),(3,4),(4,1)\}$$ that is: a) reflexive and transitive. b) reflexive, symmetric and transitive. For me reflexive would be ...
1
vote
1answer
52 views

State whether or not the relation on the set of reals is reflexive, symmetric, antisymmetric or transitive

State whether or not the relation on the set of real numbers is reflexive, symmetric, anti-symmetric or transitive. $$R= \{(x,y)\mid x=1\text{ or }y=1\}$$ This is what I have done up to now, not ...
1
vote
2answers
74 views

Notation of a function that maps a random element

Let there be a functions $f$ and $g$ such that, $$f:A \times B \mapsto \Re$$ $$g: B \mapsto A$$ where $\forall b \in B$, $g(b)$ is some $a$ such that, $\forall a' \in A, f(a,b) \geq f(a',b)$. (This ...
2
votes
2answers
49 views

Is statistical dependence transitive?

Take any three random variables $X_1$, $X_2$, and $X_3$. Is it possible for $X_1$ and $X_2$ to be dependent, $X_2$ and $X_3$ to be dependent, but $X_1$ and $X_3$ to be independent? Is it possible ...
1
vote
3answers
104 views

Show that there is exactly one maximal element in a poset with a greatest element?

This is true, any idea how to say it in proof form? I would guess: In a poset with one maximal element, then that element has no other elements above it and has elements below it. If its the only ...
0
votes
2answers
110 views

Why are these relations not posets?

I was hoping you guys could help me clarify why these relations are or arent posets. I gave my thought process that resulted in the wrong answer. ...
0
votes
1answer
158 views

Symmetric and Transitive closures

Given a relation $R$, is the symmetric closure of the transitive closure of $R$ equal to the transitive closure of the symmetric closure of $R$? If yes, prove it. If not, give a counterexample. ...
4
votes
0answers
46 views

Metric-like families of relations

Let $X$ be an arbitrary set and to start with, let us consider a relation $\leq$ on $X$ (that is $\leq$ is a subset of $X^2$) which is reflexive and transitive. such a relation is called a preorder. ...
0
votes
1answer
54 views

Variable weight according to distance.

So I have a range of numbers for this example I would say something like 0 to 25. Within this range if I get a number lets say 11, then for each number that between my goal I it weighs more depending ...
0
votes
4answers
117 views

How to find $f(2013)$ if $f(5)=45$ and $f(m)+f(n)= f(m+n)$ for all $m,n\in\mathbb N$?

$f: \mathbb N\to\mathbb N$, $f(m)+f(n)=f(m+n)$ for all $m,n\in\mathbb N$, and $f(5)=45$. Find $f(2013)$. I messed up my original posting, its fixed now. I changed $m+ n$ to $f(m+n)$.
3
votes
1answer
444 views

How many transitive relations on a set of $n$ elements?

If a set has $n$ elements, how many transitive relations are there on it? For example if set $A$ has $2$ elements then how many transitive relations. I know the total number of relations is $16$ but ...
0
votes
1answer
39 views

Why is this binary-relation symmetric?

From the example of binary-symmetric-relation demonstrated in Wikipedia, how can they say the relation "$x$ and $y$ are odd numbers" is symmetric without stating any set of $x$, $y$? If such set is ...
0
votes
1answer
62 views

Reflexive or Irreflexive

Are the following relations reflexive or irreflexive $R = \{ (x,y) : y = 2x\}$ $R = \{ (x,y) : x \text{ is a sibling of }y\}$ $R = \{ (x,y) : x = 3 + y\}$ I believe 1 is reflexive but I'm not sure ...
0
votes
3answers
57 views

Is binary-relation $\left\{\left(a,b\right)\mid a,b\in\mathbb{N}\wedge a,b \text{ are even numbers}\right\}$ reflexive?

I'm a novice in set theory and I'm not clear about reflexive relation. My question is the title. Is binary-relation $R:=\left\{\left(a,b\right)\mid a,b\in\mathbb{N}\wedge a,b \text{ are even ...
1
vote
2answers
27 views

Why $R=\{(a,b)\mid a=b \mbox{ or } a=-b\}$ is not anti symmetric?

Why $R=\{(a,b)\mid a=b \mbox{ or } a=-b\}$ is not anti symmetric? I read because this is symmetric so it is not anti symmetric, but $R=\{(a,b) \mid a=b \}$ is both symmetric and anti symmetric.
1
vote
1answer
44 views

Are there any relations R of size 15 on the set {1, 2, 3, 4, 5, 6} such that R is both transitive and symmetric?

Are there any relations R of size 15 on the set {1, 2, 3, 4, 5, 6} such that R is both transitive and symmetric? Hi, I'm gonna share my thoughts on this problem and my answer and hopefully someone ...
0
votes
1answer
217 views

Relation squared of $xRy$ iff $x-y=c$

Let $R$ be the relation on $\Bbb{Z}$ such that $xRy$ if and only if $x-y=c$. (a) Define $R^2$. Can anyone help me with $R^2$? I am not sure where to start. From similar questions, I saw that it ...
1
vote
1answer
249 views

Finding the smallest relation that is reflexive, transitive, and symmetric

Find the smallest relation containing the relation $\{ (1,2),(2,1),(2,3),(3,4),(4,1) \}$ that is: Reflexive and transitive Reflexive, symmetric and transitive Well my first attempt: Reflexive: ...
0
votes
1answer
50 views

Binary relations, closures and equivalences

Let $R$ be the relation on $Z$ such that $xRy \iff x-y=c$. Well, what I have so far is $R=\{ 0,-1,1,0,-1,1,0 \cdots\}$ Is $R^* $ and equivalence relation? Why not? This is where problems start: I ...
2
votes
2answers
31 views

Give an example of relation $R$ and $S$ on $A$ such that $R$ and $S$ are nonempty, and $R \circ S$ and $S \circ R$ are empty

Let $A = \left \{a, b, c, d\right \}$, give an example of relation $R$ and $S$ on $A$ such that $R$ and $S$ are nonempty, and $R \circ S$ and $S \circ R$ are empty I'm thinking of ways that a set ...
2
votes
1answer
29 views

Generated equivalence relations in logics

Let $L$ be some logic (FO or stronger which is not important for this purpose). Given a $\tau$-structure $A$ and a formula $\varphi(x_1, \dots x_n) \in L[\tau]$ with free variables $x_1, \dots, x_n$. ...
0
votes
1answer
19 views

How many inverse relations

How many inverse relations are there for an n-element set? I know that $R \circ R^{-1}=R^{-1} \circ R$ where $R$ is an invertible relation, but that's as far as I can get.
0
votes
3answers
68 views

Let $A$ be a set with $n$ elements

How many reflexive relations are there on $A$? How many symmetric, reflexive relations are there on $A$? How many equivalence relations are there on $A$, if $n=5$? How are you supposed to find how ...
0
votes
1answer
60 views

Show that there are no squares included in the sequences

Show that there are no squares included in in the sequences (11, 111, 1111, 11111, ....) (22, 222, 2222, 22222, ....) (33, 333, 3333, 33333, ....) and so on and so forth for all numbers $1 ...
1
vote
4answers
36 views

Stuck on equivalence relation question

I have been stuck on this question for a while. I was wondering for a set $A={1,2,3,4,5,6}$, given that its distinct equivalence classes are $\{1,4,5\},\{2,6\},\{3\}$, what is the equivalence relation ...
1
vote
2answers
36 views

Did I do this assignment right? Antisymmetric relation.

I need to prove or disprove, that R is antisymmetric. This is my set: $$ R=\{(1,1),(1,2), (1,4), (2,1), (2,2), (3,2), (3,3), (4,4)\} $$ I proved that it is not antisymmetric in the following manner: ...
0
votes
1answer
87 views

How to tell if relation on set is a partial order when relation is defined as a set of ordered pairs?

Determine whether $R$ is a partial order on set the $S$ and justify your answer. $S=\{1,2,3\}$ and $R=\{(1,1),(2,3),(1,3)\}$. So the job is to consider if $R$ is reflexive, antisymmetric and ...
2
votes
1answer
274 views

Is a set closed under finite intersections? (about filters)

In my research I was faced with the problem (as a special example and a pattern for more general problems) whether the family $\operatorname{GR} ( \Delta \times^{\mathsf{FCD}} \Delta)$ of sets is ...
1
vote
2answers
16 views

Transitive relations and Subsets

I have a question to prove: If relations R is transitive, than R^2 is transitive. In the answer the professor says that if R is transitive than: R^2 is a subset of R (I understand why, this is the ...
1
vote
3answers
37 views

why is this relation reflexive?

S is this set of all graduates from a university. xRy means that student x first attended the university at the same year student y did. The answer key says R is reflexive but isn't it possible that ...
0
votes
1answer
22 views

Congruence Inconsistency

I have a question about congruency... I understand that: $$ 12 \equiv 7 \bmod 5 $$ $$ \text {is equivalent to:} $$ $$ 5|12-7 $$ but this doesn't seem to hold for: $$ 2 \equiv 8 \bmod 6 $$ $$ \text ...
0
votes
2answers
104 views

An example of a total order (that is NOT a well-order) of the Natural numbers

I need an example of a total ordering of the Natural numbers, that is not a well-ordering. So the classic "less than or equal to" doesn't work in this case since it is well-ordered. I've been ...
2
votes
2answers
67 views

For relations to be reflexive, symmetric and transitive is the property true for just the single subset A or AxA?

I was going over my notes on what it means for relations to be reflexive, symmetric and transitive and I'm unclear on one thing: is it for every x in a set A or set AxA? So my understanding of the ...
1
vote
1answer
53 views

I need help with a transitive closure question

the question deals with relations $R$ is a binary relation defined on $A = \{0,1,2,3\}$. Let $R = \{(0,1), (0,2), (1,1), (1,3), (2,2), (3,0)\}$. Find $R^t$, the transitive closure of $R$. I have ...
2
votes
0answers
109 views

Suppose $R$ is a relation on $A$ and $R^{-1}$ is the inverse. Proof or counterexample

Suppose $R$ is a relation on $A$ and $R^{-1}$ is the inverse. Give a proof or counterexample for each of the following statements. (a) If $R$ is reflexive, then $R^{-1}$ is reflexive. Let $x \in A$; ...
0
votes
2answers
43 views

Describing relations

(a). Describe all relations $R$ on $A$ which are simultaneously symmetric and antisymmetric. (b). Describe all relations $R$ on $A$ which are reflexive, symmetric, and antisymmetric. I have no ...
1
vote
2answers
60 views

List the symmetric relations on the set {0,1}.

I think the answer should be this, but not sure. Can anyone help me? { }, {(0,0)}, {(0,1)}, {(1,0)}, {(1,1)}, {(0,0), (0,1)}, {(0,0), (1,0)}, {(0,1), (1,0)}, ...
0
votes
2answers
64 views

Model and countermodel to $\exists x.\forall y. x<y$ (with $<$ an arbitrary relation)

Can someone please help me with this question. I have been struggling with it for ages and can't quite seem to work it out: Let $<$ be a binary relation symbol that we will write infix. Let ...
0
votes
0answers
21 views

Prove that $R^*=R^+ \cup Id_A$

Let R be a relation on set A. Prove $R^*=R^+ \cup Id_A$, where $R^*$ is the reflexive transitive closure and $R^+$ is the transitive closure. In order to prove equality of the two sets you prove that ...
0
votes
1answer
44 views

Kleene Star operation on sets

I have the following question, and do not understand the Kleene star operation in the context of relations. Let R be the relation $R=\{(0,1),(0,2),(1,4),(1,5),(2,3),(2,4),(2,5)\}^*$ on the set ...