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

4
votes
1answer
46 views

If $f:X\to Y$ and $g:Y\to X$ are embeddings, show that $X=X_1\sqcup X_2,Y=Y_1\sqcup Y_2$ s.t. $f|X_1:X_1\cong Y_1, g|Y_2:Y_2\cong X_2$

I have to prove If $f:X\to Y$ and $g:Y\to X$ are embeddings, show that there are $X_1,X_2,Y_1,Y_2$ s.t. $X=X_1\sqcup X_2,Y=Y_1\sqcup Y_2$ (where $\sqcup$ denotes a disjoint union of sets) and ...
1
vote
1answer
37 views

can inclusion/exclusion be done with set subtraction instead?

The inclusion/exclusion principle applied to the Venn diagram below (from Wikipedia) would give the value of $\left\lvert A\cup B \cup C\right\rvert$ as $\left\lvert A\right\rvert + \left\lvert ...
0
votes
1answer
32 views

Conditions to be an element in a set.

If $X = \{x: P (x)\}$. Can someone explain what it means to be an element of a set? Is it 1) If $a \in X$, then $P(a)$. 2) If $P(a)$, then $a \in X$. Which conditional statement is true? Or is it ...
1
vote
1answer
31 views

Is ths FOL structure necessarily infinite?

Follow up to question: Formula that's only satisfiable in infinite structures Suppose we have predicates $D$ and $R$ such that : $\exists x: D(x)$ $\forall x:[D(x) \implies \neg R(x,x)]$ ...
0
votes
1answer
27 views

Proving the set of finite subsets of $\mathbb{N}$ is countably infinite [duplicate]

So I was given a question that begins like this. Let $P_{\text{fin}}(\mathbb{N})$ be the following set (called the finite power set of $\mathbb{N}$): $$ P_{\text{fin}}(\mathbb{N}) = \{X ...
3
votes
1answer
27 views

Find the cardinality of $S=\{(x,y,z) \in \Bbb R^3: x^2+y^2=4\}$

Find the cardinality of $S=\{(x,y,z) \in \Bbb R^3: x^2+y^2=4\}$. I know that as $S\subseteq \Bbb R^3 \implies |S|\leq \mathfrak{c}$. My conjecture is that $|S|= \mathfrak c$, I think this is true ...
1
vote
3answers
46 views

About the cardinality of sigma algebra and power set

Let $X$ be a set. We know that $|\mathcal{P}(X)|=2^{|X|}$. Let $\mathcal{K}=\{A_{1},\dots,A_{n}\}$, where $A_{1},\dots,A_{n}$ are subsets of $X$. Question: Is it true that ...
1
vote
2answers
70 views

Problem with the proof 0f “ the intersection of closed sets is closed”.

I have been reading this text http://ramanujan.math.trinity.edu/wtrench/texts/TRENCH_REAL_ANALYSIS.PDF, and before I address my main question, I want to note that the author, in the same section, ...
4
votes
1answer
34 views

Principle of mathematical induction to prove well ordering principle for set of rationals.

I am not being able to find what is wrong in this proof. statement: For any set of rationals there is a least element in the set. Hypothesis: $p(k)$=For set of k rationals there exist a least ...
-1
votes
1answer
33 views

Question about the cardinality of compact sets

I am curious how to distinguished between the cardinality of a compact set [a,b] and the cardinality of the open set (a,b). If I know that my set [a,b] is a compact set can I say that there are ...
0
votes
0answers
27 views

Comprehension “ for getting more sets”?

Comprehension determines a subset formation, I think that it is a method for getting more sets, but it is common in books on set theory say that with extensionality and comprehension one has only the ...
1
vote
1answer
70 views

Will $\kappa_1, \kappa_2, m$ cardinals. Given $\kappa_1 \leq \kappa_2$. prove: $\kappa_1 \cdot m \leq \kappa_2 \cdot m$

Will $\kappa_1, \kappa_2, m$ cardinals. Given $\kappa_1 \leq \kappa_2$. prove: $\kappa_1 \cdot m \leq \kappa_2 \cdot m$. Hi, I would be happy if someone could help me with this. What I did until ...
2
votes
0answers
38 views

Which are partitions are for $\mathbb{Z}$? Which are covers for $\mathbb{Z}$? Which are both or neither?

(a) {{x : x is an even integer}, {x : x is an odd integer}} (b) {{x : x is an even integer}, {x : x is divisible by 3}} Note - divisible by 3 includes negative integers, yes? -3, -6, -9, ... and ...
1
vote
2answers
50 views

Proving that $B \cap ((A \cup B) \cap (B' \cap A')') = B$ using set algebra

Problem: Use set operation laws to prove the following set equality, and clearly indicate which law(s) you use in each step: $$B ∩ ((A ∪ B) ∩ (B' ∩ A')') = B.$$ Answer: \begin{align} B ∩ ((A ∪ ...
1
vote
1answer
28 views

Few questions about the basics of Cardinality

I am looking for some help to either conform that my reasoning is sound, or to please elaborate to me more on the subject so I can gain a better understanding. I am studying some from my class notes, ...
2
votes
1answer
28 views

Cardinality of $X^n$

I asked the following question before: Is this proof by induction that $|\Bbb Q^n|=\aleph_0$ correct? I want to know if the proccess I did that can be generalized to the case $|X|=\kappa; \kappa$ ...
1
vote
1answer
22 views

Counting problem with set theory

Let $A$ and $B$ be subsets of a set $M$ and define $S_0 := \{A,B\}$. Now for $i \ge 0$ define $S_{i+1}$ inductively as the collection of subsets of $M$ taking the form $C \cup D$, $C \cap D$ or $M - ...
-1
votes
2answers
36 views

Show the following is true [closed]

Let $A,B$ be sets. Show the following is true For any sets $X,Y$: $P(X)\cup P(Y)\subseteq P(X\cup Y)$. Answer: $A \in P(X) \cup P(Y)$. Then $A\in P(X)$ or $A\in P(Y)$. It follows that ...
2
votes
1answer
83 views

What is a Primitive Atomic Formula?

I am reading "Axiomatic Set Theory" by Patrick Suppes and he defines a primitive atomic formula as follows: A primitive atomic is an expression of the form ($v\in w$ ), or of the form ($v=w$) where v ...
-1
votes
1answer
57 views

Transitive closure of a relation [closed]

Having trouble answering the question. Let $A=\{1,2,3,4,5\}$ and $\mathcal{R}$ the relation on $A$ with matrix representation: $$\begin{array}{c|ccccc} &1&2&3&4&5\\ \hline ...
2
votes
3answers
83 views

How do I show this is a surjection?

Problem: Assume $f: \mathbb{N}_0 \rightarrow X$ and $g: \mathbb{N}_0 \rightarrow Y$ are bijections. Prove that the function $h: \mathbb{N}_0 \rightarrow X \cup Y$ defined as \begin{align*} h(n) = ...
0
votes
4answers
41 views

Confusion about proof of every asymmetric relation being an irreflexive relation

Let R be asymmetric. We need to show R is irreflexive. So by definition, we assume: (x,y)∈R⟹(y,x)∉R Definition of irreflexivity: (x,x)∉R Let's do an indirect proof, so we assume: (x,x)∈R ...
4
votes
2answers
56 views

Probability of an infinite subsequence in a randomly generated sequence of order type $\omega_1$

Given for example $\omega_1$ coin tosses (i.e. a mapping from the elements of $\omega_1$ to $\{H,T\}$ with independent probabilities half), what is the probability that there is an infinite ...
1
vote
0answers
26 views

Question about required rigour for basic elementary set theory

I am wondering if anyone can help to tell me if my methods for solutions to the problems from by book are correct, and if not please help me to get on the right path. First, prove that $$A \cap ( B ...
0
votes
2answers
36 views

Show that $(A\Delta B) \cup C = (A\cup C) \Delta (B\setminus C)$

Show that $(A\Delta B) \cup C = (A\cup C) \Delta (B\setminus C)$ I want to show it algebraically, but I just can't make it work.
0
votes
3answers
64 views

Set Theory: Proof that there is no surjection from $A$ to its powerset $\mathcal{P}(A)$ [duplicate]

Is my proof sufficient to prove that there is no surjection from set $A$ to its powerset $\mathcal{P}(A)$ if A is infinite? Pf. by Contradiction: Suppose there is surjection from $A$ to ...
6
votes
2answers
722 views

Why do we distinguish between infinite cardinalities but not between infinite values?

More specifically, why are we "allowed" to denote $|\mathbb{N}|<|\mathbb{R}|$ but not $\sum\limits_{n\in\mathbb{N}}1<\sum\limits_{r\in\mathbb{R}}1$? Can we distinguish between "countable ...
1
vote
1answer
34 views

Independence of sigma algebras

Let $(\Omega,\Sigma,P)$ be a probability space. What I know is that if $\{g_n: n \geq 1\}$ is a sequence of $\pi$ systems where $g_n \subset \Sigma$, then $\{g_n: n \geq 1\} $ is independent if and ...
3
votes
2answers
47 views

Alternate Axiom of Infinity

The Axiom of Infinity states that there is a set $S$ containing $\varnothing$ such that if $x$ is an element of $S$ then so is $x\cup\{x\}$. Is the following variant equivalent? There exists a ...
0
votes
1answer
33 views

Find the cardinality of $S=\{(x,y) \in \Bbb R^2 : 2x+3y<5\}$.

Find the cardinality of $S=\{(x,y) \in \Bbb R^2 : 2x+3y<5\}$. Attempt: I graphed this set, and I noticed that the simpler set $(0,1)^2=B\subset S$, and I thought these two sets had the same ...
0
votes
2answers
107 views

Is this proof for $A,B$ countable $\implies A\cup B$ countable?

Is this proof for $A,B$ countable $\implies A \cup B$ countable? Here $\Bbb N=\{0,1,\dots\}$ Suppose I know $-\Bbb Z \simeq \Bbb N$. Then "$|A|\leq| \Bbb N |$ and $|B| \leq |\Bbb N|$" is equivalent ...
2
votes
1answer
38 views

Correct way to write the set theoretic defintion of a relation?

I want to write the set theoretic defintion of a relation $\preceq$ on a set $X$. So I thought I need to write that we have either $a \preceq b$ or $a \not\preceq b$. However writing $\forall a,b: (a ...
-1
votes
1answer
31 views

What would be the result of the given cartesian product? [closed]

What if a null set is an element of a set out of the two between which cartesian product is to be performed? I mean {1,2, phi } x { 2, 3, 4} Also , discuss about questions like {1,2,{1,2}} x { ...
0
votes
1answer
28 views

pre-image of a set that isn't in the image of that set

Let $A=\{X,Y,Z\}$ be a set. Define a function $f:A \to \mathbb N$ as the set of ordered pairs $$f=\{(X,1),(Y,2),(Z,3)\}$$ then, the pre-image of $f$ under $C \subset \mathbb N$ can be defined as ...
1
vote
1answer
24 views

Proving that a relation $R$ is transitive iff $R \circ R \subset R$.

Problem: Let $R$ be a relation over $X$, i.e. let $R = \left\{ (x,y) \in X \times X \mid x \in X \wedge y \in X \right\}$. Prove that $R$ is transitive if and only if $R \circ R \subset R$. Attempt ...
2
votes
2answers
38 views

Various set operations and the empty set…

Let A = { {}, {{}}, 1, a, cat, {1, a, cat} }. Determine the sets. (a) A \ { a, b, c } = { {}, {{}}, 1, cat, {1, a, cat} }. (b) A ∪ { x } = { {}, {{}}, 1, a, cat, {1, a, cat}, x }. (c) A ∩ { cat, ...
0
votes
1answer
25 views

Proving that $A \Delta C \subset (A \Delta B) \cup (B \Delta C)$

For two sets we define $A \Delta B = (A \cup B) \setminus (A \cap B)$ (symmetric difference). Problem: Proof that \begin{align*} A \Delta C \subset (A \Delta B) \cup (B \Delta C). \end{align*} ...
1
vote
2answers
66 views

Prove that there exists a countable collection of rectangles in $\mathbb{R}^n$

How can I show that the collection of all the rectangles $[a_1,b_1]\times \cdots \times[a_n,b_n]$, with each $a_i,b_i$ rational, can be arranged in a sequence, that is, that set is countable? Maybe I ...
0
votes
1answer
11 views

Interpretation of proof of the Lebesgue-Stieltjes measure as a $\sup$ over compact subsets

The following is part of a theorem and proof in Folland's Real Analysis: Modern Techniques and Their Applications: Let $\mu$ be a complete Lebesgue-Stieltjes measure on $\mathbb{R}$ associated to the ...
3
votes
2answers
61 views

Are sequences properly denoted as $\subset$ of a set, or $\in$ a set?

Given some sequence $(x_n)$ of some subset $M \subset \mathbb{R^n}$, is it more appropriately to denote $(x_n) \subset M$, or $ (x_n)\in M$? This stems from confusion of using "in" i.e. whenever ...
1
vote
1answer
32 views

Is this proof by induction that $|\Bbb Q^n|=\aleph_0$ correct?

Is this proof by induction that $|\Bbb Q^n|=\aleph_0$ correct? Suppose I know that $|\Bbb Q|=|\Bbb N|=|\Bbb N^2|=\aleph_0\cdot\aleph_0=\aleph_0$. Proof: Suppose $|\Bbb Q^n|=\aleph_0$, then ...
1
vote
1answer
22 views

$f: B \to C$ injective $\implies \exists \hat f:A\subset B \to C$ injective.

$f: B \to C$ injective $\implies \exists \hat f:A\subset B \to C$ injective. I've stumbled with a problem where using this would trivialize it. This statement appears to be pretty obvious to me, so ...
0
votes
2answers
76 views

Bijective map from $\Bbb Z$ to $\Bbb Q$

There exists a map $f: \Bbb Z\rightarrow \Bbb Q $ such that $f$ is A. Bijective and increasing B. Onto and decreasing C. Bijective and satisfies $f(n)\ge 0$ if $n\le 0$ D. Has ...
3
votes
1answer
61 views

Existence of a map $\phi \colon \mathbb N\cup \{0\} \rightarrow \mathbb N\cup \{0\}$ that holds the property $\phi (ab) = \phi(a)+ \phi(b)$

Does there exist a map $\phi \colon \mathbb N\cup \{0\} \rightarrow \mathbb N\cup \{0\}$ that holds the following property? $$\phi (ab) = \phi(a)+ \phi(b)$$ If they do what do they ...
1
vote
0answers
23 views

Show that a collection of finite unions of sets of the form $(a,b]\cap \mathbb{Q}$ is an algebra

The following is a question from Folland's Real Analysis: Modern Techniques and their Applications. (Question 23 page 32) Let $\mathcal{A}$ be the collection of finite unions of sets of the form ...
5
votes
2answers
110 views

Is $(a,a]=\{\emptyset\}$?

Let $a \in \mathbb{R}$, and consider the half open interval $(a,a]$. Is it correct to write this half open interval as $(a,a]=\{\emptyset \}$? Or $(a,a]=\{a \}$?
1
vote
3answers
62 views

Cardinality of the Cartesian Product of Two Equinumerous Infinite Sets

Is the cardinality of the Cartesian product of two equinumerous infinite sets the same as the cardinality of any one of the sets? I couldn't find this explicitly stated in any handout or text. This ...
3
votes
3answers
48 views

Use class algebra to prove the following: If A∩B = ∅ and A∪B = C, then A = C-B

I'm having a bit of trouble proving the following. If A∩B = ∅ and A∪B = C, then A = C-B My initial attempt is to prove it directly, however, I believe I'm assuming the consequent, namely, A = C-B, ...
4
votes
2answers
82 views

On the definition of a filter: Isn't $\emptyset$ a subset of any set?

Beginning my study of nonstandard analysis, I have found this definition of a filter U on a set J, where A, B are subsets of J: Proper filter: $\emptyset \not\in U$, Finite intersection property: If ...
2
votes
1answer
30 views

Can it be proved without the axiom of choice that every cardinal is comparable with every finite cardinal?

Can it be proven in ZF, without using the axiom of choice, that every finite set is a universal size comparator, meaning, is comparable with every set in terms of size? And what is the proof?