This tag is for elementary questions on set theory - the sort of material covered in "Chapter 0" of graduate texts and in undergraduate set theory texts. Topics include intersections and unions, de Morgan's laws, Venn diagrams, relations, functions, countability and uncountability, power sets, ...

learn more… | top users | synonyms

-1
votes
0answers
32 views

Is $^\mathbb{N}\mathbb{R}$ $\sim$ $^\mathbb{R}\mathbb{N}$? [duplicate]

Is $^\mathbb{N}\mathbb{R}$ $\sim$ $^\mathbb{R}\mathbb{N}$? I know you have to use Cantor-Bernstein, and prove both directions, but i don't know how to start the proof
-1
votes
1answer
39 views

How do I create an injection here? [duplicate]

I am trying to show that $|\Bbb {R} \times \Bbb {R}| \leq |\Bbb {R}|$. I don't know how to define $f:\Bbb {R} \times\Bbb {R} \rightarrow \Bbb {R}$ in a way that would make $f$ injective. My ...
-1
votes
1answer
36 views

Let F be a partition of A. Prove there exists unique equivalence relation R such that F=A|R?

Let F be a partition of A. Prove there exists unique equivalence relation R such that F=A|R? I don't even know how to start. I know to be a equivalence relation R must be reflexive, symmetric and ...
0
votes
0answers
19 views

Order on the set of partitions (terminology)

Let $S$ and $T$ be partitions of some set $U$. What is the name for the partition $\{ X\cap Y \mid X\in S, Y\in T, X\cap Y\ne\emptyset \}$? Should it be called the infimum of $S$ and $T$? meet of ...
1
vote
2answers
38 views

If there is a mapping of $B$ onto $A$, then $2^{|A|} \leq 2^{|B|}$

If there is a mapping of $B$ onto $A$, then $2^{|A|} \leq 2^{|B|}$. [Hint: Given $g$ mapping $B$ onto $A$, let $f(X)=g^{-1}(X)$ for all $X \subseteq A$] I follow the hint and obtain the function $f$. ...
1
vote
2answers
97 views

Equality in set theory

In Introduction to Axiomatic Set Theory by G. Takeuti and W. M. Zaring chapter 3 It is given: Definition of equality as: $a=b \Leftrightarrow (\forall x)[x \in a \Leftrightarrow x \in b]$. And it ...
0
votes
1answer
23 views

Cardinality of sets regarding

Consider the following sets of functions on $\mathbb{R}$. $W=$The set of all constant functions on $\mathbb{R}$ $X=$The set of polynomial functions on $\mathbb{R}$ $Y=$ The set of continuous ...
-1
votes
3answers
44 views

Cardinality of the power set

Show that the cardinality of the power set of a finite non-empty $N$ set is a multiple of $2$. Then, show that it is exactly expressed by $2^n$, where $n$ is the cardinality of $N$ and that this ...
0
votes
0answers
19 views

Transfinite recursion and sequence function of type W into X

Transfinite Recursion Theorem: If W is well ordered set and f is sequence function of type W in a set X, then there exist unique function U from W into X such that U(a) = f(U'a') for each a in W. A ...
1
vote
1answer
15 views

Order type relation in poset and well ordered sets

I just read the definition: Two partial ordered sets X and Y are said to be similar iff there a bijective function from X to Y such that for f(x) < f(y) to occur a necessary and sufficient ...
0
votes
2answers
39 views

(Different Approach) [EDITED: Please Review] An at most countable union of at most countable sets is at most countable

Question Re-phrased: I'm having a lot of trouble wrapping my head around this problem. While I've looked through similar posts, It's difficult understanding the maths because I currently have ...
0
votes
1answer
23 views

Cardinal numbers of Setminus

Could you help me check the following fact ? Let A,B,C be sets such that C⊆A and C⊆B. Then |A∖C|=|A|−|C| |A∖C|=|B∖C| if and only if |A|=|B| where |A| is the cardinal number of A and A∖C is ...
1
vote
1answer
51 views

How to prove this? “For all sets A,B⊆D and functions f:D→R, we have f(A∩B)⊆(f(A)∩f(B)).” [duplicate]

Here's my attempt: f(A∩B) = f({x|x∈A∧x∈B}) = {f(x)|x∈{x|x∈A∧x∈B}} f(A)∩f(B) = f({x|x∈A}) ∩ f({x|x∈B}) = {f(x)|x∈{x|x∈A}} ∩ {f(x)|x∈{x|x∈B}} = {x|x∈{f(x)|x∈{x|x∈A}}∧x∈{f(x)|x∈{x|x∈B}}} And now I'm ...
1
vote
1answer
35 views

A collection of pairwise disjoint open intervals must be countable

Let $U$ be a collection of pairwise disjoint open intervals. That is, members of $U$ are open intervals in $\mathbb{R}$ and any two distinct members of $U$ are disjoint. Show that $U$ is countable. ...
0
votes
1answer
24 views

Set Theory and finite unions

Let $A$ be the collection of finite unions of sets of the form $(a,b]\cap Q$ where $-\infty\leq a<b\leq \infty$. Does $\phi\in A$?
0
votes
0answers
25 views

Using the negation of a statement to disprove original statement

Prove the following statement is false by first writing the negation, then proving the negation is true: For all sets, S, if S ⊆ ℕ, then there exists some t ∈ S such that |t| ≥ 1. So far, I've ...
2
votes
2answers
64 views

What does the notation $\bigcup_{n\in\mathbb N} A_n$ mean in sets?

$$\bigcup\limits_{n\in\mathbb N} A_n$$ The book is asking me to prove that $f(\bigcup\limits_{n\in\mathbb N} A_n) = \bigcup\limits_{n\in\mathbb N} A_n$. I'm able to prove that f(the notation ...
4
votes
2answers
255 views

If x is an element of y and y is an element of z, is x an element of z?

Let x∈y and y∈z. Does this imply that x∈z? For example: Let y={A,B} and z={{A,B},C}. If x=A, then x∈y. My understanding, however, is that x is not an element of z since A is not an element of z.
-1
votes
1answer
63 views

A and B are sets. Prove that if $A \subseteq B$, then $\bigcup A \subseteq \bigcup B$

A and B are sets. Prove that if $A \subseteq B$, then $\bigcup A \subseteq \bigcup B$ Here's what I have so far: Let $x\in\bigcup A=\{x\mid\exists X\in A:x\in X\}$. Therefore $x\in X$. Since ...
0
votes
1answer
30 views

What is the relation between ∪A and A?

What I mean by this is ∪A⊆A, is A⊆∪A, or is ∪A=A? I'll give an example: Let A be a set and A={B, C}, where B and C are sets. Now let's say B={1,2} and C={2,3}. This means A={{1,2},{2,3}} and ...
3
votes
2answers
40 views

Can a binary relation on a set $S$ isomorphically embed every binary relation on $S$?

Is there any binary relation $R$ on a non-empty set $S$ such that $R$ isomorphically embeds every binary relation on $S$? (By "$R$ isomorphically embeds $Q$" I mean: there is a one-to-one function ...
-1
votes
5answers
95 views

Why the term “countable”?

In my computer science theory class, we are discussing the concept of countability. I understand the concept, but the choice to use the word countability seems absolutely unintuitive to me. Why was ...
0
votes
1answer
29 views

Is there a powerset equivalent to the Kleene star?

For some arbitrary alphabet E, is there an equivalent way to construct E* using powersets, sets, or sequences?
1
vote
1answer
41 views

Equivalence between two topological statements concerning the basis of a topology.

I need to show the following statement Let $\mathcal{B}\subset P(X)$ be a set of subsets of a set $X$, such that $\bigcup_{U\in \mathcal{B}}U =X$ then the following are equivalent $i)$ there ...
0
votes
0answers
39 views

Proving cardinality of the reals and the cross product of the reals [duplicate]

I am trying to prove that $\Bbb {R} \times \Bbb {R} \sim \Bbb {R}$ using the Cantor-Bernstein Theorem. So then that would mean that I need to prove that $|\Bbb {R}| \leq |\Bbb {R} \times \Bbb {R}|$ ...
0
votes
0answers
15 views

Extension of Premeasures

Here, a premeasure is a countably additive set function whereas a measure is one acting on a sigma-algebra. Not every positive premeasure admits an extension to a positive measure as the following ...
0
votes
1answer
37 views

Does the class of all finite unions of closed-open intervals on $\mathbb{R}$ form a ring sets?

Does the class of all finite unions of closed-open intervals on $\mathbb{R}$ form a ring on sets? By a closed-open interval , I mean an interval of the form $[x,y)$ A ring of sets is a non-empty ...
0
votes
1answer
17 views

Difference between Inclusion and continuation

Halmos defines the order continuation as follows: We shall say that a well ordered set A is a continuation of well ordered set B if B is a subset of A, if, in fact, B is an intial segment of A and ...
1
vote
1answer
24 views

“Disjoint union” in set theory.

I just came across a term called "disjoint union". Define $\{ A_i : i \in I\}$ be a family of sets indexed by $I$. On wikipedia it defines disjoint union as as, $$\bigcup_{i \in I} \{ (x,i): x \in ...
1
vote
1answer
28 views

Why is it that $\left(\bigcup_{\alpha \in A} K_{\alpha} \right)^c = \bigcap_{\alpha \in A} K_{\alpha}^c$

Why does $$\left(\bigcup_{\alpha \in A} K_{\alpha} \right)^c = \bigcap_{\alpha \in A} K_{\alpha}^c$$ Explain why the union of open sets is open? My teacher said it is, but I don't understand why? Any ...
1
vote
2answers
23 views

Is this in the cartesian product?

Given two sets $A$ and $\phi$, where $\phi$ is the empty set. The Cartesian product is defined by $A \times \phi = \{ (x,y) \mid x \in A, y \in \phi \}$ Why is $ A \times \phi = \phi$?
3
votes
2answers
35 views

Measures: Sequential Continuity

Disclaimer: This thread is meant as record and written in Q&A style. Let $\Omega$ be a measure space. It is well known that a measure is continuous from below as well as from above: ...
0
votes
1answer
31 views

Double Complement of a set proof

Question states: Prove the law of double complements for sets: If $A$ is a set and $A^\complement$ is its complement than prove that: $$ (A^\complement)^\complement = A$$ I started with: $$ ...
0
votes
1answer
33 views

Vitali Set: Inner Measure vs. Outer Measure

Context Nonlinearity in general of the Lebesgue integral for nonmeasurable functions reduces in some sense to inner and outer measure of nonmeasurable sets: ...
1
vote
2answers
69 views

A Countable Powerset — Where am I wrong?

Cantor's Theorem seems pretty airtight to me. So what is wrong with the following reasoning? Consider $X = \mathcal{P}(\mathbb{N})$. We say $X$ contains uncountably many sets. But the only sets that ...
0
votes
1answer
19 views

Number of sequences with n digits, even number of 1's (Continued question)

Some guy asked a very interesting question here before. He was trying to figure out a formula to calculate $a_n$ number of sequences with n digits from $\{1,2,3,4\}$ and an even number of 1's. Which ...
2
votes
1answer
33 views

An Exercise on showing thoroughly that two sets are equal

I have never had too many exercises on this subject. So while doing a couple of exercises I stumbled across a problem that keeps me confused, especially because I cannot honestly say that I understand ...
1
vote
0answers
44 views

Proving De Morgan laws

question is from Apostol's Vol. 1 One-variable calculus with introduction to linear algebra textbook. Page 16. Exercise 19. Let $\mathscr F$ be a class of sets. Then $$B-\bigcup_{A\in\mathscr ...
2
votes
2answers
41 views

Counterexamples for $f(\overline{A}) = \overline{f(A)}$ and $\overline{f^{-1}(B)} = f^{-1}(\overline{B})$ in (non-)continuous mapping $f: X \to Y$

Let $f$ be a mapping. Prove that the following three statements are equivalent. $f$ is continuous; $\forall A \subseteq X: f(\overline{A}) \subset \overline{f(A)}$; $\forall B \subseteq ...
1
vote
2answers
30 views

How can I modify individual elements in a set?

Let $A$ be a set with a value of $\{1, 2, 3, 4, 5\}$. How can I modify certain elements in a set? Something along the lines of changing the $5$ in $A$ to a $10$. Is this even possible?
1
vote
1answer
51 views

The proof of Cantor-Bernstein Theorem

I have a problem with the proof of Cantor-Bernstein Theorem here below: Take $A = (0,1)$ and $B = (0,\frac{1}{2})$. Then, $f(X) = \frac{x}{2}$ is a one to one function from $A$ to $B$ and from $B$ to ...
0
votes
1answer
21 views

Notation: Building a set from sequences of random variables, some a.s. equal

For $1 \leq i \leq n$ let $(\psi_{ij})_{1 \leq j \leq n_i}$ be sequences of random variables. Is there a better notation than $$\{\psi_{ij} : 1 \leq i \leq n, 1 \leq j \leq n_i\}$$ to build a set ...
0
votes
2answers
27 views

Proving a set identity

If $A \subseteq X$ and $A_{\alpha}$ is a collection of all such subsets, I need to prove that: $$\left(\bigcap_{\text{all }\alpha} A_\alpha\right)^c = \bigcup_{\text{all }\alpha} A_{\alpha}^c$$ My ...
0
votes
0answers
24 views

Cardinality of a set of injections [duplicate]

Let $A$ be the set of all injections $f: \mathbb{Z}_+ \rightarrow \mathbb{Z}_+$ What can we say about the cardinality of $A$ with respect to the cardinalities of $\mathbb{Z}_+$ and ...
18
votes
7answers
2k views

There is no smallest infinity in calculus?

Somewhat of a basic question, but I tried mixing set theory and calculus and the result is a giant mess. From set theory (assume ZFC) we know there is a smallest infinite cardinal, $\aleph_0$, and ...
3
votes
1answer
17 views

How to compute associative binary operation on a finite set based on partial information?

I am working on a problem, and I must be staring at the answer without seeing it since it's among the introductory problems in my abstract algebra textbook. We're told that an associative binary ...
1
vote
3answers
74 views

$\mathbb{N} \times \mathbb{N}$ is countable?

Until this morning I was pretty sure that the answer was yes. It should have the same cardinality of $\mathbb{Q}$, which is countable. Besides the cartesian product of countable set should be ...
0
votes
1answer
18 views

Help understanding proof for: Let $X$ be a set. Then $X \not\approx P(X)$ (where $\approx$ is equivalence relation)

In trying to understand the following proof, I am getting stuck on the chosen definition of $Y = \{ x \in X \mid x \not\in f(x) \}$. How do we know that such a set exists in $P(X)$ when we don't even ...
0
votes
2answers
54 views

Cross product of the reals question

Is $\Bbb {R} \times \Bbb {R} \subseteq \Bbb {R}$? If this is the case then would it be true that $|\Bbb {R} \times \Bbb {R}| \leq |\Bbb {R}|$?
0
votes
1answer
32 views

Maximum/Maximal set

Maximum or maximal set with property $P$ When I was reading some textbooks, I noticed that I do not get the meaning of the following two phrases. ($P1$) $\quad$ maximum set with property $P$ ($P2$) ...