# Questions tagged [relations]

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.

3,309 questions
38k views

### Are there real-life relations which are symmetric and reflexive but not transitive?

Inspired by Halmos (Naive Set Theory) . . . For each of these three possible properties [reflexivity, symmetry, and transitivity], find a relation that does not have that property but does have the ...
13k views

### Why isn't reflexivity redundant in the definition of equivalence relation?

An equivalence relation is defined by three properties: reflexivity, symmetry and transitivity. Doesn't symmetry and transitivity implies reflexivity? Consider the following argument. For any $a$ ...
3k views

1k views

### Can a relation be transitive when it is symmetric but not reflexive? [duplicate]

Pretty much what the title asks. But here's some context: Suppose $X$ is finite and $R$ is a relation on $X$ that is not reflexive but it is symmetric. Also, suppose we can rule out $xRy$ and $yRz$ ...
1k views

### How do I define exactly what a function is?

While it is easy to understand what a function is intuitively, I've been trying to wrap my head around how to precisely define what a function is using only mathematical notation. My attempt at this ...
9k views

### Can a relation with less than 3 elements be considered transitive?

The generalize rule for a transitive relation is a -> b b -> c therefor a -> c If an element has less than 3 elements, can it still be transitive? If ...
677 views

### How is the relation “the smallest element is the same” reflexive?

Let $\mathcal{X}$ be the set of all nonempty subsets of the set $\{1,2,3,...,10\}$. Define the relation $\mathcal{R}$ on $\mathcal{X}$ by: $\forall A, B \in \mathcal{X}, A \mathcal{R} B$ iff the ...
3k views

### Main Theorems/Techniques for proving Homeomorphism?

General Question: what are the most common Theorems/Methods used to prove Homeomorphism? I encountered: - find the map explicitly - use the Compact-to-Hausdorff Lemma - find cts maps $f$ and $g$ s....
880 views

### Can we extend the definition of a homomorphism to binary relations?

This is going to be quite a long post. The actual questions will be at the end of it in section "Questions." INTRODUCTION After receiving an answer to this question about extending the definition of ...
1k views

### Is every relation which is transitive and symmetric also reflexive?

I have seen a proof that every relation which is symmetric and transitive is also reflexive. if $A=\{1,2,3\}$ Then if $R=\{(1,2)(2,1)(1,1)\color{blue}{(2,2)}\}$ here $R$ is symmetric and transitive ...
34k views

27k 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 any good ...
167 views

### Counting number of mathematical objects and structures

Regarding the numbers of certain mathematical objects and structures, especially sets, relations and functions, I've compiled a list of the counts from various sources: Partitions of a set with $k$ ...
165 views

581 views

### Understanding Equivalence Classes?

I am reading about equivalence classes and I would like to make sure I understood thins properly. My book says: The set of equivalence classes under this equivalence relation [$\pmod n$] will be ...
16k views

### Whats the difference between Antisymmetric and reflexive? (Set Theory/Discrete math)

Antisymmetric: $\forall x\forall y[ ((x,y)\in R\land (y, x) \in R) \to x= y]$ reflexive: $\forall x[x∈A\to (x, x)\in R]$ What really is the difference between the two? Wouldn't all antisymmetric ...
508 views

### Counting non-isomorphic relations

On a set $X$ of $n$ elements, how many non-isomorphic relations are there? The number of relations on a set of $n$ elements is $|\mathcal{P}(X \times X)|=2^{n^2}$, but is there any way to give a ...
132 views

### Finding $f(x)$ given a function $f : \Bbb N \to \Bbb N$ which satisfies $f\circ f(x) + f(x) = 2x+15$

I'm stuck on rewriting the function $f\circ f(x) + f(x) = 2x+15$ (into $f(x) = \dots)$. The answer given is $f(x) = x + 5$, which I can easily verify, but I do not know how to go about forming this ...
713 views

### What is meant by “m|n”? Two letters separated by a vertical bar (|)

I am new to this subject, and not not sure what "|" symbol means on this statement. Let $R_2 \subset\Bbb N \times\Bbb N$ be defined by $(m, n) \in R_2$ if and only if $m|n$.
1k views

### Interesting properties of ternary relations?

Many people are familiar with some properties of binary relations, such as reflexivity, symmetry and transitivity. What are the commonly studied properties of ternary (3-ary) relations? If you ...
11k views

### Reflexive Transitive Closure

The problem I am working on is, "Show that a finite poset can be reconstructed from its covering relation. [Hint:Show that the poset is the reflexive transitive closure of its covering relation.]" I ...
285 views

### How to prove an extension of ZFC is conservative

Working in ZFC. I've defined a function-like binary predicate $R$ on a proper class. It has to be recursive; i.e. $R(a,b)$ must usually depend on one or more $R(c,d)$ for some $c$s and $d$s ...