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, ...

learn more… | top users | synonyms

1
vote
1answer
18 views

Applying set operations on subsets of $\{0, 1, 2, \ldots, 8, 9\}$

Set Operation- Let A={2,4,5,6,8} B={1,4,5,9} and c={x| E Z{positive Integer} and 2 <= x <5 } of S={0,1,2,3,4,5,6,7,8,9} compute each of the following sets: (c ∩ B)∪ ¬A my answer: C={0,1,2} ...
1
vote
1answer
62 views

True-False Problem: elementary set theory (please verify)

I'm trying to self-learn math and I'm starting with naïve set theory. The only problem is that the book I'm using lacks a solution textbook and I don't know if the solution I gave to this problem is ...
0
votes
1answer
40 views

Does $\wp(A \cap B) = \wp(A) \cap \wp(B)$ hold? How to prove it?

I'm currently working on some discrete mathematics work and I've encountered a question I'm not sure how to answer exactly. Precisely, I'm trying to prove that two power, intersected sets statements ...
0
votes
1answer
9 views

Denumerable partition of a denumerable set where each set in the partition is denumerable. [duplicate]

Suppose that a set $A$ is denumerable. Prove that there is a partition $P$ of $A$ where $P$ is denumerable and every $X \in P$ is also denumerable. I can see that this can be done but I cannot figure ...
0
votes
0answers
57 views

How to prove $f(c) = f(d) = 0$ [duplicate]

I ONLY NEED HELP WITH PROVING: $f(c) = f(d) = 0$ Robert Green's answer here : Is the first part of the answer, but I cannot problem that $f(c) = 0$ and $f(d) = 0$? How should I do this? Here was ...
1
vote
1answer
30 views

Need help with notation — finite set of random primes

I need help with notation for a finite set of random primes. Edit I've inserted my take on the format from the answer. Does it work? My attempt:$$\{X\in\binom{\mathbf P_{3,100}}{20}\},$$ ...
0
votes
1answer
23 views

How many sets of 2 without duplicates out of these options?

So there are twelve signs of the zodiac: Aries, Taurus, Gemini, Cancer, Leo, Virgo, Libra, Scorpio, Sagittarius, Capricorn, Aquarius and Pisces I want to know how many possible sets of 2 I can make ...
2
votes
1answer
41 views

Proof Verification of $B \cup A = B$ implies $Pr(A) \leq Pr(B)$

Basic Information If you're confused $Pr(A)$ stand for probability of A. My Work 1) $A\cup B = B \iff A \subseteq B$ (By Theorem 3.4 in our textbook) 2) $A \subseteq B \implies |A| \leq |B|$ ...
4
votes
2answers
39 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 ...
-1
votes
1answer
23 views

List the elements of the set

Im 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} × {1, 2, 3, 4}. List the elements of the set B = {(s, t) ∈ A | s ≥ ...
2
votes
3answers
40 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
43 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 = ...
0
votes
1answer
58 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 ...
-1
votes
1answer
44 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
6 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 ...
2
votes
2answers
16 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$ ...
1
vote
1answer
17 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 ...
1
vote
1answer
17 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 ...
0
votes
0answers
16 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
15 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
32 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
1answer
29 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
28 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
16 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 ...
1
vote
1answer
16 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
26 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 ~|~ ...
0
votes
1answer
18 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 ...
0
votes
1answer
12 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 ...
1
vote
2answers
49 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
29 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 = ...
1
vote
4answers
47 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
31 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
80 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
19 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
84 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
31 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 ...
0
votes
1answer
12 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
44 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
33 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
27 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
22 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
1answer
37 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 = ...
0
votes
1answer
26 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
26 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
33 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
36 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 ...
2
votes
2answers
64 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
27 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 ...
8
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
31 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 ...