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
3answers
30 views

Question about union with $\{∅\}$: $\{1,2\}\cup \{∅\}=\{1,2,∅\}$?

I have two quick questions: a. $\{1,2\}\cup \{∅\}=\{1,2,∅\}$ is it correct ? b. can I have an explanation why is it not just $\{1,2\}$? Or more importantly why is it important to mention the $∅$ if ...
1
vote
1answer
13 views

A theorem about cardinal numbers(an inequality)

Theorem. Let $\{ A_k | k \in K \}$ be a collection of sets indexed by the $K$, with $|K| = \kappa$. If $\forall k \in K \ \ |A_k| \leq \lambda$, then $|\bigcup\limits_{k \in K} A_k| \leq ...
2
votes
1answer
29 views

Set builder notation with $\land$?

Is it possible to rewrite set builder notation with conjunction $\land$? For example, $$y\in f(A)=\{f(x) \mid x\in A\} \\ ​​\iff \exists\,y, y=f(x)\land x\in A$$
-1
votes
1answer
21 views

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

My proof. Initially, we will show that $\cup _{n=1,2,3,...} (-1+1/n,0)\subseteq (-1,1)$. For every $n=1,2,3,...$ sicnce $-1<-1+1/n<1-1/n<1$, $(-1+1/n,1-1/n)\subseteq (-1,1)$. Now, we will ...
0
votes
0answers
17 views

Is it possible to represent {$0, ±m, ±2m, ±3m, \ldots$} in an augmented matrix? [on hold]

An augmented matrix of a system consists of the coefficient matrix with an added column containing the constants from the right sides of the equations. Source: Linear Algebra and Its Applications, ...
1
vote
1answer
11 views

Infimum inequality comparing restrictions.

Suppose $f$ is a continuous function on the real line. Say we have two collections of sets $\{A_k\}_{k=1}^{n}$ and $\{B_k\}_{k=1}^{m}$, where $n>m$ and \begin{align} \bigcap_{k=1}^{n} A_k &= ...
0
votes
1answer
56 views

What is $\left|\mathbb{N}^\mathbb{N}\right|$? [duplicate]

What is $\left|\mathbb{N}^\mathbb{N}\right|$? I know that $\forall n\in\mathbb{N}: \left|\mathbb{N}^n\right|=\left|\mathbb{N}\right|$. But is this also true for the limit?
1
vote
4answers
36 views

An equality of sets involving two directions

LEt $A,B$ be sets. Prove that $A \subseteq B \iff P(A) \subseteq P(B) $. Attempt: First, take any element of $P(A)$, say $Y$, we know by definition that $Y \subseteq A$ and so $Y \subseteq B$ ...
0
votes
1answer
14 views

An identity regarding symmetric difference of sets

Let $A,B$ be sets and define $A \triangle B = (A \setminus B) \cup (B \setminus A )$. Show that $A \triangle B = (A \cup B) \setminus (A \cap B )$. Attempt: Suppose $x \in A \triangle B$. By ...
-4
votes
1answer
47 views

The total number of subsets of a set of size 1001 is odd. [on hold]

Given the statement "The total number of subsets of a set of size 1001 is odd." determine its truthfulness. I believe the answer is that the statement is false. Could someone please provide a ...
0
votes
0answers
12 views

Is my parsing to symbolic logic of this statement correct?

Statement Prove that the natural number x is prime iff x > 1 and $\sqrt x$ there is no posi- tive integer greater than 1 and less than or equal to x that divides x. My parsing attempt into ...
2
votes
3answers
33 views

What are the differences between these two statements?

For every positive real number x, there is a positive real number y less than x with the property that for all positive real numbers z, yz ≥ z. For every positive real number x, there is a positive ...
1
vote
3answers
70 views

Find the Mistake to this Problem

Let $(a,b)$ be an open interval of real numbers and let $c \in (a,b)$. Describe an open interval $I$ centered at $c$ such that $I \subseteq (a,b)$. Here is the proposed solution to the problem: Let ...
0
votes
0answers
23 views

Is formula an intersection of sets that satisfy it? [on hold]

There seems to be a similarity between formula and intersection of sets: a formula is a property/condition that some sets have in common, while an intersection of sets is a set whose members are those ...
1
vote
0answers
23 views

induction on well-ordered sets (is this assumption necessary?)

Here is a theorem from a textbook: Let $(X,\leq)$ be a woset. Let $E$ be a subset of $X$ such that: the smallest element of $X$ is a member of $E$; for any $x\in X$, if $\forall ...
1
vote
1answer
27 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
19 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
40 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
35 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
24 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 [on hold]

If $A$ and $B$ are not disjoint sets then what would $$(A\cap B)\cup(B^c\cap A) =?$$
1
vote
1answer
31 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 ...
3
votes
2answers
37 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
65 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
23 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
21 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 ...
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}$$ ...
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
85 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 ...
0
votes
0answers
15 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
40 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 ...
-4
votes
0answers
37 views

Function definition [on hold]

Suppose we define $f : \{1, 2, 3\} \to \{7, 8, 9\}$ by $f(1)=7$, $f(2)=8$, $f(3)=9$. Now let us take the same function $f$ and give it the domain $\{1, 2, 3, 4, 5, 6\}$. What would the output (image) ...
0
votes
2answers
41 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
38 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 ...
1
vote
1answer
20 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 ...
2
votes
3answers
55 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 ...
0
votes
2answers
31 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
60 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
66 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
49 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 ...
2
votes
2answers
52 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
40 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
57 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
82 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, ...
1
vote
1answer
52 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
45 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 ...