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

2
votes
2answers
49 views

Uncomputability of subset relation

I suppose this obvious question should already be answered in plenty of places, but for some reasons I cannot find a proof of this anywhere. Prove or disprove that their exist a set $X$ that is ...
2
votes
2answers
62 views

Proof for Surjections

I'm reading through Basic Algebra I (which I enjoy so far. Thoughts on this for self-studying?) and am having a difficult time proving surjection. I believe I understand the concept, but when it comes ...
-1
votes
2answers
86 views

Showing that $A\rightarrowtail A \times \{x\}$ is a bijection

$A\rightarrowtail A \times \{x\}$ where $A$ is any set and $\{x\}$ is an arbitrary one-object set. How would I show the following is a bijection ( one to one and onto)? I know if I turn it into a ...
1
vote
1answer
36 views

Proving some properties of $\Bbb N$ without using recursion

I will try to prove that if $a, b, c \in \Bbb N$ and $a \in b \in c$, then $a \in c$ (the transitivity property). I will not use recursion or the replacement axiom. Actually we can proove in the same ...
0
votes
2answers
69 views

$\Bbb Z^\ast$ What is this notation?

What does $\Bbb Z^\ast$ mean? I would think some subset of the integers but I cannot find a definition. Thank you.
1
vote
2answers
45 views

Problem Involving a Generalized Cartesian Product

Let $I$ be a set, and for each $i \in I$, let $U_i$ and $V_i$ be sets. Furthermore, suppose for each $i \in I$, there is a bijection $f_i:U_i \to V_i$. Prove that there is a bijection $g:\prod_{i \in ...
0
votes
1answer
32 views

How to deduce number of unordered distinct pairs using set operations and bijections

In (b) of the example, we are ask to calculate the number of ordered pairs of distinct positive integers. I like the first method's answer (using bijections, set operations) because it clearly shows ...
1
vote
2answers
80 views

Prove: If $A \subseteq B$ and $B \subseteq C$, then $A \subseteq C$.

Can someone tell me if this proof is acceptable? Assume $A \not\subseteq C$. This means that there is an $x \in A$ such that $x \not\in C$. But since $\forall x \in A: x \in B$ and $\forall x \in B: ...
1
vote
1answer
30 views

Defining an ordered pair as a set

In mathematics we define mathematical objects in terms of other mathematical objects. For example, some textbooks define $(a,b)$ as a set. Such as, $$(a,b):= \{\{a\},\{a,b\}\}$$ Now, the cardinality ...
0
votes
2answers
27 views

Set and cardinality injection and surjection proof [duplicate]

Let X be a set. Prove there is an injection from $X \rightarrow 2^X$. Prove that there is not a surjection from $X \rightarrow 2^X$. My try- Assume to the contrary that $f: X \rightarrow 2^X$. is a ...
1
vote
2answers
33 views

Showing the natural number same cardinality as as even?

I am having problem with the onto part of this problem. $\mathbb{N}\rightarrow \mathbb{E}$ My function or pattern is $x \rightarrow f(x)=2x$ Which take my natural to even. One to One ...
2
votes
3answers
101 views

How to show the integers have same cardinality as the natural numbers?

How would I show the following have a bijection. Which is one to one and onto ofcourse. $\mathbb{Z}\rightarrow \mathbb{N}$ I know I need to find a function. But I do not see the pattern that makes ...
0
votes
2answers
25 views

Help with constructing power set

I' trying to construct the power set of $A = \{\phi, \{a\}\}$ and would appreciate some help. Now, the definition of a power set says that it's the set of all possible subsets of a given set. ...
0
votes
0answers
41 views

Two definitions of functions

In literature on logic and set theory, there seem to be two different definitions of functions, one more general than the other. First of all, a function $f\colon X\to Y$ consists of three element ...
3
votes
2answers
47 views

finite additivity&countable additivity

Let $\tau$ be a semialgebra of subsets of $\Omega$ and let P: $\tau\rightarrow [0,1]$, with $P(\Omega)=1$, and it satisfies finite additivity: $P\big(\bigcup_{i=1}^{n}D_i\big)=\sum_{i=1}^{n}P(D_i)$ ...
0
votes
1answer
60 views

Prove the reflexivity of $\subseteq$.

My professor gave me a list of exercises, I've been able to figure out what mechanism I should exploit to prove them, but I'd like to know if it's good. Until now we've been taught a little logic and ...
1
vote
1answer
28 views

The function space from $n$ to $m$ and the exponent $m^n$ are equinumerous (proof)

Can someone provide a tip with creating the bijection for the titular problem? Any tip is helpful! Update: $n=\{ 0,\ldots,n-1 \}$, $m=\{ 0,\ldots,m-1 \}$, and $ m^n=\{0,\ldots,m^n-1\} $. In other ...
2
votes
0answers
37 views

Elementary set-theory question

Very basic problem, just wanted to be sure I did this correctly. The problem is "Show that $X-Y = X \cap \overline{Y} $". There was hint in the problem telling one to let our universe $U=X \cup Y$. ...
1
vote
1answer
70 views

Looking for a bijection between this set and natural numbers

I am a computer programmer, and I am struggling with this mathematical problem without finding a consistent and efficient solution. Let $A_{k, M}$ be the set of all the possible assignments for $n_1, ...
3
votes
3answers
37 views

An example of symmetric transitive relation that is not reflexive on a set of natural numbers $\mathbb{N}$ [duplicate]

An example of symmetric transitive relation that is not reflexive on a set of natural numbers $\mathbb{N}$. My guess is that such relation does not exist, but I don't know how to prove it.
1
vote
1answer
35 views

Why do we need the axiom of choice in showing the non-emptiness of an infinite Cartesian product

Given $I$ a set of indexes and $X_i$ a set of topological spaces, define The Cartesian product: $\prod_{i \in I}X_i = \{ f:I \rightarrow \bigcup X_i | f(i) \in X_i \}$ I have read that we need ...
4
votes
2answers
218 views

Prove the principle of mathematical induction in $\sf ZFC $

How does one prove the principle of mathematical induction using the standard axioms of $\sf ZFC $?
2
votes
2answers
33 views

Composition of injections (proof)

I'm trying to prove that composition of injections is an injection. I want to know if this is a good proof: Composition of injections is an injection. Let $f:S_1\rightarrow S_2$ and ...
0
votes
1answer
57 views

How to prove that $f:\mathbb{N}\rightarrow X$ where $f$ maps to an element in a set, is a bijection?

Let $X$ and $Y$ be disjoint finite sets, $|X|=n$ and $|Y|=m$, so that we have the following bijections: $f:\mathbb{N}_n \rightarrow X$ and $g:\mathbb{N}_m \rightarrow Y$ I need to prove that ...
-2
votes
1answer
566 views

Uncountability of numbers written in binary system [on hold]

One can do a mapping between binary decimal numbers and integers like this: ...
-2
votes
2answers
113 views

Well-ordered sets, properties of an element that is not largest in the set

Can anyone please help me in this question: $(X,\leq )$ is a well-ordered set. $\forall x\in X$, either $x$ is the largest element of $X$ or there exists $y\in X$ such that (i) $x<y$ and ...
0
votes
2answers
52 views

Prove that the sets $S$ and $D$ have the same cardinality

Prove that the sets $S$ and $D$ have the same cardinality, where $S = \{(x,y)\mid-1\leq x \leq 1\text{ and }-1\leq y\leq 1\}$ and $D = \{(x,y)\mid x^2 + y^2 \leq 1\}$.
1
vote
2answers
58 views

Prove $|A| = |B|$

Let $A= \{a_1,a_2,a_3,\ldots\}$. Define $B = A − \{a_{n^2} : n \in\mathbb N\}$. Prove that $|A|=|B|$. I would say that $B = \{a_2,a_3,a_5,a_6,\ldots\}$. Thus $B$ is a infinite subset of $A$ and ...
0
votes
1answer
45 views

Why we use ANY in the definition of a maximal element?

I am confused about the following definition: "a maximal element of a subset S of some partially ordered set is an element of S that is not smaller than any other element in S." I do not understand ...
3
votes
1answer
64 views

What is a 'disjunct' of a union called?

Say I have a set $C = A \cup B$ and I want to refer to $A$ in natural language. Had the expression been a Boolean formula with a disjunction, then I would call $A$ the first disjunct. Is there a ...
6
votes
3answers
118 views

Functions with different codomain the same according to my book?

My book gives the following definition: A function $f$ from $A$ to $B$ is defined as $f\subseteq A\times B$ such that if $(a,b)\in f$ and $(a,b_1)\in f$ then $b=b_1$ and there exists a $(a,b)\in ...
3
votes
1answer
227 views

Finding intersecting subsets for given binomial coefficient

My apologies if this question is more appropriate for mathisfun.com, but I can only get so far reading about combinatrics and set theory before the interlocking logic becomes totally blurred. If this ...
1
vote
0answers
55 views

Zuckerman's “Sets and Transfinite Numbers”

I am beginning a study in set theory and I found an old book in my school's library by Martin Zuckeman called Sets and Transfinite Numbers which was published in the 1970's. Has anyone used this text ...
12
votes
6answers
2k views

A strange puzzle having two possible solutions

A friend of mine asked me the following question: Suppose you have a basket in which there is a coin. The coin is marked with the number one. At noon less one minute, someone takes the coin ...
4
votes
1answer
89 views
+50

Halmos “Measure theory” exercise on limit of sequence of sets

Problem statement. This is an exercise from chapter 1, section 4 (problem 13) from Halmos textbook: If $\{E_n\}$ is a sequence of sets, write $D_1=E_1, D_2=D_1 \triangle E_2, D_3=D_2 \triangle E_3$ ...
1
vote
1answer
559 views

Is the intersection of the function of two sets a subset of the function of the intersection of two sets?

Let X and Y be sets and let f: X --> Y be a function from X to Y. If A and B are subsets of X, is it true that f(A) intersect f(b) is a subset of f(A intersect B)? If so, prove your answer; ...
1
vote
0answers
43 views

How can I find the smallest set of groups of $n$ elements such that every element is in the same group as every other at least once?

Background: I'm working on a King of the Hill challenge for Programming Puzzles & Code Golf, and I've run into a problem with how I'm creating the individual matchups (groups of 4 entries). ...
2
votes
4answers
87 views

Prove $A \subset \emptyset \iff A = \emptyset$

How does one prove this? Can one prove by contradiction by saying: Let $A$ be any set such that $A$ contains at least one element. Now assume $A \subset \emptyset$. This is clearly absurd by the ...
2
votes
1answer
25 views

Finding two functions, $f, g$, such that $\mathrm{sup}(g \circ f[\omega]) < \mathrm{sup} (g[\omega + \omega])$

I've been working for some time on Schimmerling's A course on Set Theory, and, thanks to you guys, I'm now almost finishing chapter 3 on ordinals (hah!). In one of the last exercises, he ask us to ...
0
votes
3answers
56 views

Conceptually: A set whose elements can only be probabilistically characterized?

Sorry for the informality here, but was musing over the basic concepts around describing a set in real world usage: A finite set of explicitly named elements, this apple and that apple, nothing more ...
0
votes
4answers
90 views

Which of these sets is bigger?

I am a fourth year computer science student and I am taking second year level maths because they are very useful for computer stuff. At the end of the linear algebra lecture the Prof left us with a ...
0
votes
0answers
22 views

$a\le b$ iff there exist $\left|A\right|=a, \left|B\right|=b$ and $A\subseteq B$ [duplicate]

$a\le b$ iff there exist $\left|A\right|=a, \left|B\right|=b$ and $A\subseteq B$ My Proof: $(\Leftarrow)$ $A\subseteq B$ implies immediately that $\left|A\right|\le\left|B\right|$. Hence, $a\le ...
2
votes
2answers
45 views

Proof of $A \subseteq B \Leftrightarrow A \cap B = A$ (Check chain of implications)

Prove $A \subseteq B \Leftrightarrow A \cap B = A$. My attempt: Case $\Rightarrow$: $$\begin{align} A \subseteq B & \Rightarrow & [x\in A \Rightarrow x\in B] \\ &\Rightarrow &[x ...
2
votes
2answers
30 views

Help to prove $f$ is surjective $\Leftrightarrow \forall y \in Y, (X \times \{y\} \cap G_f ) \ne \emptyset $

Let $f:X \rightarrow Y$ be a function with graph $G_f \subseteq X \times Y$. Prove that $f$ is surjective if and only if $\forall y \in Y, (X \times \{y\} \cap G_f ) \ne \emptyset $ I have some ...
1
vote
0answers
14 views

Showing minimality of this set without resorting to trichotomy

I am working on this problem, which is to show that if $E$ is a nonempty subset of a natural number, then there is $k\in E$ such that for every $m\neq k$ in $E$, we have $k\in m$. I realized when ...
1
vote
1answer
41 views

Proving $X\sim Y$

Let $f:A\rightarrow B$, a bijection. Suppose $X\subseteq A$ and $Y\subseteq B$ are two sets such that $f(X)\subseteq Y$ and $f^{-1}(Y)\subseteq X$. Show that $X\sim Y$ and $f/X$ is the bijection ...
4
votes
6answers
1k views

In a class of 65, there are twice as many maths students as biology students.

I have a task: In a class of 65, there are twice as many maths students as biology students. If 12 biology students do not take maths and 15 students take neither of these subjects, how many students ...
0
votes
2answers
44 views

Sets as extremely trivial groups

A group is a structure defined upon an underlying set which is endowed with a single binary operator that has some rules attached to it. I was wondering whether one could describe a set itself as ...
2
votes
1answer
26 views

How to express membership to at least $m$ sets in a sequence of sets.

Suppose we have a sequence of sets $(A_{n})$. Pick some positive integer $m$. How would you express the set of all points that belong to at least $m$ sets in the sequence $(A_{n})$? I tried toying ...
3
votes
2answers
113 views

∅ ⊆ { ∅ } Is this true or false?

True or false? Im guessing true because an empty set is a subset of every set. Is this a correct assumption? The only time an empty set is not a subset of something is when its a proper subset of an ...