This tag is for elementary questions on set theory, spanning topics usually found in introductory courses in set theory, in addition to review sections of graduate textbooks in the same field. Topics include intersections and unions, de Morgan's laws, Venn diagrams, relations, functions, (un)...

learn more… | top users | synonyms

4
votes
2answers
133 views

$A\subset f^{-1}(f(A))$ with equality if and only $f$ is injective.

I've got a little mistakes with that: $A\subset f^{-1}(f(A))$ with equality if and only $f$ is injective. For example, if we take $f(x)=x^2$ and $A=[-1,1]$, we have $$f(A)=f([-1,1])=\{f(x)\mid x\in[-...
-1
votes
1answer
869 views

List the elements of the set

I'm working on my math homework and I don't even know how to do this or what it is asking. Any help would be great! Let $A = \{1, 2, 3\} \times \{1, 2, 3, 4\}$. List the elements of the set $B = \{(s,...
2
votes
3answers
72 views

If $f\circ g = g \circ f$ does that mean that both functions are to and from the same set and both are bijections? Does it tell us anything else?

If $f\circ g = g \circ f$ does that mean that both functions are to and from the same set and both are bijections? Does it tell us anything else?
0
votes
2answers
82 views

To prove a given set is a $\sigma$ algebra

I need to prove the following If $R$ is a $\sigma$ ring then $\{ E \subset X : E \subset R $ or $ E^c \subset R \}$ is a $\sigma$ algebra. Here now my claim is that $E_j \in R\ \forall i = 1,2,\...
0
votes
2answers
112 views

Attempt to proof the Cantor-Bernstein theorem

I've found a proof of the Cantor-Bernstein theorem in Kleene's 'Introduction to Metamathematics' (1952) in §4 Thm A. I must admit I don't understand its essence but I was wondering if the proof could ...
0
votes
1answer
54 views

$\bigcup_{i \in I} \mathcal{P} (A_i)$

This is Velleman 3.7, Problem 4 Below is the problem, verbatim. Suppose $ \{ A_i \mid i \in I\}$ is a family of sets. Prove that if $\mathcal{P}(\bigcup_{i \in I} A_i) \subseteq \bigcup_{i \in I} \...
1
vote
0answers
8 views

How the union of a bound series of integers converges to all integers for cases of all orders.

For the series $S_n = \{-n, \cdots, n \}^d$ I would like to show the union of all such sets converge to $\mathbb{Z}^d$ as $n \rightarrow \infty$. That is to said, how can I prove: $$\bigcup_{n \geq 1}...
2
votes
2answers
21 views

Showing $R$ is transitive and reflexive $\to$ $R=R^2$, $R$ is transitive and reflexive $\to$ $R=R^2$

Let $R$ be a relation over $A$. Define $R^{-1}, R^2$ like so: $aR^{-1}b \iff bRa\\ aR^2b\iff\exists _{c\in A}(aRc\wedge cRb)$ Prove: $R$ is transitive $\iff$ $R^2\subseteq R$ $R$ ...
1
vote
1answer
36 views

Show $\alpha$ is a limit ordinal $\leftrightarrow \alpha \neq 0$ and $\cup \alpha = \alpha$

$\alpha$ is a limit ordinal $\leftrightarrow \alpha \neq 0$ and $\cup \alpha = \alpha$ Sorry if this question has been asked already but I couldn't find it on this site. I assume by definition of a ...
2
votes
1answer
42 views

Question about proving intersection of two transitive relation is transitive

Suppose $R,S$ are transitive relations over $A$, prove that $R\cap S$ is transitive. Let $x,y,z\in A$, since $R,S$ are transitive then $$(x,y),(y,z),(x,z)\in R \wedge S\Rightarrow (x,y),(y,z),(x,z)\...
0
votes
0answers
22 views

Finding maximal chains in an ordered set.

Let $R$={$((x_1,y_1),(x_2,y_2))$:$x_1\le x_2, y_1\le y_2$} find the maximal chaings. Could it be that every maximal chains is of the form {$(a,b)+t(1,1)|t\in\Bbb{R}$} such that every other chain of ...
-1
votes
1answer
25 views

Ordered sets. Chain upper bounds.

Suppose I have an ordered set $A$ and a chain $B\subseteq A$ then does $B$ necessarily have a supremum? Let alone an upper bound? And if it is empty? This question is a bit confusing because I am not ...
0
votes
1answer
51 views

Clarification on intuition behind one to one correspondence?

My book - Discrete Mathematics and its Applications This is my book's definition on if an infinite set is countable And the example it gave The "infinite set is countable if and only if it is ...
1
vote
0answers
31 views

Are maps and operators between two sets the same?

I have been reading on up on the definition of maps and operators, specifically reacting to sets (rather then the more restricted vector spaces) and their definitions seem to be identical. So are all ...
2
votes
3answers
35 views

Not a precise question on equivalence class.

Consider $f:X\longrightarrow Y$. Define a relation $\sim$ on $X$ by $a\sim b$ iff $f(a)=f(b)$. I proved that $\sim$ is an equivalence relation and that if $f$ is onto and $X/\sim$ is the set of ...
0
votes
0answers
18 views

Zorn's lemma usage\problem. [duplicate]

Let $(A,\le)$ be an ordered set. Show that if any chain has an upper bound then for any $a\in A$ there exist a maximal element such that $a\le x$. I am stuck with this... Would appreciate any help......
2
votes
1answer
33 views

Equivalence class of $(x_1,y_1)\sim(x_2,y_2)$ iff $ x_1=x_2$

I proved that $x\sim y$ iff $x-y\in \mathbb Z$ is an equivalence relation on $\mathbb R$. I'd like to know if $[x]=\{x+n:n\in\mathbb Z\}$ is an equivalence class for every $x\in \mathbb R$ (if it is ...
0
votes
2answers
41 views

Total order function property

This may have been asked before but it's difficult to search for. Suppose that $|A|=n$ and that $R$ is a total order on $A$ (not a strict order). Define $g:A \to I_n$ by $$ g(a) = |\{x \in A ~|~ xRa\}...
0
votes
1answer
24 views

Unique expression as disjoint union of indecomposable subsets

Let $f:A \to A$ be a function, we say that $B \subseteq A$ is $f$-invariant iff $f(B) \subseteq B $. We say that an invariant subset is indecomposable iff it cannot be expressed as a union of non-...
0
votes
1answer
22 views

$\{h\in A^B|h \text{ is invertible}\}$ is equiumerous to $\{k\in B^A|k \text{ is invertible}\}$ and $\aleph_0$ right invertibles for a function

1.Let $A,B$ be sets, prove: $\{h\in A^B|h \text{ is invertible}\}$ is equinumerous to $\{k\in B^A|k \text{ is invertible}\}$ 2.Let $A,B$ be sets and a function $f\in A^B$ give an example right ...
2
votes
2answers
112 views

If the empty set is a subset of every set, why isn't $\{\emptyset,\{a\}\}=\{\{a\}\}$?

If the empty set is a subset of every set, why it isn't written with the elements of a set? like so $\{1,2,3,\emptyset\}$ Or why isn't $\{\emptyset,\{a\}\}=\{\{a\}\}$? I know one has two elements ...
0
votes
1answer
41 views

If $\alpha$, $\beta$ are finite cardinals such that both are greater than $1$ and $\gamma$ is an infinite cardinal then $\alpha^\gamma=\beta^\gamma$.

Can someone suggest a rigorous proof of the following: If $\alpha$, $\beta$ are finite cardinals such that both are greater than $1$ and $\gamma$ is an infinite cardinal then $\alpha^\gamma = \beta^\...
1
vote
4answers
181 views

Would this be an acceptable answer for the inverse of floor function

This problem is from Discrete Mathematics and its Applications And the book's definition on inverse Would an acceptable answer to 43b just be the set itself again? What I like to think of the ...
2
votes
1answer
112 views

Let A1,A2,…,An be distinct subsets of a set X. Then there is subset Y with size <=n-1, s.t. all intersections are all distinct.

Let $A_1,A_2,\dotsc,A_n$ be distinct subsets of a set $X$. Then there is subset $Y$ with size $\le n-1$, s.t. all intersections of $A_i$ with $Y$ are all distinct. I am trying to prove it with ...
4
votes
1answer
126 views

Metrics on $\mathbb R^n$, Counting continuous functions and Open sets

Given the set $\mathbb{R}^n$ with metric $d$. We define continuous functions from $\mathbb{R}^n$ to $\mathbb{R}^n$ by open sets -we say that function is continuous iff the pre-image of every open set ...
0
votes
1answer
30 views

Countable cofinality and closed sets

If $\kappa$ is an infinite cardinal of countable cofinality we know that $F_1=\bigcup_{n<\omega} (\kappa_{2n},\kappa_{2n+1}]$ and $F_2=\bigcup_{n<\omega} (\kappa_{2\alpha+1},\kappa_{2\alpha}]$, ...
1
vote
1answer
104 views

Cardinality of set of all bijections $\mathbb{N}\to\mathbb{N}$; is my proof correct?

I need to find cardinality of a set containing all bijections $\mathbb{N} \to \mathbb{N}$. My proof goes like that: Let $S$ be the set containing all bijections $\mathbb{N} \to \mathbb{N}$. There ...
0
votes
1answer
36 views

$\mathcal A$ is empty, what is $\bigcap_{S\in\mathcal A}S$? [duplicate]

Given a collection $\mathcal A$ of sets and a large set $X$. What are $\bigcup_{S\in\mathcal A}S$ and $\bigcap_{S\in\mathcal A}S$ ? The problem is if $\mathcal A$ is empty, what do $\bigcup_{S\in\...
0
votes
1answer
14 views

Expressing $\{\mathbf x: x_n=x_{n+1}\text{ for every $n$ prime number}\}\subseteq R^\omega $ as cross product of subsets of $\mathbb R$

The question is: can we express such a set in terms of cross products between subsets of $\mathbb R$? We would have $\{\mathbf x=(x_1,x_4,x_4,x_4,x_6,x_6,x_8,x_8,x_9,x_{10},x_{12},x_{12},\dots)\}$. ...
2
votes
1answer
77 views

Well ordering of $\mathbb{N}$ using inductive sets

In this book (Elementary Real Analysis by Thomson-Bruckner p.22), $\mathbb{N}=\left\{ 1,2,...\right\}$ (In some, $0\in\mathbb{N}$). In an exercise, a set $S\subset\mathbb{R}$ is inductive if $1\in S$ ...
0
votes
2answers
147 views

Give an example of a set which is not transitive

Transitive set: set $x$ is transitive if $\forall y\in x(y\subseteq x)$ I think $\{\varnothing\}$ is not transitive since $\varnothing\in\{\varnothing\}$ but $\varnothing\not\subseteq\{\varnothing\}$ ...
0
votes
0answers
34 views

Proof: There cannot be a universal set / set of all sets [duplicate]

I am new to mathematics as well as to math.stackexchange so my question will be a very basic one and I might have related questions that will seem very basic if not trivial. My first question is the ...
1
vote
1answer
37 views

Difference between a criteria of well-ordered and transitive in terms of an ordinal?

From what I gather a set $x$ is $transitive$ if whenever $y \in z , z \in x \rightarrow y \in x$ And one of the properties of a well-ordered set is that $x \in y , y \in z \rightarrow x \in z$ Now ...
3
votes
2answers
54 views

slightly different definition of an ordered pair

In a paper I was reading an ordered pair had a slightly different definition $\langle a,b \rangle = \{a,\{a,b\}\}$ instead the normal Kuratowski definition which is that $\langle a,b \rangle = \{\{a\},...
-1
votes
1answer
37 views

Is the following set reflective, symmetric or transitive $R = \{(x,y) : x+ y \leq 2015 , x,y \in \mathbb{Z}\}$

is the following set reflective, symmetric or transitive $R = \{(x,y) : x+ y \leq 2015 , x,y \in \mathbb{Z}\}$ The set is transitive as $(1,2)$ is there $(2,1)$ is there and $(1,1)$ is there and so ...
0
votes
1answer
40 views

Discrete Math Elements within a set

$\{x \mid x \in\mathbb N, x \text{ is even, and } 2 < x < 11\}$ Would the elements in this set be $x$ and all positive even integers between $2$ and $10$?
1
vote
0answers
36 views

Can I apply measure theory in non-mathematics fields?

I am working in a field where researches try to get insight about a complex process. I will give an example to demonstrate this. Let's say, we are attempting to get the most efficient and cost ...
0
votes
2answers
180 views

How many elements are in the set $\{(a,b) | a,b~\text{are elements of}~\mathbb{N} \times \mathbb{N}~\text{and}~1 \leq a \leq b \leq 15\}$

How many elements are in the set $\{(a,b) | a,b~\text{are elements of}~\mathbb{N} \times \mathbb{N}~\text{and}~1 \leq a \leq b \leq 15\}$? I managed to find $4$ elements, $\{1,2,3,4\}$ The way I did ...
3
votes
2answers
155 views

Least Upper Bound Property.

I had a question about the Least Upper Bound Property. So it states that every non-empty subset of $\mathbb{R}$ that has an upper bound must have a least upper bound in the reals. My question is: ...
1
vote
1answer
41 views

Prove $X$ is uncountable if $X$ is the set of all functions $f: \mathbb{Z}_+ \rightarrow \mathbb{Z}_+$ [duplicate]

I'm not sure how to approach this. I've seen a proof how to prove that $[0,1]$ is uncountable. I thought of doing this by contradiction, and assuming that $X$ was countable, but I can't really go ...
11
votes
2answers
1k views

Why is there this strange contradiction between the language of logic and that of set theory?

In standard probability theory events are represented by sets consisting of elementary events. Consider two events for which (as sets) $A \subset B$. If an elementary event $x \in A$ takes places then ...
0
votes
1answer
168 views

Complement of the Image is the Image of the Complement

Given a continuous linear map $T:E\to F$ where $E,F$ are normed vector spaces, I am wondering about the trivial question whether for any subset $U\subset E$, it holds or not: $$T(U^c)=T(U)^c$$ I could ...
0
votes
2answers
52 views

If $f$ is an injection, $f(S_1 \cap S_2) = f(S_1) \cap f(S_2)$ [duplicate]

I need to prove that if $S_1$ and $S_2$ are subsets of a set $X$, and if $f: X \to Y$ is an injection, prove that $f(S_1 \cap S_2) = f(S_1) \cap f(S_2)$. I know I need to show inclusion in both ...
0
votes
1answer
17 views

Finding a bijective function from $\prod_{i\in I}X_i$ to $\bigl(\prod_{j\in J}X_j\bigr)\times\bigl(\prod_{k\in K}X_k\bigr)$

If $(X_i)_{i\in I}$ is a family of sets and $J,K$ are non-empty disjoint sets of $I$ such that $I=J\cup K$, then show that there is a bijective function from $\prod_{i\in I}X_i$ to $\left(\prod_{j\in ...
-2
votes
1answer
57 views

Nullary Arithmetic Product (at Wiki)

In Nullary Arithmetic Product at Wiki, we are given a sequence of numbers $a_1, a_2, a_3\ldots$ The product of the first $m$ elements of this sequence is given there by $P_m=a_m \cdot P_{m-1}$ ...
1
vote
1answer
92 views

Surjection $f$ induces surjection $\mathcal P (f)$ on power sets

Just wanted to make sure the way I approach this was correct because it seemed a bit too simple for an answer: Question: Let $\mathcal P \left({X}\right)$ represent the power set of $X$. Let $f: X \...
1
vote
2answers
96 views

Demonstrate currying via homomorphism

You can demonstrate currying for two-argument functions is possible showing there's a isomorphism between $(A^B)^C \cong A^{B \times C}$. That is, the set of functions $(C \rightarrow B) \rightarrow A$...
1
vote
2answers
113 views

confusion over Finite intersection property

It is stated that $A_n={(\frac{-1}{n},\frac{1}{n})}$, then arbitrary intersection of open sets need not be open is true as in this case $\bigcap_{i=1}^{\infty}=\left \{0 \right \}$ is not open. Now ...
3
votes
1answer
49 views

Is this a topological closure operation?

Does any relation $\propto\,\subseteq X\times \mathcal P(X)$ that extends $'\!\!\in'$ in the way that: $x\in M\Rightarrow x\propto M$ $\neg\exists x\in X:x\propto\emptyset$ $x\propto A \subseteq B ...
-2
votes
1answer
55 views

Set Theory intersection and union [closed]

I have the following problem: Let $B_n = [0, 1 + n^{−1} ),\space\space T_n = [0, 1 − n^{−1} ],\space\space n \in \mathbb{N}$. Show that $\bigcap B_n = [0, 1]$ and $\bigcup T_n = [0, 1)$ ...