This tag is for elementary questions on set theory - the sort of material covered in "Chapter 0" of graduate texts and in undergraduate set theory texts. Topics include intersections and unions, de Morgan's laws, Venn diagrams, relations, functions, countability and uncountability, power sets, ...

learn more… | top users | synonyms

3
votes
2answers
35 views

Proving or disproving $\{\{a\},b\}=\{\{c\},d\}\iff a=c \land b=d$

Prove/disprove: $\{\{a\},b\}=\{\{c\},d\}\iff a=c \land b=d$ I know the LHS isn't like in the definition of ordered sets so it's probably false but I can't find any numbers as counter example, nor ...
0
votes
4answers
24 views

Is it true $f^{-1} (B^C)=(f^{-1}(B))^C$? Is it true $f (B^C)=(f(B))^C$?

Is it true $f^{-1} (B^C)=(f^{-1}(B))^C$? Is it true $f (B^C)=(f(B))^C$? I feel really confused about this. Can anyone tell me whether it is true and why? Thanks so much!
0
votes
1answer
15 views

Set builder form for representing strings

Is there a way to represent strings or palindromes using set notation? For representing palindrome using set notation, I arrived at this notation $$S=\{ab^{n}c:N\; |\; n \geq 1 \land n \leq 3\}$$ I ...
0
votes
1answer
25 views

Stuck on basics: How to prove that {subst($\alpha$,s)} is well defined?

So I feel like this is a really basic point that I'm missing and I can't really manage to prove that: So I have a substitution function $s: Var \rightarrow WFF$ and a subst function: $WFF \times ...
0
votes
2answers
40 views

The cardinal of the set of all measures on $\mathbb{R}$

It is a very simple question that I don't know how to do: Let $M = \{\mu \colon \mathcal{B}(\mathbb{R})\to \mathbb{R} \colon \mu \text{ is a measure}\}$ $$|M| = \ ?$$ Any help will be appreciated.
1
vote
1answer
50 views

Proving this equivalence relation

If $X,Y$ are reflexive, symmetric, and transitive, then $X \times Y$ is an equivalence relation where ${(a,b):a\in X, b\in Y}$. I am trying to self learn these topics. I do know what an ...
0
votes
0answers
53 views

Prove $X\times Y$ is an equivalence relation

(Relation between two sets) If $X$ and $Y$ are sets, a relation between $X$ and $Y$ is a subset $R \subset X \times Y.$ For a relation $R \subset X\times Y$ and $a \in X$ and $b \in Y$ if $(x,y) \in ...
5
votes
2answers
386 views

Inverse of a set, possible?

Just like ordinary algebraic operations have inverses, could we imagine the inverse of a set? Like $x\in\{x\}$ then maybe the inverse denoted $[|x|]$ would mean $$\{\ [|x|]\ \}=x$$ Would this idea ...
1
vote
1answer
32 views

The empty set as an Indexing set. [duplicate]

For each $\alpha\in I$, let $A_\alpha$ be a subset of some nonempty set $S$. So if $I=\emptyset$, then $$ \bigcup_{\alpha\in I} A_\alpha=\emptyset $$ and $$ \bigcap_{\alpha\in I} A_\alpha=S. $$ Why ...
-1
votes
2answers
40 views

Set theory: Why are these two sets different?

I'm currently working through a set theory book and one of the exercises is to explain why $\{z|z\subseteq \{\emptyset\}\}$ and $\{x|x\in \mathbb{Z}, 0<x<1\}$ are different. I'm just completely ...
2
votes
0answers
33 views

Clarification on the definition of $X^{\omega}$

I have never seen this notation before (graduated with a math degree a few months ago; not in school currently). Here's what I gather from Munkres' Topology: Given a set $X$, an $\mathbf{\omega}$ ...
1
vote
4answers
61 views

Is there numbers that don't fit in our sets of numbers?

It is said that the first numbers we used were natural numbers like $0$, $1$ ,$2$... in $\mathbb{N}$. Then we discovered negative numbers $-1$,$-2$... , and classified them all in $\mathbb{Z}$. Then ...
3
votes
2answers
31 views

Cardinal Arithmetic proof issues.

Let $X$ be a finite set and let $x$ be an object which is not an element of $X$. Then $X \cup \{x\}$ is finite and $|X \cup \{x\}| = |X| + 1$. Proof. Let X be a finite set with cardinality n, ...
2
votes
1answer
35 views

Existence of finite sets of infinite set without using AC

Is it possible to prove that every infinite set $B$ has a subset of cardinality $n$, for every natural $n$, without using AC? I know how to prove this claim by induction. In the induction step I chose ...
1
vote
3answers
99 views

Is natural numbers set $\mathbb N$ infinite set?

A set with uncountable number of elements is called an infinite set. Is that the set of all natural numbers, $\Bbb N=\text{{$1,2,3,\ldots$}}$ infinite set? As far i know $\Bbb N$ is "countably" ...
3
votes
1answer
32 views

Question concerning the universe of sets.

I am reading Charles Pinter's Introduction to Set Theory Every proper class is in one-to-one correspondence with the universal class $\mathscr{U}$, that is, the class of all sets [emph. added]. ...
1
vote
2answers
56 views

Disjoint Exhaustive Subsets with Alternate Elements and equal Cardinality

Suppose $U$ is an ordered infinite set, I want to construct subsets $A$ and $B$ such that: (1) (Disjoint) $A \cap B = \phi $ (2) (Exhaustive) $A \cup B = U$ (3) (Alternate elements) $\forall x,y ...
1
vote
5answers
82 views

Prove that if sets $A$ and $B$ are countable, then their union $A\cup B$ is countable

Prove that if sets $A$ and $B$ are countable, then their union $A\cup B$ is countable. I'm really confused because I'm not sure if $A$ and $B$ are finite or infinite. If I have to consider every ...
2
votes
2answers
58 views

Set theory intersections and unions

I'm in an intro to discrete mathematics course, and this is a question on my first homework. I showed what I have so far, I think the answer to the first part of the question may be right, but I'm ...
-4
votes
1answer
67 views

How to describe the Cartesian product $\mathbb{R} × \mathbb{R}$?

I am taking a discrete mathematics course in the spring and in an attempt to fully understand the material I am reading ahead. I came across this statement Let $\mathbb{R}$ denote the set of all real ...
1
vote
1answer
56 views

Basic Set Theory regarding the set $\{0\}$

For each nonnegative integer $n$, let $U_n = \left \{n,−n\right \}$. Find $U_1,\:U_2,\:\text{and}\:U_0$. $U_1 = \left \{1,−1\right \}, U_2=\left \{2,−2\right \}, U_0 = \left \{0,−0\right \} = \left ...
1
vote
4answers
64 views

Show the inverse of a bijective function is bijective

We have a function $\varphi:G\rightarrow H$ is an isomorphism, show its inverse $\varphi^{-1}:H\rightarrow G$ is also an isomorphism I am fine with showing it to be a homomorphism and surjective, ...
-3
votes
1answer
34 views

Injective function from rational numbers to rational numbers [on hold]

Suppose we have $f\colon\mathbb{Q}\to\mathbb{Q}$, $f\circ g=f$ and $g\circ f=f$. Question: is $g$ the identity function $g\colon\mathbb{Q}\to\mathbb{Q}$? Is $g$ and injective function? (meaning ...
1
vote
1answer
48 views

Show an equivalence via induction

Let $f$ be a set function $f: 2^{V} \rightarrow \mathbb{N}_{0}$; let $S,T\subset V$ be such that $S \subset T$ and let $j$ be any element such that $j \in (V \setminus T)$ (so $j$ doesn't belong to ...
1
vote
3answers
64 views

Rigorous proof that countable union of countable sets is countable

I am unsuccessfully trying to understand the proof of the fact that countable union of countable sets is countable.The argument presented till now is: Let $\displaystyle \bigcup S_n$ be a countable ...
0
votes
1answer
27 views

Properties of Image and Inverse Image

Let $f:X\rightarrow Y,A\subset X$ and $B\subset Y$. If $f^{-1}(B) \subset A$, then $B \subset f(A)$ I cannot understand that why this statement is false. Any counterexample?
1
vote
1answer
52 views

How to denote the set of all students who take the same class as some given student $s'$?

I have a set of Students: $S = \{s_1, \ldots, s_2 \}$. Now each student takes some class (doesn't matter what class). Now I need to have a set $X$ that contains all students that take the same class, ...
2
votes
2answers
19 views

How to prove this statement about this relation:

Let $p$ be a prime. On $\mathbb{Z}_{>0}$ we define the relation $\sim$ as $a\sim b\iff [\forall n\in \mathbb{Z}_{>0}: p^n|a \iff p^n|b]$. Prove that $[\forall x,y \in \mathbb{Z}_{>0}: x\sim ...
1
vote
1answer
26 views

What is the cardinality of the following equivalence classes?

We have the relation $\sim$ on $\mathbb{R}$ defined by $a\sim b \iff [\exists q\in \mathbb{Q}: a-b=q\pi]$. What are the possible cardinalities of the equivalence classes?
0
votes
0answers
51 views

Undergraduate Set theory

I'm reviewing some set theory notes and I know its a basic question, but I just want confirmation. Let the universe of discourse be $\mathbb{Z}$. What is $\{x \mid x\geq 0 \wedge x>0\}$ equal ...
3
votes
1answer
43 views

Show that $≺$ is a total ordering

Let $ℕ$ be the set of positive integers. Let $D(n)$ denotes the number of divisors of $n$. We define this binary relation: $n≺m⇔n≤m$ and $D(n)≤D(m)$ where $≤$ is the usual ordering in $ℕ$. Show ...
0
votes
2answers
59 views

Is this proof of uncountability of Cantor set true?

To construct Cantor set $C$, start with $I_1=[0,1]$ and define $$E_1=\{0,1\}=\{x:x\text{ is an end point of the set }I_1\}.$$ $\operatorname{card}(E)=\#(E)=2$. After deleting the middle open interval ...
9
votes
5answers
871 views

Contradictory definition in set theory book?

I'm using a book that defines $A\setminus B$ (apparently this is also written as $A-B$) as $\{x\mid x\in A,x\not\in B\}$, but then there was an exercise that asked to find $A\setminus A$. Wouldn't it ...
1
vote
2answers
34 views

Proof of the description of a set

We are supposed to describe the set $\bigcup_{n=1}^\infty A_n$ with a proof. $A_n = \{(x, y) \in \mathbb{R}^2 | y-x^{2n} \geq 0 \}$. This is what I have so far: "This is just the set of all points ...
1
vote
1answer
27 views

What can we say about the set X?

We have a certain set $X$ for which is valid: $\forall U\subset X:[ U\neq X ]\rightarrow U\nsim X$. What can we say about $X$? I think we've got to use the axiom of choice here. My first guess would ...
0
votes
1answer
34 views

Cantor's theorem.

If $A$ is a infinite set then the power set of $A$, $\mathcal{P}(A)$, is an uncountable set. To proof first I take $A$ countable, and I suppose $\mathcal{P}(A)$ is countable, i.e., ...
1
vote
2answers
37 views

Is there an uncountable set S, a subset of P(N), such that for any A,B an element of S; the intersection of A and B is finite? [duplicate]

I have a feeling no such uncountable set exists but have no idea how I could formulate a proof to show this. If such an uncountable set did exist I could try and use a form of the diagonalization ...
1
vote
1answer
37 views

Proving that $x \not\in B \cap C \iff x \not\in B \lor x \not\in C$.

I've got a set theory question. I'm required to show that $x \not\in B \cap C$ if and only if $x \not\in B$ or $x \not\in C$. I decided to call the universal set $S$ (which contains both and $B$ and ...
0
votes
1answer
29 views

Set notation check

Are the three statements: $(a,b,c)\in\mathbb{Q}^3$ $\{a,b,c\}\subset\mathbb{Q}$ $a,b,c \in\mathbb{Q}$ equivalent ways of saying that a, b and c are rational numbers?
2
votes
2answers
60 views

Opposite of a function being bijective?

A function is bijective if it is both surjective and injective. Is there a term for when a function is both not surjective and not injective?
0
votes
2answers
23 views

Can a surjective function have an element in the domain not mapped to the codomain?

I have seen a lot of definitions for surjectivity stating that every element in the codomain must be mapped to something in the domain. But does the opposite also have to hold true for a function to ...
5
votes
1answer
30 views

Is the limit of a recursive sequence of recursive ordinals itself a recursive ordinal?

Is the limit of a recursive sequence of recursive ordinals itself a recursive ordinal? If so, is there a nice proof of this?
0
votes
2answers
59 views

Suppose A and B are finite sets and $f : A \rightarrow B$ is surjective. Is it possible that |A| < |B|?

I am trying to understand better what surjective functions is from a set $A$ to a set $B$, and from what I understood, it basically means this: A function is subjective (onto) from set $A$ to set ...
1
vote
1answer
29 views

Is $A∩B^c∩C^c = A-[A∩(B∪C)] $ ? (Set Theory)

I'm studying set operations. The example problem is: Find a simpler expression of $[(A∪B)∩(A∪C)∩(B^c∩C^c)]$ assuming all three sets intersect. The answer I came up with is $A∩B^c∩C^c$, while the ...
0
votes
2answers
44 views

can the empty set be an element of a group?

is the following group legal: $x = \{1,2,\emptyset\}$? If so, is $P(x) = \{ \emptyset, \{1\}, \{2\}, \{1,2\}, \{\emptyset\}, \{1, \emptyset\}, \{2,\emptyset\}, \{1,2,\emptyset\} \}$ ? When I write ...
3
votes
2answers
103 views

Confusion about the definition of function

Yesterday I was talking to one of my friends about the definition of function. The formal definition of function is given by Cartesian Products but my friend's question was whether it is possible to ...
2
votes
2answers
39 views

Maximum number of relations?

The question is that we have to prove that if $A$ has $m$ elements and $B$ has $n$ elements, then there are $2^{mn}$ different relations from A to B. Now I know that a relation $R$ from $A$ to $B$ is ...
1
vote
1answer
35 views

What is the cardinality of the class of $0$ in $\mathbb{R}$?

What is the cardinality of the class of $0$ in $\mathbb{R}$? In other words: what is the cardinality of the class of all rational Cauchy sequences that converge to $0$?
4
votes
6answers
410 views

Question on induction technique

When one uses induction (say on $n$) to prove something, does it mean the proof holds for all finite values of $n$ or does it always hold when even $n$ takes $\pm\infty$?
0
votes
2answers
33 views

Set theory and logic proof

Problem: Prove that if the sets $A,B,C \in U$, where $U$ is a universal set, then $A \cap B = A \cup B$ if and only if $A = B$ My attempt:We can show that $A \cap B = A \cup B$ if $A = B$ with the ...