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

2
votes
5answers
76 views

How do I prove a set's power has $2^n$ elements?

It seems to have the same behavior as Pascal's pyramid, there's for a 2 elements set (let's call it A): $P(A)=\{\{\emptyset \}\{a\}\{b\}\{a,b\}\}$ there is 1 empty set always, 2 sets with 1 single ...
0
votes
1answer
21 views

Determining subsets in sigma field

I am given a sample space $= \{a, b, c, d, e\}$ and told that $\{\{a,b\}, \{b, d, e\}\}$ is a subset of the sigma field, which other subsets must the sigma field contain? I know the empty set and ...
0
votes
0answers
17 views

What is the name of function, which codomain is a given set?

Is there a special short term for any function $F$ from the family of functions $F(A)$ for the given set $A$ so that $A$ is the codomain of any function $F \in F(A)$? For example, suppose we ...
0
votes
2answers
48 views

If $f$ is a morphism then $x\leq f(x)$

$\mathcal{A}=(A,\leq_A)$ with $\leq_A$ a well order over $A$ and $f: \mathcal{A}\to \mathcal{A}$ is a morphism. Then $x\leq f(x) \;\forall x \in \mathcal{A}.$ I think the proof should be obvious ...
5
votes
4answers
509 views

Trying to understand the sum of ordinals

I'm having a hard time with the functions defined by transfinite induction, in particular I have the sum of two ordinals defined as follows: \begin{align}\alpha+0&=\alpha \\ ...
1
vote
2answers
31 views

Set theory basics involving unions,intersections, disjointness

Let $B_n = \bigcup_{1}^{n}A_i$ where $A_i$ are a sequence of disjoint sets. Suppose $A_1$ and $A_2$ are disjoint sets in some space $X$ and we have a set $E\subset X$. Suppose further that $B_2 = ...
2
votes
3answers
115 views

Show that $|A+A|\geq (2n-1)$

Consider a set $A$ consisting of $n$ natural numbers $\{a_i\}_{i=1}^n$ such that $a_1<a_2 < \cdots <a_{n-1} < a_n$. Define the set $A+A$ such that it contains $a_i + a_j \ ; \ i \leq j$ ...
-1
votes
0answers
22 views

Intuitive relation between set theory and logic? [closed]

How would you intuitively explain connection and interaction of classic set theory and classic logic?
2
votes
1answer
32 views

Proving cardinality of coproduct presentation is unique without choice?

The definition of an extensive category immediately implies that given two coproduct decompositions indexed by sets of equal cardinality, if the coproduct objects are isomorphic compatibly with their ...
4
votes
2answers
48 views

Does there exist a compact metric space $X$ containing countably infinitely many clopen subsets?

From this Clopen subsets of a compact metric space we know that any compact metric space $X$ contains at most countably many clopen subsets ; my question is : Does there exist a compact metric space ...
0
votes
4answers
50 views

Show that $5 \mathbb{Z} +8= 5\mathbb{Z} +3= 5\mathbb{Z} +(-2)$.

Show the following equalities $5 \mathbb{Z} +8= 5\mathbb{Z} +3= 5\mathbb{Z} +(-2)$. $5 \mathbb{Z} +8=\{5z_{1}+8: z_{1} \in \mathbb{Z}\}$, $5 \mathbb{Z} +3=\{5z_{2}+3: z_{2} \in \mathbb{Z}\}$, $5 ...
0
votes
1answer
42 views

Show that $\mathbb{Z} + \mathbb{Z} =\mathbb{Z} $.

We wil use defitinion. Definition. $\mathbb{Z} +\mathbb{Z} =${$z_{1}+z_{2}$: $z_{1},z_{2}$ $\in \mathbb{Z}$}. So, how can I prove? Can you give hint me?
0
votes
0answers
30 views

Prove $\#A \leq \#B \implies \#P(A) \leq \#P(B)$

I am having trouble properly constructing a function that goes from $P(A) \rightarrow P(B)$. Furthermore I have to show that it is injective. $\#A \leq \#B \iff$ There exists an injection $m:A ...
2
votes
2answers
38 views

Cantor middle nth's set for n in [2,3)

Taking the Cantor middle $n$th's set as constructed by successively removing the middle nth's of the interval $[0,1]$ and the resulting sub-intervals, I've seen many calculations of the length of the ...
0
votes
0answers
22 views

Question regarding the empty set as a subset and in use with measures

Let $S$ be the number of rain-free days in a city next week: $S$ = {0,1,2,3,4,5,6,7}. Let $P(S)$ be the power set of $S$. Give a counter-example to show that the following set function g is not ...
1
vote
1answer
28 views

What is a sumset?

Say we have sets $X = \{0,2,3\}$ and $Y = \{1,2,5\}$. Is the sumset defined to be $X + Y = \{0 + 1,2 +2,3+5\} = \{1,4,8\}$ or summing every element pairwise $X + Y = \{1,2,5,3,4,7,8\} $ ?
1
vote
2answers
40 views

Finding a formula for the number of functions

Let $P_{k}$ denote the set of all subsets of $\{1,2,,\ldots,k\}$. Prove that the number of functions $f$ from $P_{k}$ to $\{1,2,\ldots,n\}$ such that $f(A\cup B) = \max(f(A), f(B))$ is $1^k +2^k + ...
0
votes
1answer
13 views

Prove that symmetric difference is distributive across intersection

I have been studying sets, relations and groups and I came across this question. Somehow I can not answer it. I hope I understand correctly, if symmetric difference is distributive over intersection ...
0
votes
2answers
29 views

Let $X\subseteq \mathbb{R}$. Let $Y=(1/2) \left( X+X\right)$. Show that $X\subseteq Y$.

Let $X\subseteq \mathbb{R}$. Let $Y=(1/2) \left( X+X\right)$. Show that $X\subseteq Y$. For proof, we will use definitions. Yet, how will I use definitions?
2
votes
1answer
48 views

Trying to prove Cantor-Bernstein-Schröder following these steps

I know a proof for this theorem is a recurrent issue but I've checked wikipedia's proof and several posts in this forum about it and even if I found some similarities I couldn' solve my problem. Let ...
2
votes
1answer
44 views

For every set $X$ show that $\emptyset+ X=\emptyset X = \emptyset$

For every set $X$ show that $\emptyset+ X=\emptyset X=\emptyset$. For example, let $X$={1,2}. Then, $\emptyset+ X=\emptyset X=\emptyset$. My question is HOW? I did not understand this example.
1
vote
0answers
22 views

Stating the domain of a function using set notation

I'm trying to write the domain of $f(x+y) = \frac{1}{1+ x + y}$ given $f(x) = \frac{1}{1+ x}$ using set notation. I'm thinking first we'd have something like $Domain[ f(x) ] = \mathbb{R} \setminus ...
0
votes
1answer
21 views

When is the preimage of codomain not equal to domain?

I need to show that For every $X\subseteq A$, $X \subseteq f^{-1}(f(X))$, where $f: A\to B$. I think I understand why this is true. However, under what circumstances are they not equal? When is ...
1
vote
1answer
31 views

On half open and half closed intervals.

Which interval is commonly referred to as half closed? Is there any problem if I refer to it as half open?
-1
votes
2answers
36 views

Can decreasing sequence of sets with $A_i$ containing infinitely less elements than $A_{i-1}$ have finite limit?

An updated question to one I just asked. Can we have a decreasing sequence of sets $A_n$ each a subset of the natural numbers with all members containing countably infinitely many elements such that ...
9
votes
9answers
3k views

Set Interview Question, Any Creative Way to solve?

I ran into a simple question, but I need an expert help me more to understand more: The following is True: $ A - (C \cup B)= (A-B)-C$ $ C - (B \cup A)= (C-B)-A$ $ B - (A \cup C)= (B-C)-A$ and ...
0
votes
1answer
57 views

Proving that $f(W\cap X) \subseteq f(W) \cap f(X)$

I am trying to write the proofs and/or counterexamples to these problems, but I'm not sure if my proofs are right; I have trouble trying to write proofs. Theorem $5.4.2.$ Suppose $f: A \rightarrow ...
2
votes
0answers
23 views

Showing that an intersection of indexed sets is a subset of every individual indexed set

I am required to show that for every $k \in I$, $\bigcap_{i\in I}A_{i}\subseteq A_{k}$ where $I$ is an index for a collection of subsets $A_{i}\subseteq S$, $i \in I$. This seems obvious to me from ...
1
vote
1answer
50 views

When to use $\in$ and $\subseteq$ when talking about bases and topologies

Can someone demonstrate a concrete example of when to use $\in$ and $\subseteq$ when talking about topologies and bases? When is something $\subset$ of a basis or a topology and when is something ...
0
votes
0answers
26 views

Want to disprove $\exists$ an injection from $(A-B) \rightarrow B.$

Prove (or disprove) $\#(A-B) \leq \#B$. Can someone please check my work? Want to show $\exists$ a function $j$ such that for some $x_1,x_2 \in (A-B)$, $j(x_1) = j(x_2) \land x_1 \neq x_2$ ...
-1
votes
2answers
45 views

Prove that $f \circ g = g \circ f$ from A to A [duplicate]

How do I prove that if A is set and each of f and g is a function from A to A, then f o g = g o f? Edit: If this is not true how can I prove that it is false using sets?
1
vote
2answers
25 views

Prove $A\setminus(B \cup C) = (A \setminus B) \cap (A \setminus C)$ using element chasing?

How can I prove $A \setminus(B \cup C) = (A \setminus B) \cap (A \setminus C)$ using element chasing? I need to verify that it is correct and show the steps of element chasing.
6
votes
1answer
173 views

Why can't we order Complex Numbers? [duplicate]

I know this may very well be a silly question. I always hear that Complex numbers cannot be ordered. But there's something I'm missing... Why can't we just compare two complex numbers $z_1,z_2$ as ...
0
votes
2answers
22 views

How to prove this equality about functions over indexed and intersecting sets?

Let $f:A\to B$ be a map of sets, and let $\left\{X_{i}\right\}_{i\in I}$ be an indexed collection of subsets of $A$. I need to prove that $f\left(\bigcap_{i\in I} X_{i}\right) \subset \bigcap_{i\in ...
1
vote
1answer
22 views

Trying to prove $f(n) = |\{n' \in A| n' < n\}|$ is surjective ($A$ is infinite set of integers

As title says, I have some infinite set of integers $A$, a function $f:A \to \mathbb N$ defined by $f(n) = |\{n' \in A| n' < n\}|$ is surjective. I'm having problems proving it. I'm not entirely ...
2
votes
2answers
60 views

Filters on $\omega$

I am currently reading the book "Set theory on the real line" by Bartoszynski and Judah and I do have problems to proof the following statement: Suppose $\mathcal{F}$ is a filter on $\omega$ including ...
0
votes
1answer
25 views

elements of nested sets

I was thinking about elements of the power set, and I know that for a power set $P=\{\{\},\{a\},\{b\},\{a,b\}\}$ that $\{\},\{a\},\{b\},\{a,b\}$ are all elements of $P$. However, if you have another ...
1
vote
1answer
30 views

Concerning families of sets regarded as functions

In the course I am taking of axiomatic set theory we've defined a family of sets $F$ indexed by $I$ as any function satisfying $dom(F)=I$, where there are no assumptions about its image. This ...
0
votes
2answers
51 views

Well-formed formula, systematically rule out

Does the following formula is or is not a well-formed formula of the language of set theory? $a\in (A\subset B)$ and in either case How to systemtically tackle the above question?
1
vote
1answer
60 views

If there is an injection from $A$ to $B$, is there an injection from $A\times C$ to $B\times C$?

UPDATE: Want to show $\exists$ an injection $g:(A \times C) \rightarrow (B \times C)$. We assume $\#A \leq \#B \iff \exists$ an injection $h:A \rightarrow B$ We can let $g(a,c) = (h(a),c)$, where ...
1
vote
1answer
21 views

Prove: the cardinality of the set (A-B) is less than or equal to the cardinality of A

Hi this is my first question so please bear with me. My question is this. If A and B are sets, is $ \#(A-B) \leq \#(A) $ True? I drew some Venn diagrams and intuitively this seems to be true, $ ...
0
votes
0answers
13 views

Order type of a sum ($\bigcup$) of sets

A quick question. Is $$\textrm{ot}(\bigcup\limits_{\gamma <\lambda}\alpha_{\gamma})=\bigcup\limits_{\gamma <\lambda}\textrm{ot}(\alpha_{\gamma})?$$ where $\textrm{ot}$ stands for the order type ...
0
votes
1answer
17 views

I am confused about some specific types of domains and ranges that are provided in questions

There are some specific type of questions based on functions which map from some domain to range which is confusing to me... For example, can someone explain what sort of mapping is this: $g: ...
1
vote
1answer
36 views

Is $f(n)=\begin{cases} \frac{n}{2}&\text{if}~n~\text{is even}\\ \frac{-n-1}{2}&\text{if}~n~\text{is odd}\end{cases}$ a bijection?

let f define by : $$f(n)=\begin{cases} \frac{n}{2}&\text{if}~n~\text{is even}\\ \frac{-n-1}{2}&\text{if}~n~\text{is odd}\end{cases}$$ I would like to show that $f$ is a bijection from ...
0
votes
2answers
31 views

Increasing set or decreasing set

I know this is probably trivial but I am confused on how we determine a set is increasing or decreasing. For example suppose we have a set $\{E_j\}_{1}^{\infty}\subset M$ where $M$ is a ...
0
votes
0answers
40 views

Difficulty in understanding Cantor's diagonal argument

I recently found Cantor's diagonal argument in Wikipedia, which is a really neat proof that some infinities are bigger than others (mind blown!). But then I realized this leads to an apparent paradox ...
2
votes
2answers
68 views

Discrete Math: Multiplying a set by ∅

How would you multiply any set by $\varnothing$? Lets say $A \times \varnothing$. Would that simply be equal to $\varnothing$? or Would I write out $(a, \varnothing ), (a_1, \varnothing), (a_2, ...
2
votes
4answers
63 views

Show that $(A \cup B)-B=A$ is false. Why is my method wrong?

So the textbook uses a counter example to show this which is pretty simple. I tried playing around with the algebra. Ie. $(A \cup B)-B$ is equal to $(A \cup B)\cap \bar{B}$ and associative law says ...
0
votes
0answers
29 views

How does the cardinality of the set of all functions from $A$ to itself relate to that of $A$?

If $A$ is a set with cardinality $c$, what can we say about the cardinality of the set of all functions from $A$ to itself?
2
votes
2answers
30 views

$X$ be a non-empty subset of irrational numbers such that sum of any two elements of $X$ is rational ; then is there any upper bound for $|X|$?

Let $X$ be a non-empty subset of irrational numbers such that sum of any two elements of $X$ is rational ; then is there any possible upper bound for the cardinality of $X$ ? Can $X$ be infinite ?( I ...