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

1
vote
1answer
33 views

How do I know the fundamental group of an infinite graph is well defined?

I get that given a choice of spanning tree and base point for a (connected) graph, I can effectively change the base point through path conjugation, so there's no problem there. For finite graphs, the ...
0
votes
1answer
20 views

Generalized version of uncountable minus countable is uncountable

I think my question is generalized version of Uncountable minus countable set is uncountable I have to show: if $A$ is an infinite set, and $B$ is a subset of $A$, which satisfies $|B|<|A|$, then $...
0
votes
1answer
44 views

Is there a blackboard bold letter for the set of Boolean numbers? [duplicate]

Is there a symbol (e.g. $\mathbb{B}$) for the special set of Boolean numbers or values; ${0,1}$ or ${True,False}$?
1
vote
1answer
38 views

How does the compactness property help us show a subset $A$ of a metric space $X$ is closed?

We have a compact subset $A$ of a metric space $X$ and we want to show that this implies that $A$ is closed. Let $y \in A$ and $y \in A^c$. For each $y \in A$, we can take open neighbourhoods $U_y$ ...
1
vote
1answer
25 views

Show that $\cup_{n=1,2,3…}(-1+1/n,0)=(-1,1)$.

Is there a mistake in this question? I think, it cannot equal to $(-1,1)$.
-2
votes
4answers
44 views

Basic set theory question on non disjoint sets [closed]

If $A$ and $B$ are not disjoint sets then what would $$(A\cap B)\cup(B^c\cap A) =?$$
1
vote
1answer
33 views

Is proving “If $C⊆D⊆Y$, then $f^{-1}(C) ⊆ f^{-1}(D)$” done correctly?

Definition 9 Let $f: X\rightarrow Y$ be a function, and let $A$ and $B$ be subsets of X and Y, respectively. (a) The image of $A$ under $f$, which we denote $f(A)$, is the set of all images $f(x)$...
3
votes
2answers
41 views

Size of cardinal without choice

How can we show that $ \aleph_0 \leq 2^{2^\kappa}$ for any infinite cardinal $\kappa$ without using the Axiom of Choice? By Cantor's Theorem we can easily show that if $ \aleph_0 > 2^{2^\kappa}$, ...
3
votes
4answers
79 views

Let $A= \{1,2,3,4,5,6,7,8,9,0,20,30,40,50\}$. 1. How many subsets of size 2 are there? 2.How many subsets are there altogether?

Let $A= \{1,2,3,4,5,6,7,8,9,0,20,30,40,50\}$. 1. How many subsets of size $2$ are there? 2.How many subsets are there altogether? Answer: 1) I think there are $7$ subsets of size two are ...
0
votes
1answer
25 views

Describing the set of all points

Is there a way to describe the set of all real points in a single equation with an equals sign? Instead, is it possible to create a "function" (I use function loosely as it mathematically is supposed ...
0
votes
2answers
24 views

Naive question on symmetric difference

I have an incredibly naive question, yet which makes me doubt. Is: $(A\bigtriangleup A^c)\cup A=A\bigtriangleup A^c$, where $\bigtriangleup$ denotes the symmetric difference? I can prove yes, and no,...
0
votes
2answers
30 views

$f$ is bijective, show that $h(x)=\left(f(x); g(x)\right) \rm{\ is\ bijective\ } \iff G $ is Singleton

Let E, F and G be three sets ($E\neq 0;F\neq 0,G\neq 0 ) $ Let $h$ defined by : $$\begin{align} h \ \colon\ E & \to F\times G\\ x & \mapsto h(x)=\biggl(f(x);g(x)\biggr). \end{align}$$ with ...
1
vote
2answers
28 views

Is $h(x)=\left(x^2; 1_{[0,\infty)}(x)\right)$ an injective function?

Let h defined by : $$\begin{align} h \ \colon\ \mathbb{R} & \to \mathbb{R}^{2} \\ x & \mapsto h(x)=\biggl(f(x);g(x)\biggr). \end{align}$$ and $$\begin{align} f \ \colon\ \mathbb{R} &...
0
votes
6answers
93 views

Show that $x\subseteq y \Leftrightarrow \mathcal{P}(x)\subseteq\mathcal{P}(y)$.

Note that $\mathcal{P}(x)$,$\mathcal{P}(y)$ are power sets. My proof.$\left( \Rightarrow \right)$ Let $t\in x$. Then, $t\in y$. So, since $t\in x$, $t\in \mathcal{P}(x)$. Also, since $t\in \mathcal{P}...
0
votes
0answers
18 views

Meaning of 'extensions inside a family of sets'

what does it mean, that a function $s\in 2^{[a,b)}$ does have only k extensions inside a family of sets $J\subseteq 2^{[a,c)}$ where $a,b,c\in\mathbb{N}$ s.t. $a<b<c$?
1
vote
1answer
42 views

Is proving $(f: X→ Y)\land f(\varnothing)\neq\varnothing$ is a contradiction correct in the proof of this statement?

Definition 4 The connective $\rightarrow$ is called the conditional and may be placed between any two statement $p$ and $q$ to form the compound statement $p→q$ (read: "if $p$, then $q$". By ...
0
votes
2answers
46 views

Domain of a composite function

In set theory, given 2 functions: $f:A\to B$ and $g:B\to C$ Suppose set $A = \{1, 2, 3\}$, set $B = \{a, b, c, d,\}$, and set $C = \{X, Y, Z\}$. And $f(1) = a$, $f(2) = b$, $f(3) = c$. I know ...
2
votes
2answers
44 views

Show that the set $\mathbb{N} \times \mathbb{N}$ can be expressed as the union of a countably infinite family of countable infinite sets.

I know that $\mathbb{N}$ is countably infinite and that countability infinite sets can be split into countably infinite subsets. $\mathbb{N} \times \mathbb{N}$ = $\{(n,n) |$ $\forall n \in \mathbb{N}\...
1
vote
1answer
21 views

Associativity of cardinal sum

I'm stuck with the first exercise of chapter 9 from Jech and Hrbacek Introduction to set theory. It states: If $J_i\,(i\in I)$ are mutually disjoint sets and $J=\bigcup_{i\in I}J_i$, and if $\kappa_j\...
2
votes
3answers
63 views

Prove $|A| < |B| \leq |C| \implies |A| < |C|$

I was wondering if I actually have to construct functions here and compose them, or if I can simply argue based on cardinality. Let's say we have injections $f: A \rightarrow B$, $g: B \rightarrow C$....
0
votes
2answers
33 views

Elementary set theory - challenging problem from relations and equivalence classes

I am struggling with the following question from basics of set theory(equivalence relation, equivalence classes). The question is as follows In the set $2^{\mathbb{R} \times \mathbb{R} }$ we define ...
1
vote
3answers
63 views

What is cardinality of set of all intervals (a,b), where a, b are rational numbers?

We have set $S=\{ (a,b) | a,b \in \mathbb{Q}\}$ And we know that $(a,b)\sim \mathbb{R}$ , so $k((a,b))=c$. And $\mathbb Q \sim \mathbb N$, so $k(\mathbb Q)=\aleph_0$. I don't know how to put all ...
1
vote
3answers
68 views

What's the negation of $ \ f: X\rightarrow Y\Rightarrow f(Ø)=Ø$?

Definition 8. Let X and Y be sets. A function from X to Y is a triple (f, X, Y), where f is a relation from X to Y satisfying (a) Dom(f) = X. (b) If (x, y)$\in f$ and (x, z) $\in f$, then y=z. ...
3
votes
1answer
54 views

How to prove that $E\subset [0,1]$ with some property is countable

Let $E$ be a subset of $[0,1]$. For every sequence $(a_n)$ who's elements are in $E$ and different from each other, the series $\sum\limits_{n=1}^{\infty} a_n$ converges. prove that $E$ is countable. ...
0
votes
2answers
19 views

Union of two half-open intervals intersected by the rationals

Suppose $$\varepsilon = \{(a,b]\cap \mathbb{Q}: a,b\in\overline{\mathbb{R}}\}$$ where $-\infty \leq a < b \leq \infty$. Let $(a_1,b_1]\cap \mathbb{Q}\in \varepsilon$ and $(a_2,b_2]\cap \mathbb{Q}\...
2
votes
2answers
76 views

Subset (Comprehension, Separation) Axiom and Definability

I am reading Moshe Machover's book, Set Theory, Logic, and Their Limitations, and on p. 19 he states that if $A\cup B$ is a set, then $A$ and $B$ are too by the Subset Axiom. But this confuses me. ...
2
votes
1answer
42 views

What does $X_j \approx X$ mean when used in this blog post?

I was trying to learn disjoint union topology and used the following blog : https://drexel28.wordpress.com/2010/04/02/disjoint-union-topology/ The second theorem about disjoint topology says that if ...
0
votes
0answers
17 views

Elemental Set Theory - counterexample Bijection between power set and set of natural numbers

There is a proof that $|S| \leq |P(S)|$ with P(S) being the power set of S. Let $P = \mathbb{N}$. let $\{m_1, m_2,\cdots, m_k\} \in P(S) $. Then the binary relation (bijection) with an element of $\...
2
votes
1answer
60 views

Given $f: X → Y$ and $g: X → Y$ are two functions. How to prove that if $f⊆g ⇒ f=g$?

Definition $(x_1, x_2, ..., x_n) = (y_1, y_2, ..., y_n) \Leftrightarrow x_1 = y_1, x_2=y_2, ..., x_n = y_n$ Definition $A_1 ×A_2×A_3 \cdots ×A_n =$ {$(a_1, a_2, ...a_n)| a_1 \in A_1, a_2 \in ...
2
votes
1answer
83 views

Is [a, a[ empty?

Is the segment $[a, a[$ equivalent to the point $\{a\}$ or the empty set $\varnothing$? Can one or other be formally proved? I was wondering because in computer science it is the empty set, as the ...
2
votes
3answers
36 views

Let X be the unit interval [0, 1]. Find a function $f: X \rightarrow X$ that is a symmetric relation on X.

"R is symmetric if and only if xRy $\Rightarrow$ yRx" Question: Let X be the unit interval [0, 1]. Find a function $f: X \rightarrow X$ that is a symmetric relation on X. Source: Set Theory, You-...
1
vote
1answer
60 views

Where in the proof of this theorem shows “If (x, y)$\in f$ and (x, z) $\in f$, then y=z.”?

Definition 8. Let X and Y be sets. A function from X to Y is a triple (f, X, Y), where f is a relation from X to Y satisfying (a) Dom(f) = X. (b) If (x, y)$\in f$ and (x, z) $\in f$, then y=z. ...
0
votes
1answer
21 views

Subsets and Arbitrary Unions

In Enderton's Elements of Set Theory, he asserts that A $\subseteq$ B $\Rightarrow$ $\bigcup$A $\subseteq$ $\bigcup$B I don't believe that this is true, or at least from the way I've been trying to ...
2
votes
3answers
52 views

Prove $A$ countable and $B$ a finite subset of A $\implies (A-B)$ is countable.

Can someone verify this. I am confused because I am not sure if I am being asked to strictly construct a bijection or not, although that is probably the case. The thing that confuses me is that I am ...
0
votes
1answer
48 views

b tree least upper bound

Hi I have an university assignment question that I can't fully understand. My tutor doesn't understand some of the terminology and my lecturer in the subject is not particularly forthcoming. The ...
1
vote
1answer
17 views

Increasing sequence of cardinals and cardinal $a^{\aleph_0}$

I've got the following problem: let $m_0<m_1<m_2<\cdots$ be an increasing sequence of cardinals. Prove that the sum $m_0+m_1+m_2+\cdots$ diffiers from $a^{\aleph_0}$ for any cardinal $a$. ...
0
votes
0answers
22 views

Let $|X| \leqslant \omega$ then $X$ is finite or $|X| = |\mathbb{N}|$.

a) Let $f: \mathbb{N} \to X$ be onto. Show there is a $g:X\to \mathbb{N}$ one-to-one such that $f(g(x)) = x, \forall x \in X$. b) Then use this to show if $X$ is countable, then $X$ is either ...
1
vote
1answer
42 views

Connection between number theory and the Von Neumann construction of naturals

There are many unsolved conjectures and hypothesis in number theory. For example, the twin primes conjecture, Goldbach's conjecture, the Riemann hypothesis, infinitude of Mersenne's primes, and many ...
1
vote
1answer
10 views

Intersection of decreasing family of $\kappa-$many sets

Let's consider $\kappa$ an uncountable regular cardinal and $\lambda<\kappa$. Given any decreasing family $\{A_\alpha\}_{\alpha<\lambda}$ of sets with $\sharp A_\alpha=\kappa$, does it true that ...
0
votes
2answers
56 views

Show that $5\mathbb{N}+3\mathbb{N}$={$0,3,5,6,8,9,10,11,12,…$}. [duplicate]

Question is from my lecture notes. What will I show? It is clear, isn't it? So, $5\mathbb{N}+3\mathbb{N}$={$5n_{1}+3n_{2}$:$n_{1},n_{2} \in\mathbb{N}$}={$0,3,5,6,8,9,10,11,12,...$}.
0
votes
2answers
41 views

The product topology on $X_1 \times X_2$ - coarsest due to some continuity

Let $X_1, X_2$ be topological spaces and $X_1 \times X_2$ with the product topology. We define the projection map $\Pi_i : X_1 \times X_2 \rightarrow X_i, \Pi_i(x_1,x_2) = x_i$. Consider the following ...
1
vote
2answers
67 views

Show that $5\mathbb{Z}-5\mathbb{Z}=5\mathbb{Z}$.

My proof. Lemma. $\mathbb{Z}-\mathbb{Z}=\mathbb{Z}$. Proof. ($\Rightarrow$) Let $z\in \mathbb{Z}-\mathbb{Z}$. Then, there is $z_{1},z_{2} \in\mathbb{Z}$ such that $z=z_{1}-z_{2}$. So, $z\in\mathbb{Z}...
-1
votes
2answers
39 views

Does a polynomial in two variables which establishes a bijection between

Does a polynomial in two variables which establishes a bijection between the points with nonnegative integer coordinates and natural numbers exist? porve it
6
votes
1answer
50 views

Max size of $B \subset \{1, 2, \ldots, 3n+1\}$ for which no distinct $x, y, z \in B$ have sum in $B$

Given a set $$A=\{1,2,3,\ldots,3n,3n+1\},(n\in N^*)$$ Let $B$ be a subset of $A$, such that for any distinct $x, y, z\in B$, we have $x+y+z\not \in B$. Find the maximum number of elements $B$ ...
2
votes
1answer
42 views

Show that $x\in Bdry(A)$ if and only if $x_1^2+x_2^2+\cdots+x_n^2=1$

Let $A$ be the set of points $x=(x_1,x_2,\cdots,x_n$) such that $x_1^2+x_2^2+\cdots+x_n^2\leq 1$. Show that $x\in Bdry(A)$ if and only if $x_1^2+x_2^2+\cdots+x_n^2=1$. Suppose that $x\in Bdry(A)$, ...
2
votes
1answer
37 views

Is this proof about set product correct?

Prove that if $A\times B=A\times C$ and $A\neq \emptyset$, then $B=C$. Proof: if$$(a,h)\in A\times B \Leftrightarrow (a,h)\in A\times C$$ So we note that WLOG that if $h\in B$ then $h\in C$
0
votes
0answers
17 views

Ordinals defined by successor and union

Let $M$ be the smallest set of ordinals satisfying $0\in M$ $x\in M\implies x+1\in M$ $S\subseteq M\implies \bigcup S\in M$ What does $M$ look like? Is it all ordinals? Is it all countable ...
0
votes
2answers
40 views

$(X \setminus F) \cap Y = Y \setminus A \Leftrightarrow A = F \cap Y$

Let $(X, \mathcal{T}), (Y, \mathcal{T}_Y)$ be topological spaces, where $Y \subset X$ and $\mathcal{T}_Y$ is the subset topology. Let $A \subset Y$. During a proof of something (it's not really ...
1
vote
1answer
62 views

Is this set a contradiction or just confusing?

Book says "Prove that:$$A\cap B^c\subset B\Leftrightarrow A\subset B"$$ But if $A\subset B $ then $A\cap B^c=\emptyset$ isn't it? is book wrong?
0
votes
1answer
28 views

What am I doing wrong with the definition of union

Prove that if $A$ and $B$ are sets $$P(A)\cup P(B)\subset P(A\cup B)$$ $\Leftrightarrow$ Which seems easy using definitions: Let $$a\in P(A)\cup P(B) \Leftrightarrow (a\in P(A)) \lor (a\in P(B))$$ $$\...