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

0
votes
1answer
53 views

Can we express these sets as Cartesian products of two subsets of $\mathbf{R}$?

Let sets $A$ and $B$ be given as follows: $$A := \{ (x,y) \in \mathbf{R}^2 | \ \ x < y \ \ \} $$ and $$B := \{ (x,y) \in \mathbf{R}^2 |\ \ x^2 + y^2 < 1 \ \ \}.$$ Can we express $A$ or $B$ as ...
3
votes
1answer
303 views

Is a set closed under finite intersections? (about filters)

In my research I was faced with the problem (as a special example and a pattern for more general problems) whether the family $\operatorname{GR} ( \Delta \times^{\mathsf{FCD}} \Delta)$ of sets is ...
1
vote
2answers
77 views

How to prove $\Im$ is not a set?

Let's say $\Im = \{$ $A$ $|$ $A$ is an inductive set $\}$. With that, I mean $\Im $ is the "set" of all inductive sets. When I was reading induction is a right way of proving, the author proved it in ...
0
votes
4answers
328 views

Is it countable?

Show that the set of all bit strings (strings of 0’s and 1’s) is countable. Would you start by making a grid? I'm not exactly sure how to go about doing this?
0
votes
2answers
56 views

Prove that the cardinality of the reals and all binary funcions is not equal

Let $S$ be the the set of all real functions that bring back only two values: 0 and 1 (Binary functions). If $f\in S$ then $f:\mathbb{R}\rightarrow \left\{0,1\right\}$. Prove that $|\mathbb{R}| \neq ...
0
votes
1answer
45 views

Prove the following $A\oplus B = \neg((A\cap B) \cup \neg(A\cup B))$

I trying to prove the following statement: $$A\oplus B = \neg((A\cap B) \cup \neg(A\cup B))$$ what I tried to do is: $\neg(A\cup B)=\neg A \cap \neg B= \neg A \setminus B$ $\neg ((A\cap B)\cup(\neg ...
1
vote
2answers
55 views

Countability (show set is countable)

Show that the set $\mathbb{Z}_+\times\mathbb{Z}_+$ is countable.? To solve this you have to show a one to one correspondence. $\mathbb{Z}_+\times\mathbb{Z}_+\to\mathbb{Z}_+$ Then my book recommends ...
1
vote
2answers
222 views

Prove if true and find a counterexample if false (disproofs/algebraic proofs) [duplicate]

For all sets $A, B, C$ $$A- (B-C) = (A-B) -C$$ Now my books says it is false and begins showing a counter example, but how do you know it is false by just looking at it? Would you go about proving ...
1
vote
2answers
56 views

Describe four different elements of a union of power sets of power sets

$P(P(A))\bigcup P(P(P(A)))$ The empty is set one but other than that I'm not really sure what does a power set of a power set means. Any help would be appreciated. Edit: Is this how you read this ...
1
vote
1answer
64 views

Prove the following $(A \cap B) \cap (\neg (A\cap C))=A\cap ( B \cap(\neg C))$

I want to prove the following statement $$(A \cap B) \cap (\neg (A\cap C))=A\cap ( B \cap(\neg C))$$ Rewrite the LHS and RHS: $$(A\setminus \neg B)\setminus (A \setminus \neg C)=A\setminus ...
0
votes
1answer
53 views

Prove the following $A \setminus (B\setminus C) = (A\setminus B)\cap (A \cup C)$ [duplicate]

I want to prove the following so I decide to rewrite the RHS $$A \setminus (B\setminus C) = (A\setminus B)\cap (A \cup C)$$ $$ A\setminus(B\setminus C) = A\setminus (B \cap C^c) = A\cap (B\cap C^c)^c ...
0
votes
1answer
65 views

Can someone explain countability and cardinality simply?

One of the questions in my book asked: Show that the set $\Bbb Z^+ \times \Bbb Z^+$ is countable.? Now I don't want the solution to this particular problem, rather how to go about solving these types ...
0
votes
1answer
45 views

Prove the following $(a \cap(\neg b))\cup (a \cap c)=a\cap (\neg(b\cap(\neg c))) $

I want to prove the following: $$(a \cap(\neg b))\cup (a \cap c)=a\cap (\neg(b\cap(\neg c))) $$ What I tried to do so far is to minimize the LHS but I dont know if it enough: $$(a \cap(\neg b))\cup (a ...
0
votes
1answer
83 views

Constructing a bijection between intervals [closed]

So I am trying to solve questions below Let $A = \{(\alpha_1,\alpha_2,\alpha_3,\ldots): \alpha_i \in \{0,1\}, i \in N\}$, i.e., $A$ is the infinite cartesian product of the set $\{0,1\}$. Show ...
0
votes
1answer
54 views

determine the cardinalities of the set [closed]

So I am trying to figure out the cardinalities of the following sets (either finite, denumerable or uncountable ): the set of all open intervals with rational midpoints the set of all open intervals ...
1
vote
2answers
83 views

How to formally show “if $A \subseteq C$ and $B \subseteq C$, then $A \cup B \subseteq C$”?

Prove: if $A \subseteq C$ and $B \subseteq C$, then $A \cup B \subseteq C$ It's quite obvious, but I'm not sure what the proper approach is to proving a set problem that involves subsets, as none ...
0
votes
1answer
97 views

If a set $S$ is infinite, then it can be put in 1-1 correspondence with proper subset.

This is a problem from Curtis' Abstract Linear Algebra. We have the following definition of infinite set: A set $T$ is infinite if it contains a subset $U\subseteq T$ which can be put into a ...
2
votes
2answers
113 views

Can sets contain objects of different types?

Working on some basic proof work. The conjecture is There exists a set $\mathrm X$ for which $\mathbb R \subseteq \mathrm X$ and $\emptyset \in \mathrm X$. My reasoning was that this is false ...
-4
votes
2answers
116 views

Prove that $ \left( A-B\right) \cup B = A \cup B$

To prove:$ \left( A-B\right) \cup B = A \cup B$ I want it to be done in two ways:1. The algebraic way and 2 Using the method where we say,for example, $x \in A \text{ or }x\notin B $(I dont know ...
1
vote
2answers
3k views

What is the use of Delta symbol in set theory?

What is the use of $ \Delta $ in set theory?
2
votes
1answer
173 views

Let $\gamma $ be an ordinal. Prove there is an ordering preserving $f:\gamma \to \mathbb{R}$ iff $\gamma < \omega_1.$

Let $<$ be the usual ordering on $\mathbb{R}.$ If $\gamma$ is an ordinal, then $f:\gamma \to \mathbb{R}$ is ordering preserving if $\forall \alpha \in\gamma \forall \beta \in \gamma [\alpha \in ...
2
votes
2answers
40 views

Existence of certain $\left\langle{\alpha_n | n \in \omega}\right\rangle$

Let $\beta$ be a countable limit ordinal. Prove $\exists$ sequence $\left\langle{\alpha_n | n \in \omega}\right\rangle$ with the following properties: $(1): \alpha_0 = 0\;;$ $ (2): \forall n \in ...
2
votes
1answer
101 views

Proving $\kappa^{\lambda} = |\{X: X \subseteq \kappa, |X|=\lambda\}|$ [duplicate]

Let $\kappa , \lambda$ be cardinals with $\omega \leq \lambda \leq \kappa.$ Prove $\kappa^{\lambda} = |\{X: X \subseteq \kappa, |X|=\lambda\}|$. i.e could anyone advise me on how to construct a ...
1
vote
1answer
179 views

The number of worms (Moser's worm problem)

The Moser's worm problem [springer link] asks for the region of smallest area that can accommodate every plane curve of length 1. Curves can be rotated and translated and may be considered identical ...
2
votes
0answers
316 views

Suppose $R$ is a relation on $A$ and $R^{-1}$ is the inverse. Proof or counterexample

Suppose $R$ is a relation on $A$ and $R^{-1}$ is the inverse. Give a proof or counterexample for each of the following statements. (a) If $R$ is reflexive, then $R^{-1}$ is reflexive. Let $x \in A$; ...
1
vote
1answer
37 views

Set intersection problem.

Is $ A \cap B' = A - B$ where $A \cup B$ is the universal set? I am an absolute beginner at Sets, So please dont vote down my question because it might be too easy for you. $ B'$ refers to the ...
0
votes
2answers
39 views

ZF Natural Even Numbers

Regarding $\Bbb N$ as constructed using ZF ($0=\emptyset, n+1=n^+=n\cup\{n\}$), how is the property "divisible by 2" expressed (using sets and logic)?
0
votes
3answers
70 views

Prove associative of $(A \setminus B)\cup C = A \setminus (B \cup C)$

I would like to get some advice how to prove the associative property of the following: $$(A \setminus B)\cup C = A \setminus (B \cup C)$$ thanks.
1
vote
1answer
54 views

Defining sets using pairs, check if definition satisfies the pair correctness property - Kuratowski ordered pair

I know that (a,b) = (c,d) if a = c and b = d, but I have no idea what to do here. I assume I'm supposed to show that {{a},{a,b}} = {{c},{c,d}} if a = c and b = d, but how do I verify that using the ...
1
vote
1answer
116 views

Find a bijection between the two sets

I know the function to find the number of bijections is $f(n) = f(n-1) * n$ where $f(n)$ is the number of bijections of $n$, and $n = |A|$, i.e the number of elements in the set (in this case, ...
-2
votes
2answers
1k views

Specify a bijection from [0,1] to (0,1]. [duplicate]

A) Specify a bijection from [0,1] to (0,1]. This shows that |[0,1]| = |(0,1]| B) The Cantor-Bernstein-Schroeder (CBS) theorem says that if there's an injection from A to B and an injection from ...
0
votes
1answer
14 views

Proving that UB is transitive follows from B is transitive

I'm really stuck as to how to prove that if B is a transitive set, it must be the case that the union of B is transitive as well. I guess I'm just a bit shaky on the concepts of proofs overall, but ...
1
vote
0answers
31 views

How does one “separate” the cartesian product properly?

Say, $\delta>0$, $X$ and $Y$ are metric spaces, $(x_0,y_0)\in X \times Y $, and there is some property $P$ such that $$\forall (x,y) \in X \times Y: \ \ \ \ d \Big( (x_0,y_0), (x,y) \Big) < ...
0
votes
4answers
317 views

How can I express the non-intersecting sections of multiple sets with a single set operation?

I don't have a lot of experience with set theory, as I suspect this question will make clear! As the title says, I'm interested in expressing the non-intersecting sections of three sets using a ...
1
vote
3answers
475 views

Is this a poset?

Is $(S, R)$ a poset where $S$ is the set of all people in the world and $(a, b) \in R$, where $a$ and $b$ are people if $a$ is no shorter than $b$? My attempt: $a$ is no shorter than $a$. This is ...
1
vote
3answers
273 views

Can there exist an injective function from $\mathbb R$ to $(0,1)$?

I've been trying high and low to find an injective function from $\mathbb R$ to $(0,1)$, but to no avail. I've tried all sorts of polynomial functions, exponential functions, etc. but I've had no luck ...
0
votes
1answer
134 views

Kleene Star operation on sets

I have the following question, and do not understand the Kleene star operation in the context of relations. Let R be the relation $R=\{(0,1),(0,2),(1,4),(1,5),(2,3),(2,4),(2,5)\}^*$ on the set ...
2
votes
1answer
67 views

Functions from ordinals to ordinals

I'm trying to solve this problem, which appears in Schimmerling's "A Course in Set Theory." Problem. Find two functions $$f:\omega\rightarrow\omega\cdot2$$ and ...
3
votes
2answers
53 views

$Seq (\mathbb{N})$ of all finite sequences of elements of $\mathbb{N}$ is countable.

I have few questions to the proof of this claim that is illustrated in a textbook. $Seq (\mathbb{N})$ of all finite sequences of elements of $\mathbb{N}$ is countable. Proof: Since $Seq(\mathbb{N}) ...
2
votes
2answers
157 views

Bijection from $\mathbb N^\mathbb N$

Let's say I'm trying to find a bijection from $\mathbb N^\mathbb N$, i.e., the set of all functions from $\mathbb N$ to $\mathbb N$, to some other set, say an open interval $(a,b)∈R$. What do I need ...
0
votes
1answer
51 views

An implication involving filters

Let $z$ be a filter on a set $U$ and $I$, $J$ be sets of filters on $U$. Is the following implication always true? $$(\forall K \in z\, \exists x \in I \cup J : x \supseteq \mathop\uparrow\!\! K) ...
0
votes
2answers
39 views

is $((x_1,y_2),(x_2,y_2)) \in R \subseteq \mathbb R^2 \times \mathbb R^2 \space if\space x_1=x_2 \space if \space x_1=x_2 $ Transitive?

Is this a valid argument? there are only 2 elements that can be created let say $(x_1,y_2) (x_2,y_2)$ and c can not be created. therefore $P \rightarrow Q$ is false and $((x_1,y_2),(x_2,y_2)) \in R ...
1
vote
2answers
44 views

Maximal elements in a set

Prove that if there are two maximal elements in a partially ordered set, then these maximal elements are not comparable. I understand that I should show that if there are two maximal elements in a ...
0
votes
1answer
73 views

Proving $\mathcal P(A-B) = \mathcal P (A) -\mathcal P (B)$

I started with trying to prove $\mathcal P(A-B) \subseteq \mathcal P (A) - \mathcal P (B)$ $x \in \mathcal P (A) - \mathcal P (B)$ that mean $x \in \mathcal P (A) \wedge x \notin \mathcal P (B)$ ...
1
vote
2answers
86 views

Meaning of the set $\mathbb N^\mathbb N$

I came across a question which requires one to check if there's a bijection from the set $ \mathbb N^\mathbb N$ to another set. I've never seen a set defined this way and was wondering if this was ...
0
votes
2answers
56 views

$[\![n]\!]\times[\![m]\!]\sim[\![nm]\!]$ where $[\![n]\!] = \{1,\ldots,n\}$

We have got: Let $n,m\in \Bbb N$ and denote $[\![n]\!]=\{1,\dots,n\}\subseteq \Bbb N$. Prove that: $$[\![n]\!]×[\![m]\!]\sim[\![nm]\!]$$ So conclude that, for the finite sets $A$ and $B$, ...
2
votes
3answers
59 views

What does $|A|$ denote in set notation?

What does $|A|$ of a set $A$ denote? Also, what does $A\leftrightarrow B$ of sets $A, B$ mean? I encountered this in one of my textbooks which said: Of two sets $A, B$ we know $|B|$ but $|A|$ is ...
5
votes
1answer
134 views

Combinatorics question about downsets

Prove that if $\mathcal{A}$ is a downset then the average size of sets in $\mathcal{A}$ is at most $\frac{n}{2}$ ($\mathcal{A} ⊂ \mathcal{P}(n)$ is a downset if, for every $A∈\mathcal{A}$ , every ...
0
votes
2answers
149 views

Help needed with complements, partition and power sets

I'm working on some tasks which is listed below, and I'm trying to figure out if I've understood partition, power set, and complements correctly. Here are the tasks: Assume that $\{$$1, 2, 3, 4, ...
0
votes
4answers
209 views

Correct formal interval notation

I can't find any definitive answer on this topic, maybe that's because there isn't one, but I figured if there was a place to ask then SE was it! To describe a set in which $x$ and $y$ are in the ...