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
2answers
44 views

Is $\mathbb{N} = \mathbb{Z}^+$?

Because $\{1,2,3,4,\ldots\}$ contains all natural numbers, which are also all positive integers.
1
vote
2answers
23 views

Cardinality of $E=\left\{\left(x,y\right):x,y>0\text{ and }x+y,xy\in\mathbb{Q}\right\}\subseteq\mathbb{R}^2$

I want to find the cardinality of $$E=\left\{\left(x,y\right):x,y>0\text{ and }x+y,xy\in\mathbb{Q}\right\}\subseteq\mathbb{R}^2.$$ This problem came from a recent real analysis comprehensive exam ...
2
votes
1answer
31 views

Is it consistent without the axiom of choice that every permutation of some infinite set have fixed points?

A "permutation" of a non-empty set means an injective mapping of the set onto itself. Let $S(1)$ be the statement "There exists a permutation of every set containing at least two elements, which has ...
2
votes
2answers
10 views

Show that all intervals contained in $[0, 1]$ is a semi-algebra

Suppose $J = \{\text{All intervals contained in }[0,1]\}$ I am having trouble showing that the complement of any element of $J$ is equal to a finite disjoint union of elements of $J$. It seems ...
1
vote
2answers
34 views

Show $f(f^{-1}(B_0))\subset B_0$ and that equality holds if $f$ is surjective

Let $f: A\to B$. Let $A_0\subset A$ and $B_0\subset B$. Show $f(f^{-1}(B_0))\subset B_0$ and that equality holds if $f$ is surjective. Attempt: I already did the first part. It is showing that ...
0
votes
1answer
26 views

Let $\mathfrak T_X = \{f^{-1} (U) : U \in \mathfrak T_Y\}$ then $\mathfrak T_X$ is a topology on X. False?

Let $f :X \rightarrow Y$ be a function and suppose that $\mathfrak T_Y$ is a topology on $Y$. Let $\mathfrak T_X = \{f^{-1} (U) : U \in \mathfrak T_Y\}$ then $\mathfrak T_X$ is a topology on X. ...
0
votes
0answers
20 views

Elementary substructures and eventually constant variable assignments

One proof of the Downward Löwenheim Skolem Theorem is via consideration of elementary substructures. In a discussion of this theorem, Christopher Leary writes the following: "Suppose that $ ...
0
votes
0answers
9 views

Uniting sequentially a countable set with a “dense barrage”

consider following setup: $$ D = \{1-\frac{1}{2^n} |\space n \in {\mathbb N_0} \} $$ $$ f(x) \begin{cases} x, & \text{if $x \in D$} \\ 1, & \text{if $x \in \mathbb N_+$} \\ 0, & else ...
0
votes
2answers
38 views

How to use the element method to prove the following sets are equal?

I have been asked to describe the following sets, and then prove my answers using the element method, but i am not sure how to do this. I am trying to prove that (b) is equal to $0$ as $i$ ...
1
vote
3answers
56 views

The cantor set is uncountable

I am reading a proof that the cantor set is uncountable and I don't understand it. Hopefully someone can help me. Let $C$ be the Cantor set and $x\in C$. Then there exists unique $x_k\in \{0,2\}$ ...
0
votes
2answers
29 views

Proving Set using the laws of set theory

Let $A$ and $B$ be any sets. Prove the following set identity using the laws of set theory (set identities). So I am trying Justify each step with the law I used. $A\cap(B\cup A')\cap B'=\emptyset$ ...
1
vote
2answers
45 views

In set theory, what is the difference between $\emptyset \subseteq A$ and $\emptyset \in A$?

I know that sometimes In set theory, $\emptyset \subseteq A$ is true, whereas $\emptyset \in A$ is false. What is the difference between $\emptyset \subseteq A$ and $\emptyset \in A$ ?
0
votes
3answers
28 views

If $A = \{a,b,c,d\}$, is $\{b,c\} \subseteq \mathcal P(A)$?

If $A = \{a,b,c,d\}$, then is $\{b,c\}\subseteq \mathcal P(A)$ ? I thought the answer was true, but I am not totally sure on that, because I am not sure if it is correct to say that $\{a,b\}$ is a ...
-3
votes
1answer
21 views

Set of all functions between two sets [on hold]

Let $A,B,C,D$ be sets such that $|A| = |B|$ and $|C| = |D|$. Show that $|A^C|=|B^D|$.
0
votes
2answers
18 views

Proving De Morgan's law with the minus sign

So I know how to prove De Morgan's Law in this form: $A\cap (B\cup C)^{c}$, what I'm trying to do for practice is prove it in the slightly different notation: $A- (B\cup C)$ I get everything except I ...
0
votes
2answers
31 views

Why is the number of subsets equal to the number of relations?

In this question I don't understand why the number of subsets is equal to the number of relations. Any help is welcome.
1
vote
1answer
23 views

Proving $(A\times B) \cap (C\times D) = (A\cap C) \times (B\cap D)$

So there is a similiar question in the archives which I looked at after I attempted my proof: Proving that for any sets $A,B,C$, and $D$, if $(A\times B)\cap (C\times D)=\emptyset $, then $A \cap C = ...
3
votes
4answers
56 views

If $A = \{a,b,c,d\}$, what does $\{\{a\}\}$ mean?

I am trying to understand the significance of curly brackets in set theory. Let $A = \{a,b,c,d\}$. I understand $A$ is a set that includes the objects $a,b,c,d$. However, what does $\{\{a\}\}$ ...
8
votes
3answers
967 views

I thought the | symbol meant “divides by”, but in set theory, does it mean something different?

I thought the | symbol meant "divides by", but in set theory it seems that it means "such that." However, I thought we wrote "such that" as ...
1
vote
1answer
19 views

Show that the set of all finite subsets of $\mathbb{N}$ whose size is exactly $n$ where $0<n\in\mathbb{N}$ is countable

I got this problem: Show that the set of all finite subsets of $\mathbb{N}$ whose size is exactly $n$ where $0<n\in\mathbb{N}$ is countable. I.e. Show that $|\{P\in\mathbb{P}(\mathbb{N})| ...
0
votes
3answers
41 views

Is it true $A\cup (B - C) = (A\cup B) - (A\cup C)$ ? additional intuition of question

So I have solved the majority of this question $A\cup (B - C) = (A\cup B) - (A\cup C)$ and as well I looked at the solution that was posted previously to this question: Is it true that $A \cup (B - ...
0
votes
2answers
30 views

Can this relation be transitive but not symmetric and reflexive?

Let $A = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12\}$. Give an example of a relation $T$ on $A$ with at least three elements that is not reflexive, not symmetric, but transitive. Explain clearly why ...
1
vote
0answers
50 views

equality of Cardinality of $\mathbb{R}$ and $\mathbb{R^2}$

There was a question in our exam which wanted us to prove that $\mathbb{R}$ and $\mathbb{R^2}$ both have same Cardinality. My approach to prove this problem was to try to make a bijection between ...
-1
votes
1answer
33 views

Left inverse of a real function [on hold]

Find two left inverses for each of the following functions: 1) $f:[0,\infty) \rightarrow \mathbb R$ defined by $f(x)=x^{3}+4$ defined for $x\in[0,\infty)$ 2) $g:\mathbb R \rightarrow \mathbb R$ ...
0
votes
2answers
40 views

is this set finite or infinite

Is the set $\{2k \mid k \in \mathbb{N}\} \cap \{3k \mid k \in \mathbb{Z}\}$ finite or infinite? Justify your answer. I understand $\cap$ means the intersection of the two sets so it will be all the ...
0
votes
1answer
28 views

Meaning of the composition of functions

I've a slight curiosity about the composition of functions. Why the composition of functions is read from right to left?   Example, take 2 functions $f:X \rightarrow Y$ and $g:Z \rightarrow X$, and ...
1
vote
3answers
55 views

Proving that $A\cap B \subseteq C \iff A \subseteq \overline{B} \cup C$

I'm trying to prove the following statement: $$A\cap B \subseteq C \iff A \subseteq \overline{B} \cup C$$ I need to do it using a formal proof.. I've tried to do it for some time now and couldn't ...
0
votes
1answer
21 views

Proof of inverse of composite functions

Let $A$, $B$ & $C$ sets, and left $f:A \rightarrow B$ and $g:B \rightarrow C$ be functions. Suppose that $f$ and $g$ have inverses. Prove that $g\circ f$ has an inverse, and that $(g\circ ...
2
votes
1answer
37 views

Prove divisibility is a partial order relation over natural numbers

I have proceeded like this so far: (this natural number set includes $0$) Reflexivity: Proof: $a = k \cdot a,$ since $k$ also belongs to natural number, it is proved. Anti-symmetry: $a \mid b$ ...
0
votes
3answers
98 views

Which axiom of set theory does this formula represent ? Why? [on hold]

Which axiom of set theory does the statement below represent? Why? \begin{align}\exists x\bigg(&\forall y\Big(\neg\exists z\left(z\in y\right)\to y\in x\Big)\\&\land\forall w\Big(w\in ...
-2
votes
1answer
39 views

Calculating the size of a complicated power set [on hold]

Let $A, B$, and $C$ be sets with $|A| = r$ , $|B| = s$ and $|C| = t$ . Find the minimum and maximum value of k if $$k = |\mathcal P\left(\mathcal P\left((A\times B) \setminus ...
1
vote
0answers
16 views

Proving that a union of a countable and an uncountable set is equivalent to the uncountable set (proof check)

Let $A$, $B$ be sets with $|B|=\aleph _0$ and $|A|>\aleph _0$, Prove that $|A\cup B| = |A|$ I've already seen somewhere here (though can't seem to find it now) a proof using the fact that ...
1
vote
1answer
25 views

Let $f:(X, \mathfrak T_X) \rightarrow (Y, \mathfrak T_Y)$ be a continuous function. Then $f(Cl(A) = Cl(f(A))$.

Let $f:(X, \mathfrak T_X) \rightarrow (Y, \mathfrak T_Y)$ be a continuous function. Then $f(Cl(A) = Cl(f(A))$. My definition of closure is: Let $(X,\mathfrak T)$ be a topological space and let $ A ...
0
votes
2answers
46 views

How to write a proof in Set Theory?

I am relatively new to Set Theory. I am trying to write a proof showing that $(A-B)^\complement = A^\complement \cup B$ But I don't even know where to start. If someone wouldn't mind ...
0
votes
3answers
53 views

Prove $A\cap (B-C) = (A\cap B) - (A\cap C)$

Does Prove $A\cap (B-C) = (A\cap B) - (A\cap C)$? So I've drawn a bunch of diagrams, tried a few numerical examples and it appears like it is a true statement. So I've attempted to prove it but I'm ...
3
votes
2answers
60 views

Cardinality of a basis of an infinite-dimensional vector space

How would you find the cardinality of the basis of $\mathbb{R}$ over $\mathbb{Q}$? Is it countable or uncountable? In general, how do you find the cardinality of a basis of an infinite-dimensional ...
1
vote
1answer
26 views

Assuming $A$ is infinite, show that the set of sequences of $A$ is equinumerous to $A$

The question: Assume that $A$ is an infinite set. Prove that $A$ is equinumerous to Sq($A$). Clarification: We're using Enderton's "Elements of Set Theory", which defines natural numbers ...
1
vote
1answer
44 views

A question about infinite sets and Cantor's Power Set theorem

Let $\operatorname{Card}(X)$ denote the cardinal number of the set $X$. The standard proof of Cantor's Power Set theorem stating that "$\operatorname{Card}(X) < \operatorname{Card}(2^X)$" is ...
2
votes
5answers
86 views

Set theory $A-(B-A) = A-B$

Determine which of he following statements are true for all sets $A,B,C,D$. If a double implications fails, determine whether one or the other statement of the possible implication holds, If an ...
1
vote
2answers
29 views

Type of set theory used in Munkres w.r.t to a question

I'm doing problems from the first section of Munkres Topology based on set theory notions and it asked to confirm if the following equation is true given sets A,B: $$A - (A-B) = B$$ Now I said it is ...
4
votes
2answers
49 views

Choosing a Cauchy sequence for a real

It is easy to form in ZF, for each real $a$, a "canonical" Cauchy sequence that converges to $a$. For example, one can take the sequence of finite initial segments of the decimal expansion of $a$, ...
1
vote
1answer
33 views

Zorn's Lemma's chain condition

Zorn's Lemma requires that every chain in a partially ordered set $X$ has an upper bound. In this article Gowers uses Zorn's Lemma to find a maximal linearly independent (over $\mathbb{Q}$) subset of ...
0
votes
1answer
116 views

Uncountable chain of subsets of $\mathbb N$ [duplicate]

Denote by $\mathbb{N}$ the set of natural numbers and by $2^{\mathbb N}$ the set of all subsets of $\mathbb N$. Let $E$ be some subset of $2^{\mathbb N}$ such that for every pair of elements in $E$, ...
1
vote
1answer
63 views

Brouwer's fixed point continuous function

Can anyone point me out the continuous functions without brouwer fixed point's for the following sets $$A = \{x \in \mathbb{R}^2 | x_1,x_2 \geq 0 \text{ and }x_1^2+x_2^2 = 1 \}$$ $$B = \{x \in ...
2
votes
2answers
55 views

Explaining intersections to a 6th grader

$A=\{1,2,3,4,5\}$ $B=\emptyset$ How to explain to a learner from 6th grade the result for $A \cap B$ ? For a 6th grade student, it could be difficult to understand why the result is $\emptyset$. ...
2
votes
3answers
53 views

Prove $\bigcap S$ exists for all $S \ne \emptyset$. Where is the assumption $S \ne \emptyset$ used in the proof?

I know that $\bigcap S = \{x : \forall A \in S, x \in A \}$ Here if $S = \emptyset$ then there is no $A$ which satisfies the property. However, why is it then that it defaults to every possible ...
0
votes
1answer
20 views

Proving that $B_1$ and $B_2$ doesn't have maximal element

This is one of the problem I have been solving form Velleman's How to prove book: Suppose $R$ is a partial order on $A$, $B_1 \subseteq A$, $B_2 \subseteq A$, $\forall x \in B_1 \exists y \in B_2 ...
1
vote
1answer
24 views

Proof set theory involving instantiation

Is it okay to instantiate with the same element in universal and existential instantiation? Here follows my proof of the following theorem. Theorem If $A \subseteq B \setminus C $ and $A \not = ...
1
vote
0answers
34 views

Set Theory Proof for Trignometry

How do I solve whether $A$ is a subset of $B$, $B$ a subset of $A$, and whether either are proper subsets of each other for the following $$A=\{x \in \mathbb{R} \mid \cos x \in \mathbb{Z}\},\\ B=\{x ...
1
vote
2answers
34 views

$A\subseteq B\to C\setminus B\subseteq C\setminus A\,$ — how to prove this?

Given $A \subseteq B $. Prove for every set $C, C\setminus B \subseteq C \setminus A $. Logical Argument: Given: $\forall x, x \in A \rightarrow x \in B $ Goal: $\forall C \forall x , x\in ...